Escolha uma Página
Simulação de Monte Carlo, Jogatina, Criptografia e Bomba Atômica – Qual a probabilidade disso dar certo?

Simulação de Monte Carlo, Jogatina, Criptografia e Bomba Atômica – Qual a probabilidade disso dar certo?

Simulação de Monte Carlo, Jogatina, Criptografia e Bomba Atômica – Qual a probabilidade disso dar certo?

Simulação de Monte Carlo, Jogatina, Criptografia e Bomba Atômica - Qual a probabilidade disso dar certo? 1

Simulação de Monte Carlo é o método que utiliza probabilidade e é fortemente recomendado no Gerenciamento de Risco para análise de prazo de entrega, mas também pode ser visto em várias outras aplicações como o próprio Método dos Elementos Finitos para considerar efeitos aleatórios.

Mas você sabia que tudo isso começou com jogos de cartas?

Não que eu queira incentivá-lo a entrar em uma jogatina, apostar as suas economias em jogos de azar ou mesmo te iludir com a possibilidade de ficar milionário em uma única noite.

Para aqueles que não fazem ideia do que a foto de capa deste artigo representa, estou falando nada menos que do Cassino de Monte Carlo em Mônaco.

Este é um lugar famoso por deixar pessoas ricas em uma única noite, mas fazer muitas outras perderem verdadeiras fortunas em uma única jogada.

E você deve estar se perguntando o porquê de eu estar falando de cassino em um artigo técnico.

Então devo dizer que a história desse cassino se mistura com a construção da bomba atômica americana e de recursos fabulosos utilizados hoje na medicina, finanças e em gerenciamento de projetos.

O conceito de Simulação de Monte Carlo ou Método de Monte Carlo foi proposto por Stanislaw Ulam, matemático polonês, naturalizado americano e que adorava uma jogatina.

Vamos conhecer melhor esta história?

Então acompanhe comigo, estes são os tópicos que veremos:

 

E assim foi criado a Simulação de Monte Carlo

E Assim Foi Criado a Simulação de Monte Carlo

Simulação de Monte Carlo

Estamos quase no fim da Segunda Guerra Mundial e início da guerra fria, Ulam estava se recuperando de uma doença séria.

Ele estava em sua casa, entediado e jogando paciência (Suspeito que todos vocês já jogaram alguma vez no Windows, mas no caso dele, estava jogando com cartas reais mesmo…)

Sendo matemático, Ulam naturalmente se perguntou qual seria a probabilidade de ganhar este jogo estúpido que ele continuava perdendo?

Assim ele passou bastante tempo tentando calcular a combinatória, para chegar no cálculo da probabilidade, mas apesar de ser um matemático realmente incrível, ele falhou.

O fato é que a combinatória era muito complicada.

Então, ele pensou:

“Bem! Suponha que eu apenas jogue muitas vezes, conte o número que eu ganho e divida pelo número de mãos que joguei”.

Então ele pensou sobre isso e concluiu:

“ Eu já joguei muitas vezes e ainda não ganhei e provavelmente levaria anos para jogar mãos suficientes para obter uma boa estimativa, e eu não quero fazer isso – Ah não!! E agora? Quem poderá nos ajudar? Eu é claro! O Chapolin Colorado :)”

Quase isso! O Chapolin Colorado nesta história tem um nome, e garanto que um nome de peso.

Acompanhe…

Então Ulam supôs que ao invés de jogar o jogo, ele apenas simulasse o jogo no computador.

Como ele não sabia nada de computadores, recorreu a um amigo, este era ninguém menos que John von Neumann.

Se este nome não lhe soa familiar, saiba que von Neumann é considerado um dos mais importantes matemáticos do século XX, tendo contribuído para diversos avanços na área, além de ter trabalhado com Einstein e, o principal para esta história, de ter papel fundamental na criação do ENIAC, primeiro computador construído.

Assim foi feito, von Neumann, após algumas horas de trabalho, gerou milhares de resultados aleatórios de partidas, dando ao amigo Ulam a possibilidade de calcular a probabilidade de ganhar no seu joguinho e assim matar mais algum tempo enquanto se recuperava.

Dessa forma foi criado a Simulação de Monte Carlo, batizado assim por Ulam e seus amigos em homenagem ao famoso cassino.

Qual a Sua Relação com A Bomba Atômica?

Algo que ainda não contei é que tanto Stanislaw Ulam quanto John von Neumann trabalhavam juntos no Projeto Manhattan.

Simulação de Monte Carlo

Trabalho este que daria origem a bomba nuclear americana e que anos mais tarde seriam detonadas nas cidades de Hiroshima e Nagasaki.

A fissão nuclear tem como base o efeito dominó onde, após um átomo ter seu núcleo “quebrado”, libera energia que colide com um outro átomo que também tem seu núcleo quebrado e assim sucessivamente até que a reação em cadeia aconteça, liberando uma grande energia em forma de explosão em frações de segundo.

O problema é que essa reação em cadeia depende do “peteleco” inicial, onde uma quantidade certa de Plutônio é quebrada para que esta energia seja liberada e colida com outros átomos.

A colisão entre esses átomos não é exata e depende de cálculos probabilísticos que determina as chances ou não de uma reação atingir o próximo átomo, podendo assim a reação acontecer ou não.

Basicamente há uma linha tênue entre a bomba não explodir e explodir na sua cara enquanto dá uma “lustrada na sua lataria”.

Estamos trabalhando com plutônio, material que já possui decaimento natural e corre o risco de a reação em cadeia começar sem uma intenção prevista.

Ulam e von Neumann (e muitas outras grandes mentes que não estou mencionando aqui), precisavam determinar a quantidade de plutônio a ser utilizado no processo.

Mas, assim como no jogo de cartas, eles não podiam fazer milhares de testes práticos até obter uma quantidade suficiente de amostras para obter uma estatística confiável do quanto precisavam utilizar para ter um resultado seguro.

O teste aqui seria mais ou menos como testar se todos os fósforos de uma caixinha estão funcionando e, para checar, você risca cada um deles. No final saberia se estavam funcionando ou nao, porem nao teria mais nenhum fósforo.

A diferença seria de que, para cada bomba testada, o tamanho de uma cidade inteira seria destruído. E, muito provavelmente, Ulam teria sido riscado do mapa junto com a primeira tentativa.

Como Funciona a Simulação de Monte Carlo? Aplicando o Método no Cara e Coroa

Para exemplificar a Simulação de Monte Carlo, vamos tomar por base uma moeda, como qualquer outra moeda possui cara e coroa.

Simulação de Monte Carlo

Com esta moeda jogada para o alto, quais seriam as probabilidades dessa moeda cair no chão voltada com o lado cara ou com o lado coroa?

Seria fácil determinar a probabilidade pois a moeda só possui dois lados, então a probabilidade seria de 50% para cada lado.

Mas digamos que você não queira usar este método, ou seja, não poderá apenas dividir os 100% por dois lados e resultar em 50%, como conseguiria determinar a probabilidade de cair cara ou coroa?

O outro método é jogar inúmeras vezes a moeda para cima e anotar quantas vezes a moeda caiu para cada lado, por exemplo, você joga a moeda 1.000 vezes para cima, e, por exemplo, em 489 vezes resulta em cara e 511 da coroa.

Fazendo a divisão você terá:

Cara: 489 / 1000 = 48,9%

Coroa: 511 / 1000 = 51,1%

Ou seja, existem 48,9% de chance para Cara e 51,1% de chance para Coroa de que na jogada 1001 dê uma das duas.

Os números não são exatos ao primeiro método, mas representam uma boa aproximação.

Mas o empecilho é que foram necessárias 1000 jogadas para ter um resultado.

Imagine que tivesse sido necessário testar 1.000 bombas até que a quantidade de plutônio fosse determinada. Trabalhar no projeto Manhattan não teria sido nada divertido.

O fato é que o lado que a moeda cai depende de inúmeros fatores que não podem ser expressados matematicamente de forma analítica, apenas a probabilidade é que pode nos dar uma resposta.

Da mesma forma não podemos determinar se irá ou não chover, podemos apenas dar a probabilidade de chuva, resultado que é baseado no número limitado de amostras coletadas e resultados anteriores.

Então imagine que, em vez de jogar a moeda para cima, você utilize números aleatórios gerados por computador, sendo 0 para Cara e 1 para Coroa.

Como estamos falando de números probabilísticos, o uso de números aleatórios, após certo número de jogadas, nos dará uma boa aproximação do resultado que teríamos jogando a moeda.

O curioso é que números verdadeiramente aleatórios não podem ser gerados por computadores convencionais, pois computadores são baseados em lógica de programação e, lógica é o oposto de aleatoriedade.

Portanto, para uma amostra ser verdadeiramente aleatória ela não pode ser previsível, e um computador nada mais é que uma série de funções muito bem pré-estabelecidas.

Então, a geração da amostra aleatória é a chave principal para a Simulação de Monte Carlo.

Descrevendo matematicamente, Números aleatórios estão para a Simulação de Monte Carlo assim como o Anel está para Smigol, my precious!!

Vamos ver outros conceitos e voltar na geração dos números aleatórios em seguida.

Simulação de Monte Carlo Aplicado para Gerenciamento de Risco

Gerenciamento de Risco

Agora digamos que você está trabalhando com Gerenciamento de Projetos na construção de um novo cassino que receberá o nome de Trinity

Você está analisando o Gerenciamento de Risco para determinar quando o prédio será concluído.

Então vamos imaginar a lista abaixo como as etapas do projeto, imagine que você precisa determinar a data de entrega final do cassino, tomando como base a simples lista abaixo, onde as datas foram dadas com base em:

Simulação de Monte Carlo

Tendo essas datas, rapidamente identificaríamos que o projeto teria início em 02/09/1939 e seria concluído em 09/09/1945.

Então como ter a certeza de que essas datas são confiáveis?

Pois bem! Ou você já tem uma larga experiência em construir Cassinos ou há uma grande chance do seu projeto não finalizar no prazo.

Por isso, o que deve ser feito é estipular uma variação para cada data, por exemplo, 20% para mais ou para menos e reavaliar a data de entrega.

O problema é que se você considerar todas as datas com 20% a mais de tempo para ser entregue, você será extremamente pessimista, podendo perder o contrato pois precisaria de muito mais tempo.

O oposto também ocorre, se considerar que todas as tarefas irão ocorrer 20% mais cedo que o previsto, você será muito otimista, que, muito provavelmente, não conseguirá cumprir.

Para ter uma data de entrega com uma probabilidade maior de acerto, será preciso considerar que algumas tarefas irão levar mais tempo que o previsto, quanto outras irão acabar mais cedo, sempre variando valores intermediários entre a data proposta e números intermediários entre +20% e -20%.

Fazendo isso repetidamente por n vezes, com diferentes combinações para cada tarefa, após um certo número de tentativas, você começará a notar que a data de entrega começará a ocorrer em sua maioria em um certo intervalo de tempo, ou seja, aquela será a maior probabilidade de entrega final.

Entendo a Fundo a Matemática por Trás do Método

Uma boa probabilidade dependerá sempre de uma boa amostra, ou seja, dependerá que os valores escolhidos sejam realmente aleatórios.

Matemática por trás do método de monte carlo

E como visto anteriormente, computadores convencionais não são capazes de criar números ao acaso, tudo dependerá de uma fórmula previamente escolhida.

A geração desses resultados através de softwares de computador é, na verdade, chamada de pseudo aleatórios, uma vez que a aleatoriedade pode ser prevista sabendo o número inicial (também conhecido como seed ou semente), e há várias maneiras de serem gerados.

Um número pseudo aleatório é, na verdade, um procedimento determinístico, onde um programador utiliza um algoritmo de combinação que passará a ilusão de que os números são gerados aleatoriamente.

Um bom gerador de números aleatórios deve ter uma boa distribuição, falta de previsibilidade (a menos que se conheça a semente inicial) e não haver repetição.

Veja um exemplo simples:

Número Aleatório = 7 x Semente Mod(11)

*mod é um comando bem conhecido em programação que significa resto, ou seja, após realizar a divisão de um número pelo valor que está dentro dos parênteses, o comando retorna o resto da divisão, por exemplo:

5 / 2 = 2 e o resto é igual 1, voltando para o nosso exemplo:

O número 7 e o número 11 foram escolhidos aqui por serem números primos, isso ajuda ainda mais na “imprevisibilidade”. Para o nosso exemplo iremos utilizar o número 3 como semente inicial.

Número Aleatório = 7 x Semente Mod(11)
Número Aleatório = 7 x 3 Mod(11)
Número Aleatório = 21 Mod(11)
Número Aleatório = 10

Pois 21 / 11 = 1 e tem resto = 10, assim o nosso primeiro número aleatório será 10 e este mesmo número servirá de semente para a próxima interação:

Número Aleatório = 7 x Semente Mod(11)
Número Aleatório = 7 x 10 Mod(11)
Número Aleatório = 70 Mod(11)
Número Aleatório = 4

Pois 70 / 11 = 6 e tem resto = 4

Se repetirmos seguidamente este processo obteremos:

Número Aleatório = 7 x 4 Mod(11) = 6
Número Aleatório = 7 x 6 Mod(11) = 9
Número Aleatório = 7 x 9 Mod(11) = 8
Número Aleatório = 7 x 8 Mod(11) = 1

Nesta sequência, geramos os seguintes números pseudo aleatórios:

10, 4, 6, 9, 8, 1

Ao criar um algoritmo, o programador poderá optar por qualquer metodologia, o mais importante é que a semente não seja escolhida arbitrariamente, pois, no caso do exemplo, sempre que a semente inicial for o número 3, a sequência será sempre a mesma.

Para esta geração é comum a utilização hardware e não de software para a determinação da semente inicial, por exemplo, ler o estado de tensão de alimentação do processador do computador.

Mas, ainda assim, sabendo qual é este número já saberemos qual será toda a sequência de números gerados.

Esta problemática é enfrentada por todo computador convencional, e os programadores sofrem para criar este número.

Em criptografia, o embaralhamento é realizado utilizando a chave de criptografia, uma espécie de senha (que aqui é a nossa semente) e assim embaralhando a mensagem.

Uma mensagem criptografada é quase impossível de ser quebrada, pois cada bit de dado poderia ser qualquer estado de 0 ou 1.

Porém, conhecendo a semente original (chave de criptografia) e o método de embaralhamento, reverter a criptografia será muito fácil, bastando fazer o processo inverso.

Com o avanço dos computadores quânticos, a criptografia está seriamente ameaçada.

Um computador convencional não consegue ler uma mensagem criptografada não porque ela é inquebrável, mas sim porque a resolução e entendimento do método utilizado levaria um tempo impraticável.

Computadores quânticos utilizam em sua metodologia as probabilidades quânticas, onde cada estado é chamado de qubits. Um computador convencional é baseados em bits de dados que podem conter o estado de 0 ou 1, quanto no computador quântico o estado pode ser 0, 1 ou uma sobreposição dos dois.

Um computador quântico pode ser criado utilizando átomos, fótons ou mesmo elétrons e pósitrons. O importante é que a partícula se comporte em conformidade com a mecânica quântica.

Complicado o negócio não?

Mas é a aleatoriedade que torna a Simulação de Monte Carlo viável.

Por exemplo, no MS Excel, há uma função ALEATÓRIO() e esta função irá retornar um número qualquer.

Muitos especialistas que dependem de probabilidade e estatística, defendem que esta função do Excel não deve ser utilizada, pois a sua geração é fraca e tende a criar sequências iguais depois de um determinado número de interações.

Então, se nem os computadores modernos (fora os computadores quânticos) não são capazes de gerar números aleatórios, como foi que Ulam e von Neumann resolveram este problema?

A resposta é, eles não resolveram.

John von Neumann foi sem dúvida o cérebro por trás da arquitetura dos computadores que utilizamos até hoje, porém o ENIAC não pode ser utilizado nesta tarefa.

Na verdade, o ENIAC só foi totalmente finalizado em 1946, quando a guerra já tinha acabado e as bombas nucleares Little Boy e Fat Man já tinham sido detonadas em Hiroshima e Nagasaki em 06 e 09 de agosto de 1945 respectivamente.

O grupo fez uso de computadores humanos, em sua grande maioria mulheres (homens não são bons para isso), para resolver inúmeros cálculos complexos.

Essas mulheres nem sabiam o que estavam calculando uma vez que o projeto era secreto, o que ajudava na geração de números verdadeiramente aleatórios.

Algumas pessoas só souberam dezenas de anos mais tarde que tinham sido parte do projeto que matou centenas de milhares de japoneses.

E não é segredo pra ninguém, mas infelizmente muitas das tecnologias que temos hoje tiveram origem em períodos de guerra.

Por isso, muitas dessas histórias acabam se emaranhado, como a que conto neste artigo [ MÉTODO DOS ELEMENTOS FINITOS, OU VOCÊ SABE COMO FUNCIONA OU VOCÊ SERÁ SEMPRE UM N.N.F ], onde podemos destacar a larga utilização dos computadores na resolução do Método dos Elementos Finitos.

Que inclusive é outra utilização que vem ganhando espaço.

Na Simulação por Elementos Finitos, a Simulação de Monte Carlo vem sendo aplicada para considerar os efeitos aleatórios do carregamento em problemas estáticos e dinâmicos de estruturas reticuladas espaciais.

Para finalizar, vale ressaltar que o passado nos mostra que tecnologias foram desenvolvidas para matar pessoas, mas caberá a nós decidirmos se a evolução desses métodos serão utilizados para criar ou para destruir.

Simulação de Monte Carlo, Jogatina, Criptografia e Bomba Atômica - Qual a probabilidade disso dar certo? 2

Fabrício Leinat

Fundador do Clube do Projetista

Projetista e Gerente de Projetos, atuou em projetos na Alemanha, Irlanda, Itália e nos Estados Unidos. Especialista em Simulação Numérica, Cálculo Estrutural e Otimização de Projetos, atua com os softwares Ansys, Matlab, Kissoft, Mathcad, SolidWorks, SolidWorks Simulation, SolidWorks Flow Simulation, Mode Frontier, Creo Parametric, Autocad e Scilab.