EPFL Logo
fr|en
Se Connecter
Concept

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. 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. 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 1⁄2 et vrai avec une probabilité d'au plus 1⁄2.

Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (1)
AR-327: Introduction to computational architecture
This course introduces the students to text programming practice in 3D modeling (Rhinoceros3D). The main objective of the course is to develop a computational mindset to maximize the use of efficient
Séances de cours associées (16)
Parenthèse mathématique sur les groupes et le théorème de lagrange
Explore les cosets dans les groupes commutatifs, le théorème de Lagrange et la factorisation entière.
Factorisation des polynômes : complexité et algorithmes
Plonge dans la complexité de l'affacturage des polynômes et ses implications pour la sécurité.
Multiplication matricielle : diviser pour mieux régner
Explore l'algorithme Divide-and-Conquer pour la multiplication matricielle, y compris la méthode de Strassen et son importance dans l'optimisation de la complexité du temps.
Afficher plus
Publications associées (46)
Afficher plus
Personnes associées (7)
Concepts associés (3)
Algorithme probabiliste
En algorithmique, un algorithme probabiliste, ou algorithme randomisé, est un algorithme qui utilise une source de hasard. Plus précisément le déroulement de l’algorithme fait appel à des données tirées au hasard. Par exemple à un certain point de l’exécution, on tire un bit 0 ou 1, selon la loi uniforme et si le résultat est 0, on fait une certaine action A et si c'est 1, on fait une autre action. On peut aussi tirer un nombre réel dans l'intervalle [0,1] ou un entier dans un intervalle [i..j].
Classe de complexité
En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.

Copyright © 2025 EPFL, tous droits réservés

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.