Concept

Algorithme de Las Vegas

Résumé
En informatique, un algorithme de Las Vegas est un type d'algorithme probabiliste qui donne toujours un résultat correct ; son caractère aléatoire lui donne de meilleures performances temporelles en moyenne. Comme le suggère David Harel dans son livre d'algorithmique, ainsi que Motvani et Raghavan, le tri rapide randomisé est un exemple paradigmatique d'algorithme de Las Vegas. Quand le problème que l'algorithme résout possède plusieurs solutions, sur une même donnée, comme c'est le cas pour le tri d'un tableau qui contient des clés équivalentes, l'algorithme de Las Vegas peut retourner l'une ou l'autre de ces solutions, et il le fait de façon non prévisible. Exemple du tri rapide randomisé Tri rapide Dans cette section, nous expliquons l'exemple du tri rapide randomisé qui est un algorithme de Las Vegas. Description de l'algorithme L'algorithme de tri rapide aléatoire, ou quicksort randomisé consiste à trier un tableau d'éléments en utilisa
À 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.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement