Algorithme probabiliste
- Algorithme probabiliste
-
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.
|
Informatique théorique |
| Théorie du calcul |
|
| Logique, syntaxe et sémantique |
|
| Algorithmique, complexité et mathématiques discrètes |
|
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme probabiliste de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… … Wikipédia en Français
Algorithme de Grover — En informatique quantique, l´algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés en temps proportionnel à et avec un espace de… … Wikipédia en Français
Algorithme de Deutsch-Jozsa — L Algorithme de Deutsch Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998[1],[2]. Bien qu il ne soit pas d un grand intérêt… … Wikipédia en Français
Algorithme génétique — Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d obtenir une solution approchée à un problème d optimisation, lorsqu il n existe pas de méthode exacte (ou que la solution est inconnue) pour le… … Wikipédia en Français
Algorithme glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… … Wikipédia en Français
Algorithme — Ne pas confondre avec la notion d algorithme en sport Un algorithme est une suite finie et non ambiguë d’opérations ou d instructions permettant de résoudre un problème. Le mot algorithme vient du nom latinisé du mathématicien persan Al… … Wikipédia en Français
Algorithme diviser pour régner — Diviser pour régner (informatique) Pour les articles homonymes, voir Diviser pour régner. Diviser pour régner est une technique algorithmique consistant à diviser un problème de grande taille en plusieurs sous problèmes analogues. L étape de… … Wikipédia en Français
Algorithme De Shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… … Wikipédia en Français
Algorithme de shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… … Wikipédia en Français
Algorithme a estimation de distribution — Algorithme à estimation de distribution Les algorithmes à estimation de distribution résolvent des problèmes d optimisation en échantillonnant un modèle de distribution, dont les paramètres évoluent via des opérateurs de sélection. Ici, un AED à… … Wikipédia en Français
Portail de l’algorithmique
Portail des probabilités et des statistiques
