Algorithme probabiliste

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Complexité en moyenne des algorithmes.

En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].

Les algorithmes probabilistes sont étudiés car ils sont souvent plus simples à analyser et très souvent plus rapides[1].

Définition[modifier | modifier le code]

Un algorithme est dit probabiliste si son comportement dépend à la fois des données du problème et de valeurs produites par un générateur de nombres aléatoires.

En particulier un même algorithme probabiliste, exécuté deux fois sur le même jeu de données, peut rendre deux réponses différentes du fait de valeurs aléatoires différentes.

Distinction entre les algorithmes Monte Carlo, Las Vegas et Atlantic City[modifier | modifier le code]

Parmi les algorithmes probabilistes, on distingue généralement ceux dits de Monte-Carlo, ceux dits de Las Vegas[2] et ceux dits d'Atlantic City (en)

Un algorithme de Monte-Carlo peut donner une réponse approchée dans un certain intervalle de confiance. Dans ce cas on cherche à avoir un petit intervalle de confiance tout en conservant une complexité en temps faible, par exemple polynomiale en la taille de l'entrée.

Un algorithme de Las Vegas donne toujours un résultat exact, mais le temps de calcul est petit avec une très forte probabilité. En particulier pour certains tirages aléatoires, l'algorithme peut soit prendre un temps très long, soit pire encore ne pas se terminer, mais ces deux cas n'arrivent qu'avec un probabilité nulle ou dérisoire. Ce qu'on cherche c'est montrer que le temps de calcul attendu en moyenne et/ou en probabilité est polynomial.

Un algorithme d'Atlantic City (en) donne une réponse avec une très forte probabilité sur l'exactitude de la réponse pour un temps de calcul faible en moyenne probabiliste. En gros, il ajoute au compromis sur l'exactitude de la réponse des algorithmes de Monté-Carlo le compromis sur la complexité du calcul des algorithmes de Las Vegas.

Modèle théorique associé et complexité[modifier | modifier le code]

Un modèle de calcul associé aux algorithmes probabilistes est la machine de Turing probabiliste. Ces machines permettent de définir des classes de complexité probabilistes, notamment BPP, RP et ZPP[3].

Utilisations[modifier | modifier le code]

Certains algorithmes probabilistes sont utilisés pour leur simplicité et leur efficacité, même lorsque l'on connaît un algorithme déterministe efficace, c'est le cas du test de primalité de Miller-Rabin et de l'algorithme de Karger pour le problème de la coupe minimum par exemple. Certains sont étudiés et enseignés car ils sont plus faciles à analyser, par exemple le tri rapide avec un pivot choisi aléatoirement et uniformément.

Enfin dans certains cas on ne connaît pas d'algorithme déterministe aussi efficace que l'algorithme probabiliste. C'est un problème ouvert de savoir par exemple si les algorithmes en temps polynomiaux avec randomisation sont plus efficaces ou pas (i.e. est-ce que BPP=P). Un exemple est la complexité de la communication où certains protocoles randomisés donnent de bien meilleurs résultats que leurs équivalents déterministes.

Dérandomisation[modifier | modifier le code]

On parle de dérandomisation, lorsqu'on transforme un algorithme probabiliste en un algorithme déterministe. Une première étape lorsque qu'on essaye de créer un algorithme pour un problème, peut être de créer un algorithme probabiliste, car cela est parfois plus facile. Ensuite, on peut essayer d'obtenir un algorithme déterministe avec une complexité semblable en transformant l'algorithme précédent. Ce processus est appelé dérandomisation.

De façon plus générale, on peut considérer l'aléa comme une ressource (au même titre que le temps ou l'espace), et essayer de minimiser son utilisation (au mieux d'obtenir un algorithme déterministe, et sinon de réduire le nombre bits aléatoires nécessaire).

Une méthode classique de dérandomisation est la méthode des probabilités conditionnelles (en).

Histoire[modifier | modifier le code]

On peut considérer que l'idée de faire des calculs basés sur du hasard a pour origine les méthodes de Monte-Carlo en analyse numérique et en statistiques[4]. Le principe de machine de Turing probabiliste date de 1955[5],[4].

Bibliographie[modifier | modifier le code]

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

  1. Ranjeev Motwani et Prabhakar Raghavan, Randomized algorithms, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995) (ISBN 0-521-47465-5).
  2. Ranjeev Motwani et Prabhakar Raghavan, « Introduction: Las Vegas and Monte Carlo », dans Randomized algorithms, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995) (ISBN 0-521-47465-5), chap. 1.2, p. 9-10
  3. (Arora Barak 2009)
  4. a et b Ranjeev Motwani et Prabhakar Raghavan, « Introduction: Computation model and complexity classes (Notes) », dans Randomized algorithms, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995) (ISBN 0-521-47465-5)
  5. Karel De Leeuw, Edward F. Moore, Claude E. Shannon et Norman Shapiro, « Computability by probabilistic machines », Automata studies, vol. 34,‎ , p. 183-198