Master Informatique 2e année


UE : Algorithmique Appliquée

2015-2016

Modalités

Projet de programmation 2015

Il s'agit de déterminer le score maximum réalisable avec une poignée de n cartes d'un jeu de UNO. De précieux détails sont disponibles ici et . Vous pourrez éventuelement utiliser le générateur de graphes gengraph.c pour vos jeux d'essais en testant par exemples les graphes uno et unok.

Articles en relations avec le projet:
(user: gavoille et password: bib0)

Enseignants

Ouvrages de références

Notes de cours

(anciennement titrées "Analyse d'Algorithme", ne pas imprimer les notes de cours car elles sont régulièrement mise à jour.)

Plan du cours

(tout ne sera pas traité)

  1. Introduction
    1. ...

  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