Ê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 GraphSearch.
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.
Tri rapide Dans cette section, nous expliquons l'exemple du tri rapide randomisé qui est un algorithme de Las Vegas.
L'algorithme de tri rapide aléatoire, ou quicksort randomisé consiste à trier un tableau d'éléments en utilisant diviser pour régner :
choisir aléatoirement un pivot (i.e. un élément du tableau) ;
partitionner le tableau en plaçant les éléments strictement plus petits que le pivot à gauche (sous-tableau A), puis le pivot, puis les éléments plus grands que le pivot (sous-tableau B) ;
trier récursivement les sous-tableaux A et B.
Le résultat est un tableau constitué d'un tri du tableau A, suivi du pivot, suivi d'un tri du tableau B.
vignette|354x354px|On effectue l'algorithme de tri rapide randomisé sur un exemple. Les pivots successifs sont surlignés en gris.
vignette|299x299px|On effectue l'algorithme de tri rapide randomisé sur le même exemple en surlignant en gris les pivots successifs. On obtient un autre ordre de tri L'aléatoire se situe au niveau du choix des pivots. Le résultat est un tableau trié, quels que soient les choix de pivots, i.e. le résultat est toujours correct. En revanche, le temps d'exécution dépend de ces choix. C'est, en fait, un tri souvent utilisé sur des tableaux de grandes tailles parce que, de manière empirique, il donne de bons résultats en complexité temporelle.
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.