Informatique-réseaux : algorithmique
Ingénieurs 2000Université de Marne-la-Vallée, septembre 2006
Présentation
L'objectif de ce cours est présenter des méthodes de programmation et les structures de données associées. Le cours contient une revue d'algorithmes de traitement d'arbres, de graphes, d'automates, et de textes.Les têtes de chapitre sont : arbres binaires de recherche, arbres AVL, B-arbres, flots dans les graphes, équivalence et minimisation d'automates, recherche de motifs, comparaison de mots, compression de texte.
Première partie : arbres et graphes
-
Six cours de deux heures
- Ensembles (arbres binaires de recherche) et files de priorités (aux formats pdf ou ppt)
-
Arbres déployés (Splay trees),
voir [3], [4] ou arbres.pdf
Animation par Jorge Riera - Arbres AVL (aux formats pdf ou ppt)
- B-arbres (aux formats pdf ou ppt)
-
Arbres 2-4 et arbres rouges-noirs, voir [1,3,4]
ATTENTION : erreur dans Fig 9.36 de [3] concernant la suppression dans un arbre rouge-noir - Chemins et cycles eulériens
- Flots (aux formats pdf ou ppt)
-
Compression de texte (MTF, BW, LZ)
voir, par exemple, Pattern Matching and Text Compression Algorithms
- Six séances de Travaux Dirigés avec Tayssir Touili
-
Contrôles
- test écrit le 30 octobre
- devoir de programmation (voir ci-dessous)
Deuxième partie : automates et textes
- Six cours de deux heures
- Six séances de Travaux Dirigés avec Tayssir Touili
-
Contrôles
- test écrit le 20 décembre
- sujet du devoir de programmation (projet commun aux deux parties) à rendre avant le 4 février 2007
Philippe Geluck - Le chat
Références principales
- D. Beauquier, J. Berstel et Ph. Chrétienne, Éléments d'algorithmique, Masson, 1992, 463 pages.
- M. Crochemore, C. Hancart et T. Lecroq, Algorithmique du texte, Vuibert, 2001, 347 pages.
- M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Wiley, 2004.
- R. Sedgewick, Algorithms in Java, Parts 1-4, Addison-Wesley, 2003.
