Master Informatique 2e année


UE : Analyse d'Algorithme

2009-2010

Modalités

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

Notes de cours

Plan du cours


  1. 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

  2. Algorithmes exactes
    1. Temps polynomial vs. exponentiel
    2. Problèmes jouets
    3. Algorithmes exhaustifs
    4. Complexité paramétrique
    5. Arbre de recherche borné
      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"
    7. Réduction aux graphes de treewidth bornée
      1. Principe
      2. Exemple de noyau
      3. Converture par sommets
      4. Noyau et approximation
    8. Théorie des mineurs de graphes
      1. Définitions
      2. Théorème des mineurs de graphes
      3. Applications
    9. Réduction aux graphes de treewidth bornée
      1. Décomposition arborescente
      2. un exemple simple: 3-coloration
      3. Couverture par sommets pour treewidth bornée
      4. Application aux graphes planaires
      5. Amélioration pour les graphes planaires
    10. Remarques finales

  3. 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. Algorithme exact

gavoille@labri.fr Mail