Master Informatique 2e année


UE : Analyse d'Algorithme
2010-2011

Modalités

Projet de programmation : sujet 2010, sujet 2009

[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

Ces notes sont régulièrement mises à jour, ne les imprimées pas !

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

  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. Un second algorithme glouton
      3. Algorithme exact

gavoille@labri.fr Mail