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 simple à 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, lancé deux fois sur les mêmes données, peut sortir 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 (en), 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. Dans de nombreux cas il y a un compromis entre le temps et l'erreur car l'on peut lancer plusieurs fois l'algorithme indépendamment pour réduire la probabilité d'erreur.

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. Dans ce cas, on cherche par exemple à 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 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. De façon plus générale, on peut considérer l'aléas comme une ressource, et essayer de minimiser son utilisation. Une méthode classique est la méthode des probabilités conditionnelles (en).

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)