Algorithme probabiliste

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Exemple introductif[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 le bon résultat, mais au bout d'un temps qui peut devenir très grand avec faible probabilité. On peut transformer un algorithme de Las Vegas en algorithme de Monte-Carlo en interrompant les calculs après un temps fixé à l'avance.

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)