Graphes, algorithmique et complexité

Vous êtes ici :

Graphes, algorithmique et complexitéCode de l'UE : HMIN333M

Présentation

Ce module se situe à l'interface de la combinatoire des structures discrètes, de l'algorithmique et de la théorie de la complexité. Il comportera donc plusieurs volets complémentaires tels que :
[Théorie des graphes.] L'objectif est ici de présenter les développements récents et les techniques émergentes pour les problèmes classiques (e.g. coloration, domination…) mais aussi les théories des décompositions de graphes et des mineurs ou encore des graphes géométriques / topologiques.
[Algorithmes combinatoires.] Les propriétés structurelles des graphes (décomposition, plongement dans les surfaces) permettent souvent, sur des classes de graphes particulières, soit de prouver l'existence d'algorithmes efficaces ou de concevoir de tels algorithmes. Nous étudierons essentiellement les méthodes algorithmiques (polynomiales, paramètrées, exponentielles) permettant de calculer des solutions exactes à des problèmes d'optimisation combinatoire.
[Algorithmique paramétrée.] Au delà de la théorie de la complexité classique, nous nous intéresserons en particulier à la complexité paramétrée et aux méthodes de pré-processing polynomial (kernelization) en lien avec la logique (model checking) et les automates.

Volume horaire

  • CM : 13.5
  • TD : 25.5
  • TP : 0
Diplômes intégrant cette UE

En bref

Crédits ECTS 5

Période de l'année
S3