Welcome to Christophe Paul's home page
Home | Research
| Publications | Talks |
Teaching | Vitae
Avertissement : Le
matériel ci-dessous contient des notes ou des transparents
susceptibles de contenir des erreurs ou imprécisions. Les supports ne
sont pas toujours complets par rapport au contenu du cours.
Méthodes exactes : complexité et algorithmes
paramétrés
(Master 2 Informatique, Université Montpellier 2)
- (1) Introduction
(3h): ce cours d'introduction offre un survol du contenu des l'ensemble des
séances : difficulté d'un problème - paramétrisation - algorithmes
paramétrés - kernelization (slides)
- (2) Kernelization - Noyaux :
- bornes supérieures (6h): sunflower, couronnes et conflict packing (slides)
suggestions d'exercices : rédaction du noyau quadratique pour cluster editing et chordal completion
- bornes inférieures : ou-composition, reduction paramétrés polynomiales, compositions croisée
(slides)
- (3) Algorithmes paramétrés :
- techniques algorithmiques : arbres de branchement borné, compression
itérative, algorithmes randomisés (color coding), ensembles importants (slides)
- largeur arborescente : programmation dynamique, approximation de la largeur arborescente, théorème de Courcelle (slides)
- (4) Classes de complexité
: réductions paramétrées et
W-hiérarchie (slides)
Autre materiel
- Exposé
d'introduction (Journée scientifique du LIRMM -
juin 2010)
- Ecole Jeunes Chercheurs Informatique Mathématiques du GDR IM, Perpignan, avril 2013 :
- Quelques sujets d'examens
Contrôle continu 2014-2015
- Lecture d'article : choix d'un article à lire pour le 28 novembre 2014
- Compte-rendu de cours : choix du sujet pour le 28 novembre 2014
- la note de cours (3-5 pages) devra être rédigée en Latex
- elle devra contenir des preuves décrites en cours (au moins 2) qui seront rédigée de manière complète.
- la note comprendra aussi le contexte et les définitions formelles nécessaires à la description du résultat.
- le contenu traité sera validé en cours.
Bibliographie :
- Parameterized Complexity, R. Downey and M. Fellows, 1999.
- Invitation to Fixed-Parameter Algorithms, R. Niedermeier, 2006.
- Parameterized Complexity Theory, J. Flum and M. Grohe, 2006.
- Algorithm Design, J. Kleinberg, E. Tardos, 2005
Autres cours de master
- Introduction à la théorie de la complexité (nov. 2007)
- Méthodes polynomiales de
décomposition de graphes
- Lectures notes:
- Homeworks :
|