Monografia
(→Aspectos Históricos) |
(→Aspectos Históricos) |
||
Linha 74: | Linha 74: | ||
Paralelamente a isso, um time de cientistas, engenheiros e técnicos trabalhava na construção do primeiro computador eletrônico – o ENIAC – na Universidade da Pensilvânia, na Filadélfia. Os mentores da equipe se inspiraram para a criação do computador elétrico ao ver filas e filas de mulheres fazendo contas em suas calculadoras de mesa. O computador eletrônico seria construído para lidar com tais processos. | Paralelamente a isso, um time de cientistas, engenheiros e técnicos trabalhava na construção do primeiro computador eletrônico – o ENIAC – na Universidade da Pensilvânia, na Filadélfia. Os mentores da equipe se inspiraram para a criação do computador elétrico ao ver filas e filas de mulheres fazendo contas em suas calculadoras de mesa. O computador eletrônico seria construído para lidar com tais processos. | ||
− | Com a criação do ENIAC, Stanislaw Ulam viu a possibilidade de trazer de | + | Com a criação do ENIAC, Stanislaw Ulam viu a possibilidade de trazer de volta as técnicas de amostragem estastísticas e discutiu a idéia com John von Neumann, consultor em Aberdeen e Los Alamos. Ao ver a relevância da sugestão feita por Ulam, Neumann enviou uma carta às autoridades explicando uma possível aproximação estatística para o contorno do problema da difusão dos nêutrons em materiais físseis, encontrado durante a construção da bomba atômica. |
Nesta carta, Neumman relacionou o problema de difusão dos nêutrons a uma partida de Paciência e relacionou também uma rodada aleatória das cartas a números aleatórios necessários para se tomar decisões ao longo do caminho, no caso do problema em questão. Por isso a necessidade de se ter uma fonte de números aleatórios distribuídos de forma não uniforme. | Nesta carta, Neumman relacionou o problema de difusão dos nêutrons a uma partida de Paciência e relacionou também uma rodada aleatória das cartas a números aleatórios necessários para se tomar decisões ao longo do caminho, no caso do problema em questão. Por isso a necessidade de se ter uma fonte de números aleatórios distribuídos de forma não uniforme. |
Edição de 13h58min de 27 de outubro de 2010
Exemplo de comentário. Usar para colocar novas referências usadas, caso necessário.
Tabela de conteúdo |
Introdução
Uma simulação é uma imitação de uma operação ou sistema do mundo real em função do tempo. Uma simulação envolve gerar e observar uma história artificial do sistema estudado podendo assim traçar diversas conclusões sobre a operação do sistema no mundo real (BANKS et al.,2005, p.3).
Para tal estudo, é necessário fazer “suposições” sobre o sistema a ser estudado. Tais “suposições” são normalmente feitas através de relações lógicas ou matemáticas, sendo estas chamadas de modelos. Para casos onde o modelo é simples, é possível utilizar métodos analíticos para se determinar a informação “exata” que se precisa, porém casos no mundo real costumam ser complexos demais para se obter uma solução analítica e, portanto, utiliza-se uma simulação realizada em computador. Em uma simulação computacional avalia-se um modelo numericamente e os dados obtidos são utilizados para “estimar” características do sistema (LAW e KELTON, 2000).
Simulação torna-se uma ferramenta apropriada para modificar e estudar interações internas dentro de um sistema muito complexo permitindo prever alterações que ocorreriam no mundo real. Simulação ainda pode ser utilizada como apoio pedagógico para reforçar metodologias de solução analítica (BANKS et. al, 2005, p.4).
Além disso, diversos sistemas modernos (projeto e análise de fábricas, determinação de requisitos de hardware, protocolos para redes de comunicação, projeto e operação de sistemas de transporte como aeroportos, rodovias, portos e metrôs, etc.) são complexos demais, logo suas interações internas podem ser tratadas apenas por via de simulações (BANKS et al., 2005, p.4).
Sistemas e Modelos de Simulação
De acordo com Schmidt e Taylor (apud LAW e KELTON, 2000) um 'sistema' é uma coleção de entidades que agem juntas e interagem para um mesmo fim lógico. Já que um sistema é o conjunto de variáveis que descrevem o sistema em um determinado instante.
O sistema pode ainda ser classificado entre discreto e contínuo. Um sistema discreto é aquele cujas variáveis mudam instantaneamente em certos tempos, enquanto em um sistema contínuo o estados das variáveis se altera continuamente. Um sistema dificilmente será totalmente discreto ou totalmente contínuo, mas é possível realizar tal classificação de acordo com o tipo de mudança predominante (LAW e KELTON, 2000).
Para se simular o sistema desejado é necessário criar um modelo de tal sistema. Um modelo é a representação de um sistema com o propósito de estudar o sistema. Para a maioria dos estudos, é necessário apenas considerar os aspectos do sistema que afetam o problema sob investigação (BANKS,2005,p. 12). Modelos ainda podem ser classificados entre matemáticos ou físicos. Modelos matemáticos utilizam notação matemática representando as relações lógicas e qualitativas do sistema. Modelos de simulação são um tipo específico de modelo de sistema.
Tais modelos de simulação ainda podem ser classificados como estáticos ou dinâmicos, determinísticos ou estocásticos. Os modelos de simulação estáticos representam o sistema em um ponto específico no tempo onde a decorrência do tempo não é relevante. Já os modelos de simulação dinâmicos representam sistemas que evoluem com o tempo. Modelos de simulação que não contém variáveis randômicas são chamados de modelos determinísticos, enquanto que modelos estocásticos possuem uma ou mais variáveis aleatórias (LAW e KELTON, 2000).
Proposta
Apresentação didática do Método de Monte Carlo, seus aspectos históricos e aplicações, discutindo a essência do método num ambiente computacional, que é a geração de números pseudo aleatórios e suas limitações. Para tanto será desenvolvido um software de apoio, exemplificando o uso do método em algumas áreas, assim como um pequeno modelo de simulação. Os softwares abordarão o cálculo do pi através de uma circunferência desenhada e através da agulha de Buffon, que será apresentada mais a frente nesta monografia.
Justificativa
O Método de Monte Carlo é utilizado em diversas áreas do conhecimento, desde a própria informática, através da qual o método foi desenvolvido, até a administração. Entretanto, o método é normalmente usado puramente como uma ferramenta, não havendo uma preocupação de entendê-lo.
Considerando importante não apenas utilizar uma ferramenta, mas também entender seus fundamentos, é necessária uma abordagem didática do assunto. É a isto que este trabalho se propõe, expor didaticamente os fundamentos do Método de Monte Carlo para que as pessoas que a utilizam como ferramenta possam entender um pouco mais de seus princípios.
Objetivos
O objetivo geral deste trabalho é a apresentação didática do Método de Monte Carlo. Para tal, foram definidos os seguintes objetivos específicos:
Estudo do Método de Monte Carlo no contexto de simulações;
Estudo dos problemas de cálculo do pi e agulha de Buffon;
Elaboração de material escrito sobre o Método;
Elaboração de softwares que ilustrem o Método.
Procedimentos
Elaborar melhor os procedimentos.
Os procedimentos para a elaboração do trabalho podem ser divididos em duas seções: os procedimentos para a elaboração da monografia e os procedimentos para a elaboração dos softwares.
Para a elaboração da monografia, os procedimentos metodológicos constituem-se de três etapas: Pesquisa bibliográfica;
Definição do sumário e;
Revisão bibliográfica.
Para a elaboração dos softwares, os seguintes procedimentos foram adotados: Levantamento de requisitos;
Projeto do programa em UML;
Programação e;
Testes.
Método de Monte Carlo
Segundo Prado (2009), o Método de Monte Carlo pode ser definido como “uma maneira de transformar um conjunto de números aleatórios em outro conjunto de variáveis , com a mesma distribuição da variável considerada.”
Para Machline (1985), dá-se o nome de Monte Carlo ao “método de simulação que consiste em gerar eventos aleatórios com dados”.
Nota-se que em ambos os conceitos estão presentes variáveis aleatórias, sendo este um ponto fundamental do Método. Trata-se de um método de várias aplicabilidades e que teve surgimento na década de 40, logo após a Segunda Guerra Mundial.
Aspectos Históricos
O método de Monte Carlo surgiu em meados dos anos 40, durante o projeto Manhattan da Segunda Guerra Mundial. Foi aplicado na pesquisa em fusão nuclear para construção da bomba atômica, mais especificamente, no estudo do comportamento dos nêutrons nas reações em cadeia em dispositivos de fissão.
Stanislaw Ulam foi um matemático americano que gostava de analisar, estatisticamente, situações cotidianas. Ao analisar, através de análise combinatória, a probabilidade de se ganhar uma partida de Paciência , perdeu muito tempo efetuando cálculos até perceber que seria mais produtivo realizar várias partidas e anotar os resultados, mas naquela época as técnicas de amostragem estatística tinham caído em desuso devido aos cálculos serem cansativos e volumosos.
Paralelamente a isso, um time de cientistas, engenheiros e técnicos trabalhava na construção do primeiro computador eletrônico – o ENIAC – na Universidade da Pensilvânia, na Filadélfia. Os mentores da equipe se inspiraram para a criação do computador elétrico ao ver filas e filas de mulheres fazendo contas em suas calculadoras de mesa. O computador eletrônico seria construído para lidar com tais processos.
Com a criação do ENIAC, Stanislaw Ulam viu a possibilidade de trazer de volta as técnicas de amostragem estastísticas e discutiu a idéia com John von Neumann, consultor em Aberdeen e Los Alamos. Ao ver a relevância da sugestão feita por Ulam, Neumann enviou uma carta às autoridades explicando uma possível aproximação estatística para o contorno do problema da difusão dos nêutrons em materiais físseis, encontrado durante a construção da bomba atômica.
Nesta carta, Neumman relacionou o problema de difusão dos nêutrons a uma partida de Paciência e relacionou também uma rodada aleatória das cartas a números aleatórios necessários para se tomar decisões ao longo do caminho, no caso do problema em questão. Por isso a necessidade de se ter uma fonte de números aleatórios distribuídos de forma não uniforme.
Muitas pessoas se interessaram pelo método sugerido por Neumman em sua carta e foi então que Nicholas Metropolis sugeriu um nome: método de Monte Carlo.
O Método
Fazer. Possivelmente noções estatísticas utilizadas entrem aqui.
Aplicações
De acordo com Barros (2005), há duas aplicações básicas para o Método de Monte Carlo. A primeira delas diz respeito é para avaliar empiricamente uma distribuição estatística teórica. Esta é uma aplicação bastante utilizada no ensino estatístico. A segunda aplicação, e mais comum, é o uso do Método de Monte Carlo para estudar os efeitos que estão por trás de determinadas estatísticas.
Agulhade Buffon
O problema da agulha de Buffon data de 1777 e é um dos problemas mais antigos na área de probabilidade e geometria (ROSA et al., 2002). No problema da agulha de Buffon, observa-se que quando uma agulha de comprimento k é aleatoriamente lançada em direção a linhas paralelas com 2k de distância umas das outras, a razão entre o número de lançamentos pelo número de 'acertos' (número de vezes em que a agulha cruza uma linha) se aproxima do valor de PI. (BARROS, 2005). A ilustração abaixo mostra os conceitos do problema da agulha de Buffon:
Figura 01: Agulha de Buffon Fonte: Rosa et al. (2002).
Colocar a dedução matemática do porquê isto ocorre.
Cálculo do Pi
Editar na Wiki e complementar.
Limitações
Fazer.
Geração de Números Aleatórios
Para gerar números aleatórios, é necessário que o computador tenha uma fonte de números pseudo aleatórios com distribuição uniforme. Um algoritmo bastante utilizado é o chamado “dígitos de raiz quadrada” de von Neumann. Com ele, extrai-se a raiz quadrada de um número arbitrário com n dígitos, gerando outro número com 2n dígitos. O novo número gerado é formado pelos n dígitos centrais deste número gerado. Este processo é repetido diversas vezes, formando uma cadeia cujas propriedades foram intensamente estudadas. Em algum ponto desta cadeia, os números começam a repetir.
Depois de se obter um algoritmo de criação de números pseudo aleatórios com distribuição uniforme, é preciso transformá-los em uma distribuição não uniforme que represente a propriedade de interesse.
Geradores Lineares (Congretual)
Outros Geradores
Testando Geradores de Números Aleatórios
Implementação e Resultados
Conclusão
Referências
Lembrar de retirar as referências que não tenham sido utilizadas.
ANDRADE, Eduardo L.. Introdução à Pesquisa Operacional. 3. ed. LTC Editora, Rio de Janeiro, 2002.
BANKS, J.; CARSON II, J.S.; NELSON, B.L. Discrete event system simulation. 4.ed. New Jersey: Prentice Hall, 2005.
BARROS, Emílio A. C.. Aplicações de Simulação Monte Carlo e Bootstrap. 2005, 52 f. Monografia (Bacharelado em Estatística) – Departamento Acadêmico de Estatística, Universidade Estadual de Maringá, Maringá, 2005. Disponível em <http://www.des.uem.br/graduacao/Monografias/Monografia_Emilio.pdf>
ECKHARDT, Roger. Stan Ulam, John von Neumann, and The Monte Carlo Method. Los Alamos Science, Los Alamos, no. 15, p. 131-137, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-13.pdf >. Acesso em: 05 set. 2010.
FREITAS FILHO, Paulo José de. Introdução à modelagem e simulação de sistemas: com aplicações em Arena. 2. ed. Florianópolis: Visual Books, 2001.
LAW, A.M.; KELTON, W.D. Simulation modeling and analysis. 3. ed. Boston: McGraw-Hill, 2000.
MACHLINE, Claude, MOTTA, Ivan de Sá, SCHOEPS, Wolfgang, WEIL, Kurt E. Manual de Administração da Produção, Vol. II. Rio de Janeiro: Fundação Getúlio Vargas,1985.
METROPOLIS, Nicholas; Ulam, S. The Monte Carlo Method. Journal of the American Statistical Association, vol. 44, No. 247 (Sep. 1949), pp. 335-341.
______. The Beginning of The Monte Carlo Method. Los Alamos Science, Los Alamos, no. 15, p. 125-130, 1987. Disponível em: < http://library.lanl.gov/cgi-bin/getfile?15-12.pdf >. Acesso em: 05 set. 2010.
PRADO, Darci Santos do. Teoria das filas e da simulação. 4. ed. Belo Horizonte: Editora de Desenvolvimento Gerencial, 2009.
ROSA, Fernando H. F. P. da; COSTA, Matheus Moreira; TORTELLA, Tiago Luiz; JUNIOR, Vagner Aparecido. Método de Monte Carlo e Aproximações de PI. Disponível em <www.feferraz.net/files/lista/montecarlopi.pdf>
TAHA, Hamdy A. Operations research: an introduction . 6.ed. Upper Saddle River: Prentice Hall, c1997.