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 informatique, un algorithme probabiliste, parfois dit aussi randomisé, est un algorithme dont le déroulement fait appel à des données tirées au hasard.

Exemples introductifs[modifier | modifier le code]

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 et Las Vegas[modifier | modifier le code]

Parmi les algorithmes probabilistes, on distingue généralement ceux dits de Monte-Carlo et de Las Vegas. Un algorithme de Monte-Carlo peut, avec faible probabilité, donner une réponse incorrecte ; tandis qu'un algorithme de Las Vegas donne toujours un bon résultat, mais au bout d'un temps qui peut devenir très grand ou infini (au cas ou l'algorithme diverge) avec faible probabilité.

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

Exemples[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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

  1. (Arora Barak 2009)