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
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
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.
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.
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].
↑Karel De Leeuw, Edward F. Moore, Claude E. Shannon et Norman Shapiro, « Computability by probabilistic machines », Automata studies, vol. 34, , p. 183-198
