Ler o artigo completo
Transcrição
Ler o artigo completo
Números (Pseudo) Aleatórios, Probabilidade Geométrica, Métodos de Monte Carlo e Estereologia Humberto José Bortolossi Instituto de Matemática e Estatı́stica Universidade Federal Fluminense 1 Números (pseudo) aleatórios Muitos jogos de computador realizam ações que, em princı́pio, parecem ser aleatórias: embaralhar as cartas no jogo paciência, distribuir as minas no jogo campo minado, lançar dados em um jogo de RPG (Role Playing Game), etc. Todas estas ações são programadas a partir da suposta capacidade do computador de gerar números aleatórios. Contudo, a maioria dos computadores digitais domésticos atuais não geram números aleatórios. O que estes computadores fazem é usar um algoritmo para produzir números (denominados pseudoaleatórios) que “simulam” o comportamento de números aleatórios. Um dos algoritmos mais simples para se gerar números pseudoaleatórios (e ainda muito usado em vários programas computacionais) é o assim denominado gerador congruente linear (GCL), apresentado por D. H. Lehmer em 1949: considere números inteiros m, a, c e s tais que m > 0, 0 ≤ a < m e 0 ≤ s < m. Escrevendo x0 = s, defina recursivamente, para cada inteiro n ≥ 0, xn+1 = (a xn + c) mod m, isto é, xn+1 é o resto da divisão de a xn + c por m. Por exemplo, se m = 10, a = 11, c = 3 e x0 = s = 3, então a x0 + c = 36. Como o resto da divisão de 36 por 10 é 6, segue-se que x1 = 6. Sendo assim, a x1 + c = 69. Como o resto da divisão de 69 por 10 é 9, segue-se que x2 = 9. Prosseguindo-se com este esquema, a partir do número x0 = 3, geramos os números x1 = 6, x2 = 9, x3 = 2, x4 = 5, x5 = 8, x6 = 1, x7 = 4, x8 = 7, x9 = 0 e x10 = 3. Note que depois de x10 , a sequência de números gerados se repete (com perı́odo 10). As constantes m, a e c são escolhidas seguindo basicamente dois critérios: (1) o método deve gerar um grande número de valores diferentes (isto é, o perı́odo da sequência deve ser longo) e (2) o método deve gerar números rapidamente. Os GCLs geram números inteiros positivos entre 0 e m. Para gerar números decimais entre 0 e 1, basta dividir os números gerados por m. Os geradores congruentes lineares são rápidos e usam pouco memória do computador. Contudo, dependendo da aplicação, o seu uso não é recomendável. Um defeito grave dos GCLs é que os números gerados possuem uma correlação: triplas de números geradas aglomeram-se em um determinado número de planos paralelos ([Marsaglia, 1968], [Knuth, 1998]). A figura a seguir ilustra este fato. 1 Nesta figura, 10000 pontos foram gerados no cubo unitário usando-se o algoritmo RANDU da IBM, o GCL definido pela escolha m = 2147483648, a = 65539 e c = 0. O RANDU foi muito usado nos computadores de grande porte das décadas de 1960 e 1970. Observe como os 10000 pontos gerados se aglomeram sobre 15 planos dentro do cubo. Dado a este defeito, especialistas não recomendam o emprego de um GCL, por exemplo, em criptografia, pois um hacker poderia explorar esta particularidade dos GCLs para descobrir os valores dos parâmetros m, a e c a partir da sequência gerada. Isto aconteceu com o antigo navegador de internet Netscape em 1995: dois alunos da Universidade de Berkeley nos Estados Unidos conseguiram descobrir o GCL usado pelo navegador. Além dos GCLs, existem vários outros geradores de números pseudoaleatórios: Mersenne Twister (usado no PlayStation 3 e com perı́odo 219937 − 1), Blum Blum Shub (usado em criptografia), Xorshift de George Marsaglia, etc. Existem geradores de números verdadeiramente aleatórios? Para responder a esta pergunta, é preciso definir antes o que se entende por um número ou evento aleatório. Esta é uma questão polêmica, sendo ainda debatida por psicólogos, filósofos, matemáticos, fı́sicos e cientistas da computação. Por exemplo, você poderia pensar que o lançamento de uma moeda honesta é um evento aleatório com probabilidade “1/2” para cara e probabilidade “1/2” para coroa. Mas o lançamento de uma moeda também pode ser pensado como um processo determinı́stico (complexo, mas ainda determinı́stico), regido pelas leis da Fı́sica. De fato, o artigo [Diaconis, Holmes, Montgomery, 2007] descreve um experimento onde, através de um ajuste de velocidade inicial e momento angular, uma moeda lançada por uma máquina sempre dá como resultado cara. Os excelentes artigos [Volchan, 2004] e [Volchan, 2002] apresentam e discutem as várias definições propostas para a noção de aleatoriedade. Mesmo sem um consenso com relação a definição de aleatoriedade, empresas têm comercializado dispositivos que, segundo elas, produzem números verdadeiramente aleatórios. Várias técnicas são empregadas: medições de ruı́do atmosférico, medições de decaimento radioativo, fotografias de lâmpadas de lava e processos óticos em fı́sica quântica. A capacidade de se gerar números (pseudo) aleatórios tem várias aplicações. Por exemplo, ela é uma peça-chave nos vários algoritmos que permitem criar simulações computacionais de diversos fenômenos em várias ciências ([Gentle, 2003], [Ross, 2006]). Na próxima seção veremos como a geração de números (pseudo) aleatórios pode ser usada para se calcular, de forma aproximada, medidas de comprimento, área e volume. 2 Probabilidade Geométrica, Métodos de Monte Carlo e Estereologia Seguindo [Wagner, 1997], considere a situação onde um atirador, com os olhos vendados, tenta acertar um alvo circular com 36 cm de raio tendo no centro um disco vermelho de 3 cm de raio. Se soubermos que o atirador acertou o alvo, qual é a probabilidade de que ele tenha atingido o disco vermelho central? 2 Note que, aqui, o espaço amostral é infinito (todos os pontos do alvo), como também é infinito o conjunto dos casos favoráveis (todos os pontos do disco vermelho central). Mesmo não podendo “contar” casos possı́veis e casos favoráveis, é bem razoável considerar que a probabilidade de acertar o disco central deve ser a razão entre as áreas do disco e do alvo, no caso 1/144, menos de 0.7% (como o atirador está vendado, não existem pontos privilegiados no alvo). Este é um exemplo de probabilidade geométrica: se tivermos uma região B do plano contida em uma região A, admitimos que a probabilidade de um ponto de A também pertencer a B é proporcional à área de B e não depende da posição que B ocupa em A. Portanto, selecionado ao acaso um ponto de A, a probabilidade de que ele pertença a B será: p = (área de B)/(área de A). Se, em vez de regiões no plano, A e B forem regiões no espaço, então selecionado ao acaso um ponto de A, a probabilidade de que ele pertença a B será: p = (volume de B)/(volume de A). Usando-se a fórmula p = (área de B)/(área de A) e a geração de números (pseudo) aleatórios, podemos criar um método para estimar a área desconhecida de uma região B contida em uma região A de área conhecida. Suponha, por exemplo, que você não saiba o valor da área do cı́rculo B de centro (1/2, 1/2) e raio 1/2, mas saiba a área do quadrado unitário A = [0, 1] × [0, 1]. Gerando-se pares ordenados de números (pseudo) aleatórios uniformemente distribuı́dos no quadrado A, contamos o número total m de pontos sorteados e o número n de pontos sorteados que pertencem ao cı́rculo B. O número r = n/m dará uma aproximação de p e, portanto, o número r × (área de A) dará uma aproximação para a área de B (no caso, π/4 = 0.78539816 . . .). Na figura: n = 64, m = 78 e r = n = 0.82051282 . . . . m Este tipo de técnica de análise de fenômenos através de algoritmos de computador que empregam essencialmente a geração de números (pseudo) aleatórios é denominado “Método de Monte Carlo”. O nome “Monte Carlo” foi dado por Stanislaw Ulam (1909-1984) e John von Neumann que inventaram o método para resolver problemas de difusão de nêutrons relacionados com projetos de armas nucleares (Projeto Manhattan) no Laboratório Nacional de Los Alamos, Estados Unidos, por volta de 1940 ([Metropolis, Ulam, 1943], [Metropolis, 1987]). Stanislaw Ulam John von Neumann Segundo sua autobiografia ([Ulam, 1976]), “Stanislaw Ulam ajudou a dar forma a algumas das mudanças mais dramáticas do mundo pós-guerra. Com uma tendência experimental, que o distinguiu de outros matemáticos, foi um dos primeiros a defender e a usar os computadores em pesquisas cientı́ficas. 3 Ulam também contribuiu com ideias para a propulsão nuclear de veı́culos espaciais e fez contribuições fundamentais para muitos dos mais desafiadores projetos matemáticos da atualidade.”. John von Neumann é tido como um dos mais importantes matemáticos do século XX, tendo feito contribuições em matemática, fı́sica, economia, computação e estatı́stica. Junto com Alan Turing (1912-1954) e Claude Shannon (1916-2001), John von Neumann é considerado como um dos idealizadores do computador digital com programas armazenados. Um outro problema de probabilidade geométrica bem interessante foi proposto pelo naturalista francês George-Louis Leclerc (1707-1788), Conde de Buffon: suponha que você esteja em uma sala cujo chão é feito de ripas retangulares de madeira, todas com largura d. Ao se jogar uma agulha de comprimento a, com a ≤ d, qual é a probabilidade da agulha ficar sobre um reta divisória de duas ripas? Com recursos de cálculo integral, é possı́vel demonstrar (consulte, por exemplo, [Tunala, 1992]) que esta probabilidade é igual a p = (2a)/(dπ). Estas conexões entre probabilidade e geometria formam a base da estereologia, campo interdisciplinar cujo objetivo é estudar propriedades geométricas de objetos tridimensionais usando métodos de amostragens ([Howard, Reed, 2005], [Stroeven, Hu, 2009]): sondas geométricas (como pontos, retas, planos e regiões volumétricas) são “jogadas” em um objeto tridimensional de interesse. A dimensão da sonda geométrica depende do que se quer medir no objeto: para se medir o volume do objeto, as sondas são pontos; para se medir uma área no objeto, as sondas são retas; para se medir comprimentos no objeto, as sondas são planos; para se contar “pontos” no objeto, as sondas são regiões volumétricas. Em cada caso, a interseção da sonda com o que se quer medir no objeto são entidades de dimensão zero: pontos. Se as sondas são geradas aleatoriamente de forma apropriada, uma contagem destes pontos fornecerá uma estimativa para a medida que se quer realizar. São estes métodos matemáticos que permitem, através de um aparelho de raios-X, obter medidas de objetos no interior do corpo humano, medidas estas que são inacessı́veis de forma direta. A informação de que os pulmões humanos têm uma superfı́cie (de troca gasosa) equivalente a um campo de tênis foi obtida usando-se métodos estereológicos. Outras áreas que usam estereologia: petrografia (ramo da geologia que trata da descrição e classificação sistemática das rochas, especialmente através do exame microscópico de seções delgadas), ciência dos materiais, histologia e neuroanatomia. É importante diferenciar estereologia de tomografia computadorizada. Em tomografia computadorizada, o objeto de interesse é completamente reconstruı́do a partir de suas seções planas e, a partir desta reconstrução, medidas podem ser feitas. Em estereologia, o objeto não é reconstruı́do. As medidas são estimadas usando-se processos de amostragem através de sondas geométricas. Entre as tecnologias que tornam a estereologia possı́vel estão a ressonância magnética, a ultrassonografia, a microscopia confocal de alta resolução e a microscopia de luz convencional. 4 3 Referências No endereço http://www.uff.br/cdme/rdf/ (ou no espelho http://www.cdme.im-uff.mat.br/rdf/) está disponı́vel uma série de aplicativos interativos que permitem explorar a geração de números pseudoaleatórios e os métodos de Monte Carlo apresentadas neste texto. Também está disponı́vel um arquivo DOC (o Formulário de Acompanhamento do Aluno) com várias sugestões de exercı́cios para serem trabalhados em sala de aula. Orientações didáticas e metodológicas estão disponı́veis no Guia do Professor. Sugerimos as seguintes referências ao leitor interessado em mais detalhes sobre a geração de números pseudoaleatórios, probabilidade geométrica, métodos de Monte Carlo e estereologia. Calude, C. S. Who Is Afraid of Randomness?. CDMTCS Research Report Series, University of Auckland, New Zealand, 2000. Diaconis, P.; Holmes, S.; Montgomery, R. Dynamical Bias in The Coin Toss. SIAM Review, vol. 49. n. 2, pp. 211-235, 2007. Gentle, J. E. Random Number Generation and Monte Carlo Methods. Second Edition. Statistics and Computing, Springer-Verlag, 2003. Howard, V.; Reed, M. G. Unbiased Stereology: Three-dimensional Measurement in Microscopy Advanced Methods. Taylor & Francis Routledge, 2005. Knuth, D. E. The Art of Computer Programming. Volume 2. Seminumerical Algorithms. Addison Wesley Longman, 1998. Marsaglia, G. Random Numbers Fall Mainly in The Planes. Proceedings of the National Academy of Sciences of the United States of America, v. 61, n. 1, pp. 25-28, 1968. Metropolis, N. The Beginning of The Monte Carlo Method. Los Alamos Science, n. 15, pp. 125-130, 1987. Metropolis, N.; Ulam, S. The Monte Carlo Method. Journal of The American Statistical Association, vol. 44, n. 247, pp. 335-341, 1949. Peterson, I. The Jungles of Randomness – A Mathematical Safari. Wiley, 1998. Ross, S. M. Simulation. Fourth Edition. Academic Press, 2006. Shonkwiler, R.; Mendivil, F. Explorations in Monte Carlo Methods. Undergraduate Texts in Mathematics, Springer-Verlag, 2009. Stroeven, P.; Hu, J. Review Paper – Stereology: Historical Perspective and Applicability to Concrete Technology. Materials and Structures, v. 39, pp. 127-135, 2006. Tunala, N. Determinação de Probabilidades por Métodos Geométricos. Revista do Professor de Matemática, Sociedade Brasileira de Matemática, vol. 20, pp. 18-22, 1992. Ulam, S. M. Adventures of A Mathematician. Charles Scribner’s Sons, 1976. Volchan, S. B. What is A Random Sequence?. The American Mathematical Monthly, vol. 109, pp. 46-63, January, 2002. http://mathdl.maa.org/images/upload library/22/Ford/Volchan46-63.pdf Volchan, S. B. A Teoria Algorı́tmica da Aleatoriedade. Em Chediak, K.; Videira, A. A. P. (Editores). Temas de Filosofia da Natureza, UERJ, pp. 123-130, 2004. http://www.uff.br/cdme/arquivos/ volchan-2002.pdf Wagner, E. Probabilidade Geométrica – O Problema do Macarrão e Um Paradoxo Famoso. Revista do Professor de Matemática, Sociedade Brasileira de Matemática, vol. 34, pp. 28-35, 1997. 5