Informations pratiques

Description de la ressource

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)

Domaine(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
  

Intervenants

Édition

• Institut National de Recherche en Informatique et en Automatique

Diffusion

Cette ressource vous est proposée par :

• Cette ressource fait partie de
  • Colloquium Jacques Morgenstern : Collection des séminaires