Algorithme de Monte Carlo - Monte Carlo algorithm

En informatique , un algorithme de Monte Carlo est un algorithme aléatoire dont la sortie peut être incorrecte avec une certaine probabilité (généralement faible) . Deux exemples de tels algorithmes sont l'algorithme de Karger-Stein et l' algorithme de Monte Carlo pour l' ensemble d'arc de rétroaction minimum .

Le nom fait référence au grand casino de la Principauté de Monaco à Monte Carlo , qui est bien connu dans le monde entier comme une icône du jeu. Le terme « Monte Carlo » a été introduit pour la première fois en 1947 par Nicholas Metropolis .

Les algorithmes de Las Vegas sont un double des algorithmes de Monte Carlo qui ne renvoient jamais de réponse incorrecte. Cependant, ils peuvent faire des choix aléatoires dans le cadre de leur travail. Par conséquent, le temps nécessaire peut varier entre les exécutions, même avec la même entrée.

S'il existe une procédure pour vérifier si la réponse donnée par un algorithme de Monte Carlo est correcte et que la probabilité d'une réponse correcte est limitée au-dessus de zéro, alors avec une probabilité d'exécuter l'algorithme à plusieurs reprises tout en testant les réponses donnera éventuellement une réponse correcte. Que ce processus soit un algorithme de Las Vegas dépend de la question de savoir si l'arrêt avec probabilité est considéré comme satisfaisant à la définition.

Erreur unilatérale ou bilatérale

Alors que la réponse renvoyée par un algorithme déterministe est toujours censée être correcte, ce n'est pas le cas pour les algorithmes de Monte Carlo. Pour les problèmes de décision , ces algorithmes sont généralement classés comme faux ou vrais . Un algorithme de Monte Carlo faussement biaisé est toujours correct lorsqu'il renvoie false ; un algorithme à vrai biais est toujours correct lorsqu'il renvoie true . Bien que cela décrive des algorithmes avec des erreurs unilatérales , d'autres peuvent n'avoir aucun biais ; ceux-ci sont dits avoir des erreurs bilatérales . La réponse qu'ils fournissent ( vraie ou fausse ) sera incorrecte ou correcte, avec une probabilité limitée.

Par exemple, le test de primalité de Solovay-Strassen est utilisé pour déterminer si un nombre donné est un nombre premier . Il répond toujours vrai pour les entrées de nombres premiers ; pour les entrées composites, il répond à faux avec une probabilité d' au moins 1 / deux et vrai , avec une probabilité inférieure à 1 / deux . Ainsi, les fausses réponses de l'algorithme sont certaines d'être correctes, alors que les vraies réponses restent incertaines ; on dit qu'il s'agit d'un algorithme de faux biais 1 . 2 -correct .

Amplification

Pour un algorithme de Monte Carlo avec des erreurs unilatérales, la probabilité d'échec peut être réduite (et la probabilité de succès amplifiée) en exécutant l'algorithme k fois. Considérons à nouveau l'algorithme de Solovay-Strassen qui est 12 -correct faussement biaisé . On peut exécuter cet algorithme plusieurs fois en retournant une fausse réponse s'il atteint une fausse réponse en k itérations, et sinon en retournant true . Ainsi, si le nombre est premier alors la réponse est toujours correcte, et si le nombre est composé alors la réponse est correcte avec une probabilité d'au moins 1−(1− 12 ) k  = 1−2 −k .

Pour les algorithmes de décision de Monte Carlo avec erreur bilatérale, la probabilité d'échec peut à nouveau être réduite en exécutant l'algorithme k fois et en renvoyant la fonction majoritaire des réponses.

Classes de complexité

La classe de complexité BPP décrit des problèmes de décision qui peuvent être résolus par des algorithmes de Monte Carlo en temps polynomial avec une probabilité bornée d'erreurs bilatérales, et la classe de complexité RP décrit des problèmes qui peuvent être résolus par un algorithme de Monte Carlo avec une probabilité bornée de un. erreur recto-verso : si la bonne réponse est false , l'algorithme le dit toujours, mais il peut répondre faux de manière incorrecte dans certains cas où la bonne réponse est true . En revanche, la classe de complexité ZPP décrit des problèmes pouvant être résolus par des algorithmes polynomiaux à temps prévu de Las Vegas. ZPP RP BPP , mais on ne sait pas si l'une de ces classes de complexité est distincte l'une de l'autre ; c'est-à-dire que les algorithmes de Monte Carlo peuvent avoir plus de puissance de calcul que les algorithmes de Las Vegas, mais cela n'a pas été prouvé. Une autre classe de complexité, PP , décrit des problèmes de décision avec un algorithme de Monte Carlo en temps polynomial qui est plus précis que de lancer une pièce mais où la probabilité d'erreur ne peut pas nécessairement être limitée à 12 .

Applications en théorie des nombres computationnelle

Bien connu Monte Carlo algorithmes incluent le test de primalité Solovay-Strassen, le test de primalité Baillie-PSW , le test de Miller-Rabin primalité , et certaines variantes rapide de l' algorithme Schreier-Sims dans la théorie des groupes de calcul .

Voir également

Les références

Citations

Sources