Théorie de l'information : modèles,algorithmes,analyse

Tout étudiant d'un cours d'algorithmique de base apprend que la complexité moyenne de l'algorithme QuickSort est en O(n log n),celle de QuickSelect est en O(n) et celle de RadixSort est en O(n log n). De tels énoncés ont le mérite d'être simples,mais leur simplicité est trompeuse,car ils sont fondés sur des hypothèses spécifiques à chaque algorithme : pour les deux premiers algorithmes,le coût unitaire est la comparaison entre clés,tandis que,pour le troisième,le coût unitaire est la comparaison entre symboles.  Dans cet exposé,l'analyse probabiliste de trois principaux algorithmes est revisité: QuickSort,QuickSelect,et les algorithmes de dictionnaire fondés sur la structure de tri.

Mots-clés : analyse algorithmique,théorie de l'information,algorithme de tri,algorithme de recherche,complexité algorithme,analyse probabiliste,fuscia
Type de document : ensemble de données
Type de ressource : lecture
Niveau : higher education
Publics visés : learner,teacher
Proposition d'utilisation : On peut  conseiller cette ressource comme un cours de recherche sur le sujet à utiliser dans le cadre d'un master en informatique 2eme année ou recherche
Auteurs ou éditeurs : Brigitte Vallée,Institut National de Recherche en Informatique et en Automatique