Algoritme de Las Vegas

Un algoritme tipo Las Vegas és un procediment de computació de caràcter aleatori (random) que no és aproximat: és dir, dona el resultat correcte o informa que ha fallat.

Característiques

Un algoritme d'este tipo no especula en el resultat, sino que determina els recursos a utilisar en la seua computació.

De la mateixa manera que el método de Montecarlo, la provabilitat de trobar una solució correcta aumenta en el temps amprat en obtindre-la i el número de mostrejos utilisat. Un algoritme tipo Las Vegas s'utilisa sobretot en problemes NP-complets, que serien intractables en métodos determinísticos.

Existix un risc de no trobar solució degut a que es fan eleccions de rutes aleatòries que poden no dur a cap lloc. L'objectiu és minimisar la provabilitat de no trobar la solució, prenent decisions aleatòries en inteligència, pero minimisant també el temps d'eixecució en aplicar-se sobre l'espai d'informació aleatòria.

La classe de complexitat dels problemes de decisió d'estos algoritmes en eixecució polinòmica és ZPP.

$Z P P = R P * n o - R P$

El seu esquema d'implementació s'assembla al dels algoritmes de Montecarlo, pero es diferencien d'ells en que inclouen una variable booleana per a saber si s'ha trobat la solució correcta.

Visió general

En informàtica, un algoritme de Las Vegas és un algoritme aleatori que sempre dona resultats correctes, és dir, que sempre produïx el resultat correcte o informa sobre el fallo (és dir, que no s'ha trobat la solució buscada). No obstant, el temps d'eixecució d'un algoritme de Las Vegas diferix depenent de l'entrada. La seua definició usual inclou la restricció de que el temps d'eixecució esperat siga finito, a on l'expectativa es porta a terme sobre l'espai d'informació aleatòria, o entropía, usada en l'algoritme. Una definició alternativa requerix que un algoritme de Las Vegas sempre termine (perque es tracta d'un método efectiu), pero pot donar com resultat un símbol que no forma part de l'espai de la solució, per a indicar el fallo en trobar-la.^[1] La naturalea dels algoritmes de Las Vegas els fa adequats en situacions a on el número de possibles solucions és llimitat, i a on verificar la correcció d'una solució candidata és relativament fàcil, mentres que trobar una solució és complex.

Els métodos de busca sistemàtica per a problemes computacionalment complexos, com algunes variants del algoritme de Davis-Putnam per a la satisfacibilidad proposicional (SAT), també utilisen decisions no determinista i, per lo tant, poden considerar-se algoritmes de Las Vegas.^[2]

Vore també

Referències

↑ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography, Cambridge University Press, p. 16. ISBN 978-1-107-01392-6.
↑ Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).

Bibliografia

Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999.
"Las Vegas algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. Institut Nacional d'Estàndarts i Tecnologia. 17 de juliol de 2006. (Consultat el 9 de maig de 2009). Disponible en: [1]

Referències

Este artícul conté una traducció derivada de «Algoritmo de Las Vegas» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[Galbraith201222-1] Steven D. Galbraith (2012). Mathematics of Public Key Cryptography, Cambridge University Press, p. 16. ISBN 978-1-107-01392-6.

[2] Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).

[1]

[2]