Page d’accueil du cours de Magistère L2 en Mathématique et Informatique

Objets combinatoires

Équipe pédagogique : Roland Bacher Institut Fourier et Jean-Marc Vincent, Laboratoire d’Informatique de Grenoble

Objectif :

L’objectif de ce cours de magistère bi-disciplinaire Mathématique et Informatique en L2 est d’étudier des objets combinatoires, c’est à dire de les écrire, les énumérer, donner leurs propriétés, les générer aléatoirement,… Ces objets permettent la modélisation d’un très grands nombre de problèmes, en particulier en informatique où ils jouent un rôle central en algorithmique et en analyse de la complexité. Ces objets interviennent également en physique par exemple dans le modèles à spin de la physique statistique ou en biologie pour l’analyse du génome et la phylogénie.

De tels objets combinatoires ont déjà été utilisés en L1, par exemple : les vecteurs de bits, les arbres, les graphes, les partitions,… Le cours se décomposera en des activités théoriques (propriétés des objets combinatoires, méthodes d’énumération,…) et des activités expérimentales (génération aléatoire uniforme d’objets, observation et propriétés statistiques,…)

Les thèmes abordés dans ce cours seront :

I) Partitions
activités théoriques : Coefficients binomiaux, triangle de Pascal, nombres de Stirling (des deux espèces)
activités expérimentales : le générateur Random, génération uniforme de terrains avec obstacles, génération uniforme de routes dans un réseau

II) Permutations et graphes
activités théoriques : Permutations (pour les automorphismes de graphes et autres), Graphes, hypergraphes, arbres, hyperarbres et codage de Pruefer
activités expérimentales : génération de permutations (ex: jeu de carte), analyse d’algorithmes de tri

III) Arbres
activités théoriques : Arbres couvrant d’un graphe connexe, complexité, théorème de Kirchhoff, et quelques exemples (graphes complets, graphes bipartis complets, cycles, graphe de Petersen)
activités expérimentales : génération de graphes, propriétés d’arbres couvrant

En début de semestre un sujet d’étude est proposé aux étudiants (travail en binôme), un rapport sera remis en fin de semestre et une présentation orale sera faite en fin de semestre à tous les étudiants du groupe. Les sujets seront variés et comporteront une partie théorique et une partie mise en oeuvre (programmation).

Pré-requis :
- aimer compter

Présentation du 2 septembre

Calendrier prévisionnel

Calendrier 2012 : (dates des lundi. gris = vacances ou férié ; rouge = ponts ; orange = exam)

  1. Lundi 23 janvier salle 204
    • Introduction, présentation du cours, discussion sur les projets
    • Cours : Binomiaux, code de Prueffer
  2. Lundi 30 janvier salle 204
  3. Lundi 6 février salle 204
    • Cours : Partition d’entiers, diagrammes de Ferrer
  4. Lundi 20 février salle 204
    • Cours : Transformation de dés (lois uniformes discrètes) Transparents
  5. Lundi 27 février salle 204
    • Cours :
  6. Lundi 5 mars salle 204
    • Cours : Génération de structures combinatoires : vecteurs de bits, chemins dans un graphe
  7. Lundi 12 mars salle 204
    • Cours :
  8. Lundi 26 mars salle 204
    • Cours : Génération de permutations, dérangements, le problème du mélange de cartes
  9. Lundi 2 avril salle 204
    • Cours :
  10. Lundi 16 avril salle 204
    • Cours : Génération d’arbres et de graphes
  11. Lundi 23 avril salle 204
    • Cours : créneau en réserve (déplacement d’un cours)

Présentation des projets:

Références bibliographiques