Algorithme de Monte-Carlo
Pour les articles homonymes, voir Monte-Carlo (homonymie).
Ne doit pas être confondu avec méthode de Monte-Carlo.
En algorithmique, un algorithme de Monte-Carlo est un algorithme randomisé dont le temps d'exécution est déterministe, mais dont le résultat peut être incorrect avec une certaine probabilité (généralement minime). Autrement dit un algorithme de Monte-Carlo est un algorithme qui utilise une source de hasard, dont le temps de calcul est connu dès le départ (pas de surprise sur la durée du calcul), cependant dont la sortie peut ne pas être la réponse au problème posé, mais c'est un cas très rare. L’intérêt de tels algorithmes est d'avoir une probabilité d'échec faible et d'être rapide.
Deux autres types d'algorithmes probabilistes sont la famille des algorithmes de Las Vegas et la famille des algorithmes d'Atlantic City. Les algorithmes de Las Vegas prennent un temps d'exécution aléatoire, mais produisent toujours une réponse correcte. Les algorithmes d'Atlantic City donnent une réponse probablement correcte dans un temps d'exécution probablement rapide. Un algorithme de Monte-Carlo peut être transformé en un algorithme de Las Vegas quand il existe une procédure capable de vérifier la correction du résultat. En effet, il suffit d'exécuter l'algorithme de Monte-Carlo jusqu'à lui faire produire une réponse correcte.
Accessoirement, le qualificatif Monte-Carlo fait référence à la Principauté de Monaco et à son célèbre casino appelé Casino de Monte-Carlo, haut lieu des jeux de hasard.
Définition et intérêt[modifier | modifier le code]
Un algorithme de Monte-Carlo a deux caractéristiques : primo il est randomisé, c'est-à-dire qu'il utilise un aléa au cours de son calcul, secundo son temps d'exécution est déterministe. Sa nature aléatoire se manifeste dans son résultat qui peut être incorrect avec une certaine probabilité (généralement minime), mais qui peut-être quantifiée rigoureusement[1].
Exemple[modifier | modifier le code]
Le test de primalité de Solovay-Strassen est un test qui détermine si un nombre donné est premier. Il répond toujours vrai pour les nombres premiers, tandis que pour les nombres composés (c'est-à-dire non premiers), il répond faux avec une probabilité d'au moins ½ et vrai avec une probabilité d'au plus ½. Ainsi, les réponses faux de l'algorithme sont correctes, alors que les réponses vrai sont aléatoires ; autrement dit l'algorithme est biaisé vers le faux.
Biais ou non[modifier | modifier le code]
Alors que la réponse renvoyée par un algorithme déterministe est toujours exacte, ce n'est pas le cas pour les algorithmes de Monte-Carlo qui peuvent ne l'être que dans le cas d'un biais. Supposons qu'il s'agisse de résoudre un problème de décision, ces algorithmes sont dits alors soit non biaisés, soit biaisés vers le faux, soit biaisés vers le vrai. Un algorithme de Monte-Carlo biaisé vers le faux est toujours correct quand il retourne faux ; un algorithme biaisé vers le vrai est toujours correct quand il retourne vrai. Quant aux algorithmes de Monte-Carlo non biaisés, leur réponse (vrai ou faux) sera soit incorrecte, soit correcte avec une certaine probabilité bornée.
En anglais, on parle de one-sided error et two-sided error[1].
Amplification[modifier | modifier le code]
Étant donné un algorithme de Monte-Carlo biaisé, sa probabilité d'échec peut être réduite (et sa probabilité de succès augmentée) en l'exécutant k fois[1]. Considérons à nouveau l'algorithme de Solovay-Strassen qui est biaisé vers le faux. On peut l'exécuter plusieurs fois lui faisant retourner vrai s'il répond vrai lors des k étapes de l'itération et faux autrement. Ainsi, si le nombre est premier, alors la réponse est vraiment correcte, et si le nombre est composé, alors la réponse est correcte, avec une probabilité renforcée au moins 1−(1−½)k = 1−2−k.
Pour les algorithmes de décision de Monte-Carlo non biaisés, la probabilité d'erreur peut aussi être réduite en exécutant l'algorithme k fois et en retournant la réponse qui correspond à la majorité.
Classes de complexité[modifier | modifier le code]
La classe de complexité BPP (pour bounded-error probabilistic polynomial time) décrit les problèmes de décision qui peuvent être résolus par un algorithme de Monte-Carlo non biaisé en temps polynomial, avec une probabilité bornée d'erreur[2].
La classe de complexité RP (pour randomized polynomial time) décrit les problèmes qui peuvent être résolus avec une probabilité bornée d'erreur par un algorithme de Monte-Carlo biaisé : si la bonne réponse est faux, l'algorithme le dit, mais il peut répondre faux dans des cas où la réponse correcte est vrai.
En revanche, la classe de complexité ZPP (pour zero-error probabilistic polynomial time) décrit les problèmes solubles en temps polynomial par un algorithme de Las Vegas. On a ZPP ⊆ RP ⊆ BPP, mais on ne sait pas si ces classes de complexité sont mutuellement distinctes. Autrement dit, les algorithmes de Monte-Carlo peuvent avoir de meilleures performances que les algorithmes de Las Vegas, mais cela n'a pas été démontré.
Une autre classe de complexité est PP (pour polynomial probabilistic) ; elle décrit les problèmes de décision résolus en temps polynomial par un algorithme de Monte-Carlo qui donne un résultat plus précis qu'un simple tirage à pile ou face, mais dont la probabilité d'erreur ne peut être ramenée significativement en dessous de ½.
Exemples[modifier | modifier le code]
En théorie algorithmique des nombres[modifier | modifier le code]
Des algorithmes Monte-Carlo notables comprennent le test de primalité de Solovay-Strassen et le test de primalité de Miller-Rabin, et certaines variantes rapides de l'algorithme de Schreier-Sims dans la théorie computationnelle des groupes.
En théorie des graphes[modifier | modifier le code]
Problème du voyageur de commerce[modifier | modifier le code]
La résolution du problème du voyageur de commerce est difficile, du fait de la complexité du problème, l'emploi de méthodes d'optimisation probabilistes peut s'avérer efficace pour obtenir une approximation de la meilleure solution, en un temps plus court que pour des méthodes déterministes.
Coupe minimum[modifier | modifier le code]
L'algorithme de Karger est un algorithme de Monte-Carlo pour le problème de la coupe minimum[3],[1].
Notes et références[modifier | modifier le code]
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Monte Carlo algorithm » (voir la liste des auteurs).
- (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, (réimpr. 1997, 2000), 1re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 1 (« Introduction »), p. 7-9
- (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 7 (« Randomized Computation »)
- (en) David R. Karger et Clifford Stein, « A new approach to the minimum cut problem », Journal of the ACM, vol. 43, no 4, , p. 601 (DOI 10.1145/234533.234534, lire en ligne)
Bibliographie[modifier | modifier le code]
- (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, New York, Cambridge University Press, , 476 p. (ISBN 978-0-521-47465-8)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein (trad. de l'anglais), Algorithmique : Cours avec 957 exercices et 158 problèmes, Dunod, , 3e éd. (1re éd. 1990), 1188 p. (ISBN 978-2-10-054526-1, BNF 42363501)
- (en) Kenneth A Berman et Jerome L. Paul, Algorithms : Sequential, Parallel, and Distributed, Boston, Course Technology, , 962 p. (ISBN 978-0-534-42057-4), « Ch 24. Probabilistic and Randomized Algorithms »
