Structures de données

Structures de données Licence d'informatique et licence d'IUP	Maxime.Crochemore@univ-mlv.fr Université de Marne-la-Vallée, octobre 2003
Présentation Le cours vise à présenter les principales structures de données utilisées en programmation avec les algorithmes qui les accompagnent. Le cours commence par une introduction à l'algorithmique et contient une revue des algorithmes de recherche et de classements. Les têtes de chapitre sont : complexité asymptotique, récursivité, classements (tri rapide), types abstraits (liste, pile, file), hachage, arbres, codage de Huffman, arbres binaires de recherche, arbres AVL, B-arbres, files de priorité (tri par tas), tri lexicographique, tris externes (tri par fusion polyphase). Pour la suite du cours, voir « Algorithmique - graphes et automates ».
Organisation Douze cours de deux heures Algorithmique (conception, preuve, complexité) Récurrence et récursivité (aux formats pdf ou ppt) Classements internes (tri rapide) (aux formats pdf ou ppt) Types abstraits de données (listes) (deux cours) (aux formats pdf ou ppt) Hachage (aux formats pdf ou ppt) Arbres (compression de texte) (deux cours) (aux formats pdf ou ppt) Ensembles (arbres binaires de recherche) et files de priorités (aux formats pdf ou ppt) B-arbres (aux formats pdf ou ppt) ou arbres AVL (aux formats pdf ou ppt) Tri lexicographique (aux formats pdf ou ppt) Tris externes (aux formats pdf ou ppt) Douze séances de Travaux Dirigés par Frédérique Bassino, Cyril Nicaud, Giuseppina Rindone, et Marc Zipstein Contrôles devoirs de programmation (novembre-janvier) examen écrit (janvier) Sujets passés : 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997.
Références principales A.V. Aho, J.E. Hopcroft et J.D. Ullman, Structures de données et algorithmes, InterEditions, 1988. D. Beauquier, J. Berstel et Ph. Chrétienne, Éléments d'algorithmique, Masson, 1992, 463 pages.
Institut Gaspard-Monge, Laboratoire d'informatique, le 28 mai 2003, Maxime Crochemore