Algoritmo de Monte Carlo - Monte Carlo algorithm

Na computação , um algoritmo de Monte Carlo é um algoritmo aleatório cuja saída pode estar incorreta com uma certa probabilidade (normalmente pequena) . Dois exemplos de tais algoritmos são o algoritmo de Karger-Stein e o algoritmo de Monte Carlo para o conjunto mínimo de arco de feedback .

O nome se refere ao grande cassino do Principado de Mônaco em Monte Carlo , que é conhecido em todo o mundo como um ícone do jogo. O termo "Monte Carlo" foi introduzido pela primeira vez em 1947 por Nicholas Metropolis .

Os algoritmos de Las Vegas são uma dupla dos algoritmos de Monte Carlo que nunca retornam uma resposta incorreta - no entanto, eles podem fazer escolhas aleatórias como parte de seu trabalho. Como resultado, o tempo gasto pode variar entre as execuções, mesmo com a mesma entrada.

Se houver um procedimento para verificar se a resposta dada por um algoritmo de Monte Carlo está correta, e a probabilidade de uma resposta correta for limitada acima de zero, então, com a probabilidade um executando o algoritmo repetidamente enquanto testa as respostas, eventualmente dará uma resposta correta. Se este processo é um algoritmo de Las Vegas depende se a parada com probabilidade um é considerada para satisfazer a definição.

Erro unilateral vs erro bilateral

Embora sempre se espere que a resposta retornada por um algoritmo determinístico seja correta, esse não é o caso dos algoritmos de Monte Carlo. Para problemas de decisão , esses algoritmos são geralmente classificados como com polarização falsa ou com polarização verdadeira . Um algoritmo de Monte Carlo com polarização falsa está sempre correto quando retorna falso ; um algoritmo com tendência verdadeira está sempre correto quando retorna verdadeiro . Enquanto isso descreve algoritmos com erros unilaterais , outros podem não ter viés; diz-se que esses erros têm dois lados . A resposta que eles fornecem ( verdadeira ou falsa ) será incorreta ou correta, com alguma probabilidade limitada.

Por exemplo, o teste de primalidade de Solovay-Strassen é usado para determinar se um determinado número é um número primo . Ele sempre responde verdadeiro para entradas de números primos; para entradas compostas, responde falso com probabilidade pelo menos 1 ⁄ 2 e verdadeiro com probabilidade menor que 1 ⁄ 2 . Assim, as respostas falsas do algoritmo são certamente corretas, ao passo que as respostas verdadeiras permanecem incertas; este é considerado um algoritmo de falso enviesamento correto 1 ⁄ 2 .

Amplificação

Para um algoritmo de Monte Carlo com erros unilaterais, a probabilidade de falha pode ser reduzida (e a probabilidade de sucesso ampliada) executando o algoritmo k vezes. Considere novamente o algoritmo de Solovay-Strassen, que é falso-polarizado 1 ⁄ 2- correto . Pode-se executar esse algoritmo várias vezes, retornando uma resposta falsa se atingir uma resposta falsa em k iterações e, de outra forma, retornando verdadeiro . Portanto, se o número for primo, a resposta será sempre correta e, se o número for composto, a resposta será correta com probabilidade de pelo menos 1− (1− 1 ⁄ 2 ) ^k  = 1−2 ^−k .

Para algoritmos de decisão de Monte Carlo com erro bilateral, a probabilidade de falha pode ser novamente reduzida executando o algoritmo k vezes e retornando a função majoritária das respostas.

Classes de complexidade

A classe de complexidade BPP descreve problemas de decisão que podem ser resolvidos por algoritmos de Monte Carlo em tempo polinomial com uma probabilidade limitada de erros bilaterais, e a classe de complexidade RP descreve problemas que podem ser resolvidos por um algoritmo de Monte Carlo com uma probabilidade limitada de um - erro lateral: se a resposta correta for falsa , o algoritmo sempre diz isso, mas pode responder falsa incorretamente em alguns casos em que a resposta correta é verdadeira . Em contraste, a classe de complexidade ZPP descreve problemas solucionáveis ​​por algoritmos de Las Vegas de tempo esperado polinomial. ZPP ⊆ RP ⊆ BPP , mas não se sabe se alguma dessas classes de complexidade é distinta uma da outra; ou seja, os algoritmos de Monte Carlo podem ter mais poder computacional do que os algoritmos de Las Vegas, mas isso não foi provado. Outra classe de complexidade, PP , descreve problemas de decisão com um algoritmo de Monte Carlo em tempo polinomial que é mais preciso do que jogar uma moeda, mas onde a probabilidade de erro não pode necessariamente ser limitada a 1 ⁄ 2 .

Aplicações na teoria computacional dos números

Algoritmos de Monte Carlo bem conhecidos incluem o teste de primalidade Solovay – Strassen, o teste de primalidade Baillie – PSW , o teste de primalidade Miller – Rabin e certas variantes rápidas do algoritmo Schreier – Sims na teoria de grupo computacional .

Veja também

• Métodos de Monte Carlo , algoritmos usados ​​em simulação física e estatísticas computacionais baseadas na obtenção de amostras aleatórias
• Algoritmo de Atlantic City
• Algoritmo de las vegas

Referências

Citações

Origens