Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

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.

• Granularité : leçon
• Structure : en réseau

"Domaine(s)" et indice(s) Dewey

• Information theory (003.54)
• Systems programming and programs (005.4)

Thème(s)

Informations pédagogiques

• 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
• Commentaires pédagogiques : Il s'agit plutôt d'un thème enseignement-recherche qui ne fait pas encore partie des cursus standard en biologie