Algorithme probabiliste

Cet article est une ébauche concernant l’informatique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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.

• Portail des mathématiques
• Portail de l’informatique