Algorithmique
Graphes et automates
Licence d'informatique
et
licence d'IUP
Université de Marne-la-Vallée, janvier 2004
Présentation
Ce cours est la suite du cours « Structures de données ». Il présente des algorithmes de traitement de graphes, d'automates et de textes. Il introduit quelque structures de données supplémentaires utilisées dans ce cadre.Les thèmes en sont : problèmes sur les graphes, coloration des graphes, exploration des graphes, tri topologique, composantes connexes, clôture transitive, plus courts chemins (algorithmes de Dijkstra, et de Bellman-Ford), arbres recouvrants (algorithmes de Kruskal et de Prim), flots dans les graphes, représentation d'équivalences, équivalence et minimisation d'automates, recherche de motifs, comparaison de mots.
Organisation
- Douze cours de deux heures
- Graphes (coloration, parcours) (deux cours) (aux formats pdf ou ppt)
- Chemins et cycles eulériens
- Clôture transitive (aux formats pdf ou ppt)
- Plus courts chemins (aux formats pdf ou ppt)
- Arbres recouvrants (aux formats pdf ou ppt)
- Flots (aux formats pdf ou ppt)
- Automates - minimisation - équivalence (deux cours) (aux formats pdf ou ppt)
- Recherche de motifs (aux formats pdf ou ppt)
- Alignements (aux formats pdf ou ppt)
- Algorithmes parallèles
- Douze séances de Travaux Dirigés
- par Cyril Nicaud et Marc Zipstein
- Contrôle
Références principales
-
T.H. Cormen, C.E. Leiserson, and R.L. Rivest,
Introduction to Algorithms,
The MIT Press, 1990, 1028 pages.
Version en français chez Dunod. - D. Beauquier, J. Berstel et Ph. Chrétienne, Éléments d'algorithmique, Masson, 1992, 463 pages.