Algorithme 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

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

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

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

É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é

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

En théorie algorithmique des nombres

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

Problème du voyageur de commerce

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

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

(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).

↑ ^{a b c et d} (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re é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, 2009 (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, n^o 4,‎ 1996, p. 601 (DOI 10.1145/234533.234534, lire en ligne)

Bibliographie

(en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, New York, Cambridge University Press, 1995, 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, 2010, 3^e éd. (1^re é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, 2005, 962 p. (ISBN 978-0-534-42057-4), « Ch 24. Probabilistic and Randomized Algorithms »

Voir aussi

Portail de l'informatique théorique

[RA-1] {a b c et d} (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 1 (« Introduction »), p. 7-9

[2] (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7 (« Randomized Computation »)

[3] (en) David R. Karger et Clifford Stein, « A new approach to the minimum cut problem », Journal of the ACM, vol. 43, n^o 4,‎ 1996, p. 601 (DOI 10.1145/234533.234534, lire en ligne)

[1]

[2]

[3]