Discussion:Algorithme probabiliste

Autres discussions [liste]

Admissibilité
Neutralité
Droit d'auteur
Article de qualité
Bon article
Lumière sur
À faire
Archives
Commons

Cet article est indexé par les projets Informatique, Probabilités et statistiques et Mathématiques.

Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.

**Évaluation** de l’article « **Algorithme probabiliste** »
Avancement	Importance
Bon début	Élevée	Informatique (discussion • critères • liste • stats • hist. • comité • stats vues)
	Moyenne	Probabilités et statistiques (discussion • critères • liste • stats • hist. • comité • stats vues)
	Faible	Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues)

Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.

Probabiliste et randomisé[modifier le code]

Bonjour,

dans le Cormen (Algorithmes ou Introduction à l'algorithmique selon les éditions), il y a une distinction marquée entre algorithme probabiliste et algorithme randomisé et ici on dit que c'est la même chose. Je suppose que c'est dû à une traduction pas tout à fait bonne du Cormen, puisque j'ai toujours entendu les deux prononcés indifféremment. Qu'en pensez-vous ?

--Roll-Morton (discuter) 23 novembre 2013 à 14:26 (CET)[répondre]

Je ne lis que des sources en anglais, quasiment. A quel(s) terme(s) anglais se réfère(nt) ce(s) terme(s) ? Est-ce qu'il y a un lexique dans la source ? Quelle différence fait la source entre ces deux types d'algorithmes. Ce ne serait pas la différence Las Vegas/Monte Carlo ? Cordialement --Jean-Christophe BENOIST (discuter) 24 novembre 2013 à 13:02 (CET)[répondre]

En allant vérifier ma source, je me suis aperçu que j'avais mal lu, en fait en anglais probabilistic algorithm et randomized algorithm ont le même sens, comme en français (le Cormen fait la distinction entre analyse probabiliste et algorithme randomizé, ce qui est normal). Désolé pour l'erreur mais merci d'avoir répondu ! D'ailleurs si vous avez un peu temps ce serait bien que l'on retape cet article. Cordialement,--Roll-Morton (discuter) 24 novembre 2013 à 21:57 (CET)[répondre]

Je pense aussi qu’il y a une confussion entre : algorithme faisant appel au hasard (type Monte-Carlo) et algorithme fournissant un résultat probabiliste (type Filtre de Bloom ou HyperLogLog --Unio 18 juin 2015 à 14:05 (CEST)

A moins que je n'aie pas compris ce que vous voulez dire, il me semble que toute confusion possible est levée par la distinction entre algorithme de Monte-Carlo, algorithme de Las Vegas et algorithme d'Atlantic City. Les filtres de Bloom et les algorithmes HyperLogLog font partie des algorithmes de type Atlantic City. --Pierre de Lyon (discuter) 19 juin 2015 à 12:57 (CEST)[répondre]

Il me semble aussi qu'il n'y a pas de problème. Je ne connais pas bien les filtres de Blum, et l'article ne fait pas référence explicite à la complexité, mais on est pour sûr dans du Monte Carlo ou du Atlantic City. --Roll-Morton (discuter) 22 juin 2015 à 21:40 (CEST)[répondre]

Des idées pour l'exemple introductif[modifier le code]

Quelques idées sourçable par le Cormen (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition]) :

tri rapide randomisé (une permutation aléatoire avant un tri rapide, revient à une complexité moyenne)
MAX-3-CNF (donne le bon résultat avec une certaine probabilité)

— Le message qui précède, non signé, a été déposé par Roll-Morton (discuter), le 27 février 2015 à 10:07‎