Master Informatique 2e année

---

UE : Analyse d'Algorithme
2010-2011

Modalités

• 12 cours/TD intégrés
• 1 examen d'1h30 (50%)
• 1 projet de programmation (50%)

Projet de programmation : sujet 2010, sujet 2009

Enseignant : Cyril Gavoille

Ouvrages de références

• Parametrized Complexity Theory - J. Flum, M. Grohe - Springer 2006
• Invitation to fixed-Parameter Algorithms - R. Niedermeier - Oxford 2006
• Parametrized Complexity - R.G. Downey, M.R. Fellows - Springer 1999
• Algorithmes d'approximation - V.V. Vazirani - Springer 2006

Notes de cours

Plan du cours

Introduction

1. À quoi ça sert ?
2. Quelques algorithmes que nous analyserons
3. Des algorithmes pour construire quoi ?
4. Existence d’objets spécifiques: les spanners

Algorithmes exacts

1. Temps polynomial vs. exponentiel
2. Problèmes jouets
3. Algorithmes exhaustifs (brute force)
4. Complexité paramétrique: définition
5. Arbre borné de recherche
   1. Couverture par sommets de taille k
   2. Ensemble Indépendant pour les graphes planaires
   3. Ensemble dominant pour les graphes planaires
   4. Améliorations : raccourcissement de l'arbre
6. Réduction à un noyau : "kernalisation"
   1. Principe et propriété
   2. Exemple de noyau
   3. Couverture par Sommets
   4. Noyau et approximation
7. Théorie des mineurs de graphes
   1. Définitions
   2. Théorème des mineurs de graphes
   3. Applications
8. Réduction aux graphes de treewidth bornée
   1. Décomposition arborescente
   2. Un exemple simple: 3-coloration
   3. Converture par sommets pour treewidth bornée
   4. Applications aux graphes planaires
   5. Amélioration pour les graphes planaires
   6. Remarques finales

Algorithmes d'approximation

1. Introduction
2. Problèmes bien caractérisés
   1. Couplage
   2. Les problèmes MIN-MAX
   3. Comment concevoir un algorithme d'approximation ?
3. Couverture par sommets de taille minimum
   1. Un premier algorithme
   2. Un second Algorithme
   3. Technique de précalcul (color coding)
4. Couverture par ensembles
   1. Algorithme glouton
   2. Un second algorithme glouton
   3. Algorithme exact

gavoille@labri.fr