Algorithme probabiliste

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].

Ne doit pas être confondu avec Complexité en moyenne des algorithmes.

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

Définition

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

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

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 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 Monte-Carlo le compromis sur la complexité du calcul des algorithmes de Las Vegas.

Modèle théorique associé et complexité

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

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.

Les structures de données probabilistes, comme le filtre de Bloom, sont utilisées en pratique car plus efficaces pour certaines situations réelles.

Les stratégies probabilistes permettent d'avoir des stratégies efficaces en moyenne pour problème algorithmique en ligne. Une méthode générale est la méthode des poids multiplicatifs.[pas clair]

Dérandomisation

On parle de dérandomisation, lorsqu'on transforme un algorithme probabiliste en un algorithme déterministe. Une première étape lorsqu'on essaye de concevoir un algorithme pour un problème, peut être de concevoir d'abord un algorithme probabiliste, car cette étape est souvent plus facile. Ensuite, on peut essayer d'obtenir un algorithme non probabiliste avec une complexité semblable en transformant l'algorithme probabiliste. Ce processus de conception 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 on obtiendra un algorithme déterministe, sinon on réduira au moins le nombre de bits aléatoires utilisés.

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

Histoire

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].

Notes et références
  1. (en) Ranjeev Motwani et Prabhakar Raghavan, Randomized algorithms, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995), 476 p. (ISBN 978-0-521-47465-8).
  2. (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
  3. Arora et Barak 2009.
  4. (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), « Introduction: Computation model and complexity classes (Notes) »
  5. Karel De Leeuw, Edward F. Moore, Claude E. Shannon et Norman Shapiro, « Computability by probabilistic machines », Automata studies, vol. 34,‎ , p. 183-198

Annexes

Bibliographie

Liens externes
  • Portail des probabilités et de la statistique
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.