Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme probabiliste
Résumé
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].
Les algorithmes probabilistes sont étudiés car ils sont souvent plus simples à analyser et très souvent plus rapides.
Un algorithme est dit probabiliste si son comportement dépend à la fois des données du problème et de valeurs produites par un générateur de nombres aléatoires.
En particulier un même algorithme probabiliste, exécuté deux fois sur le même jeu de données, peut rendre deux réponses différentes du fait de valeurs aléatoires différentes.
Parmi les algorithmes probabilistes, on distingue généralement ceux dits de Monte-Carlo, ceux dits de Las Vegas et ceux dits d'Atlantic City
Un algorithme de Monte-Carlo peut donner une réponse approchée dans un certain intervalle de confiance. Dans ce cas, on cherche à avoir un petit intervalle de confiance tout en conservant une complexité en temps faible, par exemple polynomiale en la taille de l'entrée.
Un algorithme de Las Vegas donne toujours un résultat exact, mais le temps de calcul est petit avec une très forte probabilité. En particulier pour certains tirages aléatoires, l'algorithme peut soit prendre un temps très long, soit pire encore ne pas se terminer, mais ces deux cas n'arrivent qu'avec un probabilité nulle ou dérisoire. Ce qu'on cherche c'est montrer que le temps de calcul attendu en moyenne et/ou en probabilité est polynomial.
Un algorithme d'Atlantic City donne une réponse avec une très forte probabilité sur l'exactitude de la réponse pour un temps de calcul faible en moyenne probabiliste.
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.