Semestre 8 – Option – Méthodes exactes pour la résolution des problèmes CSP et SAT

Objectifs

Présenter les différentes approches pour la résolution exacte des problèmes CSP et SAT.

Prérequis

Logique propositionnelle et Algorithmique de Licence.

Contenu pédagogique de l’UE

  • Représentation de problèmes, NP-complétude.
  • Les problèmes de satisfaction de contraintes :
    • Domaines finis, complexité (classes polynomiales, phénomènes de seuil).
    • Consistances et filtrages, Backtrack, Forward-Checking, MAC.
    • Contraintes n-aires, Constraint Programming.
  • Les méthodes de résolution en logique propositionnelle :
    • De la logique à SAT (Formes normales, 2-SAT, 3-SAT, Horn-SAT)
    • Complexité (Classes polynomiales, Phénomènes de seuil)
    • Méthodes de résolution : tableaux, résolution, DP, DPLL