Cours Master 2 Informatique Recherche: Aspects Algorithmiques de la Combinatoire
Ce cours est un tour d'horizon des objets fondamentaux de
l'algorithmique et de la combinatoire: les mots, arbres, permutations,
graphes et cartes (i.e. les plongements de graphes sur une surface).
Pour chacun de ces objet on étudie les algorithmes fondamentaux
associés et on analyse leurs performances.
Cette analyse fait intervenir des problèmes d'énumération.
Diverses techniques d'énumération sont alors mises en oeuvre:récurrences, séries génératrices, bijections.
Contrôle continu 2006
Devoir à rendre pour le 11 décembre
-
Polycopié du cours
-
Annales d'Examen
-
Ouvrages conseillés
-
Ouvrages Généraux:
Cormen, Thomas H. & Leiserson, Charles E. & Rivest, Ronald L.
Introduction to algorithms.
- MIT Press (Massachusetts Institute of Technology), 1990.
Cormen, Thomas H. & Leiserson, Charles Eric & Rivest, Ronald L.
Introduction à l'algorithmique.
- Dunod, 1994.(traduction du précédent)
Knuth, Donald E.
The art of computer programming, Volume 3: sorting and searching. Second edition updated and revised.
- Addison Wesley, 1998.
Addison-Wesley Series in Comput.Science and Informat.process
).
-
Mots:
Lothaire, M.
Combinatorics on words.
- Addison Wesley, 1983.
- (Encyclopedia of Mathematics and its Appl./Addis.Wesley; 17).
Crochemore, Maxime & Rytter, Wojciech
Text algorithms.
- Oxford university press, 1994.
-
Analyse d'Algorithmes:
Graham, Ronald L. & Knuth, Donald E. & Patashnik, Oren
Concrete mathematics: a foundation for computer science. Dedicated to Leonhard Euler (1701-1783).
- Addison Wesley, 1989.
Sedgewick, Robert & Flajolet, Philippe
An introduction to the analysis of algorithms.
- Addison Wesley, 1996.
-
Arbres:
- Voir ouvrages généraux.
-
Permutations:
Berge, Claude
Principes de Combinatoire
.
- Dunod, Paris 1968
Sagan, Bruce Eli
The symmetric group : representations, combinatorial algorithms and symmetric functions.
- Wadsworth & Brooks / Cole, 1991.
-
Graphes:
Berge, Claude
Hypergraphes, combinatoire des ensembles finis.
- Bordas, 1987.
Berge, Claude
Graphes. 3ème édition.
- Gauthier-Villars, 1983.
Even, Shimon
Graph algorithms.
- Computer Science Press, 1979.
(Computer software engineering series).
-
Sujets de devoirs