Objectifs

L’objectif de cette UE est de présenter la modélisation et la résolution de problèmes de recherche et d'optimisation combinatoire s'appuyant principalement sur des cadres de représentations issus de l'intelligence artificielle (réseaux de contraintes (CSP), logique propositionnelle (SAT)), et les principaux algorithmes associés (résolution/élimination de variable, cohérence locale, recherche arborescente et locale). Ces techniques sont utilisées dans de nombreux domaines (vision, planification, diagnostic, ordonnancement, bioinformatique, déduction automatique, gestion de ressources...) pour modéliser, analyser et contrôler des systèmes complexes.

Le cours comprend une partie fondamentale consacrée à la théorie de la complexité (classes polynomiales, problèmes NP-complets, preuves de NP-complétude) et une partie consacrée à la présentation et à la compréhension des principaux algorithmes et techniques de résolution formant une boîte à outils pour la résolution de problèmes combinatoires en intelligence artificielle.

Mots-clés :
Programmation par Contraintes, Optimisation, Logique Propositionnelle, Recherche Complète, Recherche Heuristique, Théorie de la Complexité.
Pré-requis :
De bonnes bases en logique propositionnelle et en algorithmique générale.

Description

Cours (20h)

Algorithmes énumératifs : Principe de base et illustration sur un problème (voyageur de commerce) . Rappel sur le problème SAT : la procédure de Davis et Putnam. Définition du cadre des CSP et exemples ; algorithme de backtrack. Optimisation  dans les CSP valués ; algorithme de branch and bound.

Production de conséquences : Introduction : pourquoi la recherche de conséquences (inférence, synthèse d'information, propagation). Illustration sur SAT : résolution,  propagation unitaire, recherche d'impliqués premiers. Amélioration d'algorithmes énumératifs : par recherche de conséquence (propagation) et par backtrack intelligent. Illustration sur les CSP, sur SAT.

Recherche incomplète : Algorithmes énumératifs partiels et algorithmes de recherche locale (e.g. descente, recuit simulé, recherche taboue)

Notions de théorie de la complexité : Notion de complexité des problèmes. Réductions entre problèmes, complétude pour une classe. Illustration : quelques problèmes polynomiaux (2-SAT, Horn-SAT) et NP-complets  (SAT,  3-SAT,  Coloriage de graphe, cohérence d'un CSP,    etc…).

Bibliographie :

  • Papadimitriou C.M., Computational Complexity, Addison- 1994.
  • Handbook of Constraint Programming, Elsevier, 2006.
  • Alliot, Schiex, Brisset, Garcia, Intelligence artificielle et Informatique théorique, Cépaduès, 2002.
Equipe pédagogique :
Martin Cooper , Hélène Fargier, Simon de Givry, Thomas Schiex
Responsable :
Hélène FARGIER ( Cette adresse email est protégée contre les robots des spammeurs, vous devez activer Javascript pour la voir. ) 05 61 55 82 97