Algorithme de Las Vegas

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste. Plus précisément, c'est un algorithme qui, bien qu'utilisant de l'aléatoire, produit un résultat correct, donc qui produit exactement le même résultat qu'un algorithme qui n'utilise pas de probabilité du tout. Le hasard est ainsi restreint au contrôle interne du calcul et n'affecte en rien le résultat. L'algorithme de tri rapide aléatoire, ou Quicksort randomisé où les pivots sont choisis aléatoirement, est un exemple typique d'algorithme de Las Vegas. Le résultat est une liste triée comme l'aurait fait n'importe quel algorithme de tri. Par conséquent, quicksort randomisé rend un tableau parfaitement trié.

Quand le problème que l'algorithme résout a plusieurs solutions correctes, sur une même donnée, comme c'est le cas pour le tri d'un tableau qui possède des clés équivalentes, alors l'algorithme de Las Vegas peut retourner l'une ou l'autre de ces solutions, et il le fait de façon non prévisible.

Algorithme de Las Vegas, de Monte Carlo et d'Atlantic City[modifier | modifier le code]

On oppose et compare souvent les trois familles d'algorithmes probabilistes de Las Vegas, de Monte Carlo et d'Atlantic City (en) (trois villes connues pour leur casinos). Alors que les algorithmes de Las Vegas donnent (de façon probablement efficace) une réponse exacte à la question posée, les algorithmes de Monte-Carlo donnent de façon toujours efficace une valeur numérique approchée sise dans un intervalle de confiance et les algorithmes d'Atlantic City donnent de façon probablement efficace une réponse probablement juste (avec une chance sur cent millions de se tromper par exemple) à la question posée.

Dit autrement :

  • l'algorithme de Las Vegas s'arrête quand il a trouvé une réponse exacte ;
  • l'algorithme de Monte-Carlo répond dans un temps prévisible et court sans pour autant garantir une réponse toujours exacte ;
  • l'algorithme d'Atlantic-City est relativement rapide et donne une réponse exacte avec une bonne garantie de l'exactitude (voir tests de primalité probabilistes).

Notes et références[modifier | modifier le code]

  • 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. National Institute of Standards and Technology. 17 July 2006. (accessed May 09, 2009) Available from: [1]
  • (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995), 476 p. (ISBN 9780521474658), chap. 1.2 (« Introduction: Las Vegas and Monte Carlo »), p. 9-10


Voir aussi[modifier | modifier le code]