Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)
Aspects algorithmiques de la combinatoire (48h, 6 ECTS)
Responsables : Robert Cori et Gilles Schaeffer
Plan du cours et intervenants prévus pour 2010-2011
Le cours prendra la forme de séances de 2h30. Les cours auront a priori lieu en français, les polycopiés et sujet d'examen seront
disponibles en anglais.
- Qu'est ce que la combinatoire énumérative, 8 séances, Sylvie Corteel (LIAFA, Paris). (Page personnelle)
- Génération aléatoire, 6 séances, Eric Fusy (LIX, Palaiseau). (Page personnelle)
- Combinatoire bijective, applications algorithmiques, liens avec la physique statistique, 6 séances, Gilles Schaeffer (LIX, Palaiseau). (Page personnelle)
La page des sujets de stages est ici.
Des examens sont disponibles en ligne:
Objectifs
Il s'agit d'un cours qui présente quelques
objets classiques de la combinatoire
en leur donnant une motivation algorithmique,
et un développement de nature algébrique.
on propose 4 parties de "tronc commun" et quelques
exemples d'extensions (à varier selon l'année)
Plan du cours de cette année universitaire 2010-2011
Qu'est ce que la combinatoire énumérative (Sylvie Corteel)
La première partie du cours s'inspirera du
nouveau Enumerative combinatorics Volume 1 de
Richard Stanley, dont le chapitre I se trouve
[[http://math.mit.edu/~rstan/ec/ch1.pdf][ici]
Chapter 1: What is Enumerative Combinatorics?
- How to count
- Sets and multisets
- Cycles and inversions
- Descents
- Geometric representations of permutations
- Alternating permutations, Euler numbers, and the cd-index of Sn
- Permutations of multisets
- Partition identities
- The Twelvefold Way
10. Two q-analogues of permutations
En fonction du temps, on abordera d'autres chapitres
du [[http://math.mit.edu/~rstan/ec/ec1-2toc.html][livre].
Génération aléatoire (Eric Fusy)
- Méthodes élémentaires
- Méthode récursive
- Génération à la Boltzmann
- Chaines de Markov
Un polycopié associé au cours est disponible.
Combinatoire bijective, applications algorithmiques, liens avec la physique statistique (Gilles Schaeffer)
- Chemins dans Z^2, polyominos, particules sauteuses
- Arbres, cartes, graphes
- Applications aux codages et représentations compactes de structures de données.
Pré-requis
Elements d'algèbre élémentaire, principes d'algorithmique.
Bibliographie
- Lothaire: Combinatorics on Words,
- Knuth: The art of computer programming, Volume 3,
- Flajolet, Sedgwick : Analysis of algorithms,
- Stanley: Enumerative Combinatorics,
- Berge : Principes de combinatoire,
- Biggs: Algebraic Graph Theory,
- Van Lint & Wilson: A course in Combinatorics.
Modules d'extension
Voici quelques exemples de sujets traités au fil des ans.
- Les cartes
- Définitions, théoreme du genre, cartes non orientables, cartes planaires, codage compact, génération aléatoire.
- Partitions planes, couplages et pavages
- Définitions, lien avec les chemins, formules avec déterminants, Gessel-Viennot, bijections.
- Combinatoire des chaines de Markov
- Généralités, évolution, états récurrents, stationnaires, modèles de tas de sable, modèles de particules.
- Génération aléatoire avancée
- Rejet florentin, arbres couvrants (Aldous, Wilson), génération récursive, génération à la Bolzmann.
Les années précédentes
Équipe pédagogique
| R. Cori | PU | U. Bordeaux 1 | LIX |
| S. Corteel | CR | CNRS | LIAFA |
| D. Poulalhon | MC | U. Paris 7 -- CNRS | LIX |
| D. Rossin | CR | CNRS | LIAFA |
| G. Schaeffer | DR | CNRS | LIX |
| E. Fusy | CR | CNRS | LIX |
