Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Aspects algorithmiques de la combinatoire (48h, 6 ECTS)

Responsable : Gilles Schaeffer

Objectifs

Il s'agit d'un cours qui présente quelques objets et outils classiques ou actuels de la combinatoire, avec un fort accent mis sur la combinatoire énumérative et bijective, ses aspects algorithmiques et ses liens avec la physique statistique.

Plan du cours et intervenants prévus pour 2018-2019

Le cours prendra la forme de séances de 2h30 et aura lieu le jeudi midi de 12h45 à 15h15. Les cours auront lieu en français sauf si suffisament d'étudiants demandent que les cours aient lieu en anglais, les supports de cours et sujet d'examen seront disponibles en anglais.

Les intervenants seront cette année Gilles Schaeffer (LIX, Palaiseau), Enrica Duchi (IRIF, Paris), Eric Fusy (LIX, Palaiseau) et Matthieu Josuat-Vergès (IGM, Marne-la-Vallée)

La première période sera consacrée à des méthodes fondamentales d'énumération et de génération aléatoire. La deuxième période au contraire portera sur l'étude approfondie de familles d'objets combinatoires particulièrement intéressants (et devrait être l'occasion de revenir sur et d'utiliser les techniques apprises dans la première partie).

Le plan prévisionnel du cours:

  • 13/10, 20/10 [EF,GS]: Introduction, Inclusion-Exclusion, Théorème BEST, Théorème Matrix-tree.
  • 27/10, 4/10 [GS]: Série génératrices, Arbres, Lemme cyclique, inversion de Lagrange.
  • 11/10 [EF]: Algorithmes de génération aléatoire
  • 18/10 [GS]: Séance d'exercices
  • 25/10 [GS]: Lemme de Lindtröm-Gessel-Viennot
  • 08/11, 15/11 [EF] : Algorithmes de génération aléatoire
  • 22/11: Exam 1
  • 06/12, 13/12, 20/12, 10/01, 17/01 [ED, GS]: Énumération et codage de chemins, polyominos, cartes
  • 24/01, 31/01 [MJV]: Tableaux de Young et algorithme de Robinson-Schensted-Knuth.
  • 7/02, 14/02, 21/02 [MJV]: Partitions planes, partitions planes renversées, algorithme de Hillman-Grassl.
  • 28/2 ou 7/03: Exam 2

Modalités et annales d'examen

L'évaluation est basée sur deux examens, l'un à la fin de la première période et l'autre à la fin de la deuxième période, tous deux sur table et d'une durée de 2h30. La note finale est la moyenne (arithmétique !) des notes des deux examens.

Annales (attention le programme des cours, notamment dans la seconde période, peut être assez différent d'une année sur l'autre)
sujet 2011 sujet 1ère période 2012/2013 sujet 2ème période 2012/2013 Sujet et Corrigé, 1ère période 2015/2016 Sujet et Corrigé, 1ère période 2016/2017

Notes de cours : un chapitre de livre qui peut servir de notes de cours et un complément au sujet du jardin de Catalan un chapitre de livre plus détaillé sur l'énumération des cartes et un article sur les bijections à base d'orientations minimales pour les cartes.

Pré-requis

Elements d'algèbre élémentaire, principes d'algorithmique.

Cours liées

Le cours est très lié au cours 2-15, bien que chacun des deux puisse être suivi indépendemment de l'autre: 2-10 et 2-15 traitent souvent des mêmes problèmes, d'un point de vue exact et bijectif dans 2-10, d'un point de vue asymptotique dans 2-15.

Plus généralement le cours 2-10 s'inscrit naturellement dans un parcours algorithmique.

Bibliographie

  • Lothaire: Combinatorics on Words,
  • Knuth: The art of computer programming, Volume 3,
  • Flajolet, Sedgwick : Analysis of algorithms,
  • Stanley: Enumerative Combinatorics,
  • Wilf: Generatingfunctionology,
  • Berge : Principes de combinatoire,
  • Biggs: Algebraic Graph Theory,
  • Van Lint – Wilson: A course in Combinatorics,
  • Andrews, The Theory of Partitions,
  • Andrews, q-series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra

Équipe pédagogique

M. AlbenqueCRCNRSLIX
G. ChapuyCRCNRSIRIF
S. CorteelDRCNRSIRIF
E. DuchiMCU. Paris 7IRIF
E. FusyCRCNRSLIX
M. Josuat-VergèsCRCNRSIGM
J. LovejoyCRCNRSIRIF
D. PoulalhonMCU. Paris 7IRIF
D. RossinCRCNRSLIX
G. SchaefferDRCNRSLIX
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA