Master Informatique 2e année
UE : Analyse d'Algorithme
2009-2010
Modalités
- 12 cours/TD intégrés
- 1 examen (50%)
- 1 projet de programmation (50%)
Devoir à la maison : sujet
[Utiliser le générateur de graphes gengraph.c
pour vos jeux d'essais.]
Enseignant : Cyril Gavoille
Ouvrages de références
- Parametrized Complexity Theory - J. Flum, M. Grohe -
Springer 2006
- Parametrized Complexity - R.G. Downey, M.R. Fellows -
Springer 1999
- Algorithmes d'approximation - V.V. Vazirani - Springer 2006
- Invitation to fixed-Parameter Algorithms - R. Niedermeier -
Oxford 2006
Plan du cours
- Introduction
- À quoi ça sert ?
- Quelques algorithmes que nous analyserons
- Des algorithmes pour construire quoi ?
- Existence d’objets spécifiques: les spanners
- Algorithmes exactes
- Temps polynomial vs. exponentiel
- Problèmes jouets
- Algorithmes exhaustifs
- Complexité paramétrique
- Arbre de recherche borné
- Couverture par sommets de taille k
- Ensemble Indépendant pour les graphes planaires
- Ensemble dominant pour les graphes planaires
- Améliorations : raccourcissement de l'arbre
- Réduction à un noyau : "kernalisation"
- Réduction aux graphes de treewidth bornée
- Principe
- Exemple de noyau
- Converture par sommets
- Noyau et approximation
- Théorie des mineurs de graphes
- Définitions
- Théorème des mineurs de graphes
- Applications
- Réduction aux graphes de treewidth bornée
- Décomposition arborescente
- un exemple simple: 3-coloration
- Couverture par sommets pour treewidth bornée
- Application aux graphes planaires
- Amélioration pour les graphes planaires
- Remarques finales
- Algorithmes d'approximation
- Introduction
- Problèmes bien caractérisés
- Couplage
- Les problèmes MIN-MAX
- Comment concevoir un algorithme d'approximation ?
- Couverture par sommets de taille minimum
- Un premier algorithme
- Un second Algorithme
- Technique de précalcul (color coding)
- Couverture par ensembles
- Algorithme glouton
- Algorithme exact