Cours MPRI 2-10: Aspects Algorithmiques de la Combinatoire
Voir aussi la
page
du MPRI concernant ce cours.
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.
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
Pages personnelles intéressantes