Algoritmo Las Vegas
Em computação, um algoritmo Las Vegas é um algoritmo randômico que sempre retorna resultados corretos; isto é, ele sempre produz o resultado correto ou informa sobre a falha. Em outras palavras, um algoritmo de Las Vegas não aposta com a corretude do resultado; ele aposta somente com os recursos usados para a computação. Um exemplo simples é o algoritmo randômico quicksort, onde o pivô é escolhido aleatoriamente, mas o resultado é sempre ordenado. A usual definição de um algoritmo Las Vegas inclui a restrição de que o tempo de execução esperado tem sempre que ser finito, quando a estimativa é calculada em um espaço de informações aleatórias, ou entropia, utilizados no algoritmo. Uma definição alternativa requer que um algoritmo Las Vegas sempre pare(que seja eficaz), mas ele pode dar como saída um símbolo que não faz parte do espaço de solução para indicar a falha em encontrar uma solução.[1]
Os algoritmos Las Vegas foram introduzidos por László Babai, em 1979, sob o contexto do problema do isomorfismo de grafos, como um dual dos Algoritmos Monte Carlo.[2][3][4] Os algoritmos Las Vegas podem ser utilizados em situações onde o número de soluções possíveis é relativamente limitada, e onde verificar a corretude de uma solução candidata é relativamente fácil, enquanto realmente calcular uma solução é complexo.
O nome refere-se à cidade de Las Vegas, Nevada, que é bem conhecida nos Estados Unidos como um ícone dos jogos de azar.
Classe de complexidade[editar | editar código-fonte]
A classe de complexidade dos problemas de decisão que possuem algoritmos Las Vegas com tempo de execução estimado polinomial é ZPP.
Acontece que o que está intimamente ligado com a forma que os algoritmos Las Vegas são, às vezes, construídos. Ou seja, a classe RP consiste em todos os problemas de decisão para os quais existe um algoritmo randômico de tempo polinomial onde a resposta correta é "não", mas é permitido estar errado, com uma certa probabilidade (limitada até 1), quando a resposta é "sim". Quando existe um algoritmo para um problema e o seu complemento (com as respostas "sim" e "não" trocadas), os dois algoritmos podem ser executados simultaneamente e repetidamente: execute cada um para um número constante de passos, revezando entre eles, até que um deles retorne uma resposta definitiva. Esta é a forma padrão para a construção de um algoritmo de Las Vegas que se espera ser executado em tempo polinomial. Note que, em geral, não há um limite superior do pior caso sobre o tempo de execução de um algoritmo de Las Vegas.
Relação com os Algoritmos Monte Carlo[editar | editar código-fonte]
Os algoritmos Las Vegas podem ser contrastados com os algoritmos Monte Carlo, em que os recursos são limitados, mas a resposta não é garantida de sempre ser correta. Via uma aplicação da Desigualdade de Markov, um algoritmo Las Vegas pode ser convertido em um algoritmo Monte Carlo via rescisão antecipada.
Ver também[editar | editar código-fonte]
- Aleatoriedade
- Atlantic City algoritmo
- O algoritmo Monte Carlo
Notes[editar | editar código-fonte]
Referências
- ↑ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. [S.l.]: Cambridge University Press. p. 16. ISBN 978-1-107-01392-6
- ↑ László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
- ↑ Leonid Levin, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103.
- ↑ Dan Grundy, Concepts and Calculation in Cryptography, University of Kent, Ph.D. thesis, 2008
Referências[editar | editar código-fonte]
- Algoritmos e Teoria da Computação Manual, CRC Press LLC, 1999, "algoritmo de Las Vegas", em Dicionário de Algoritmos e Estruturas de Dados [online], Paul E. Preto, ed. Dos EUA, o Instituto Nacional de Padrões e Tecnologia. 17 de julho de 2006. (acedido em Maio 09, 2009) Disponível em: [1]
