Algorithmique avancée

Les documents de ce cours ont été rédigés par Emmanuel Filiot, Albert Oliveras et Enric Rodriguez-Carbonell. L'UE est organisée en 10 séances de 4h, chaque séance comporte une partie cours et une partie TD. La dernière séance est consacrée aux exposés évalués des étudiants. Voici le planning prévisionnel de l'UE :
  1. Logique propositionnelle, SAT
  2. L'algorithme DPLL
  3. Modélisation SAT
  4. Théorie de la complexité-1, 1--15
  5. Théorie de la complexité-2, 16--36
  6. Théorie de la complexité-3
  7. Théorie de la complexité-4
  8. Théorie de la complexité-5 : 2-Sat est polynomial
  9. Chemin dans un graphe : algorithme et complexité, exemples d'application du principe des tiroirs, révisions DPLL et Tseitin
  10. Exposés
    -- Partiel

SAT

Cours

  1. Logique propositionnelle
  2. Le problème SAT, Wikipedia Fr et En
  3. L'algorithme DPLL
  4. Modélisation SAT: 0, 1, 2, 3

Exercices

  1. Logique propositionnelle 1, 2
  2. Formes normales - résolution
  3. Tutoriel solveurs SAT : le format DIMACS
  4. MiniSAT, version Javascript, SAT4J, un solveur SAT en Java
  5. Principe des tiroirs de Dirichlet, modélisation SAT
  6. Autres modélisations SAT

Introduction à la théorie de la complexité

Cours

  1. Introduction à la théorie de la complexité
  2. Problème de partition
  3. Equivalence des deux définitions de NP
  4. A propos d'encodages
  5. Le problème k-SAT, complexité du problème 1-SAT, complexité de 2-SAT (Dana Moshkovitz)
  6. Les 21 problèmes NP-complets de Richard Karp
  7. Complexité descriptive

Exercices

  1. 1-SAT et 2-SAT
  2. NP-complétude, solution en Prolog de l'exercice 6

Evaluation

Contrôle continu : un partiel sans document ni moyen électronique et un oral 50% + 50%. Il n'y a pas de seconde session.

Annales

Bibliographie


Valid HTML5