La Programmation Par Contraintes est un paradigme de programmation basé sur la logique. Le conténu de la mémoire peut être compris comme une formule logique qui exprime des connaissances (souvent incomplètes) par des équations et des appartenances de variables à des domaines numériques. L'avancement du calcul est contrôlé par ce qui est logiqement impliqué par la mémoire. La construction d'un arbre de recherche, qui est centrale dans la Programmation Logique, est içi seulement un outil parmi d'autres à la disposition du programmateur. Ce paradigme fondamental permet de réaliser programmation impérative, fonctionnelle, orienté objet, distribué et logique.

Ce cours se focalise sur l'utilisation de la programmation par contraintes pour la résolution de problèmes combinatoires, pour lesquels il faut chercher une solution (optimale) dans un très grand espace de solution potentielles.

Nous allons utilsier le langage Oz et le système de programmation Mozart.

1. Le modèle d'exécution
2. Programmation concurrente dataflow
3. Contraintes de domaine fini en Oz
4. Propagateurs
5. Blocage de propagateurs et recherche multi-dimensionnelle
6. Réification et contraintes souples
7. Optimisation
8. Symétries et contraintes redondantes

• Programmation logique en Oz
• Implémentation de machines de recherche
• Un exemple complèt : Le Test Auto-Référentiel

• Bases de la programmation fonctionnelle (OCaml, Haskell, …), par exemple Programmation Fonctionnelle du L3 :
  • Modéliser avec des termes (arbres)
  • Programmer avec des fonctions d'ordre supérieure (map, fold, iter, etc.)
  • Programmer avec des termes fonctionnelles (function x → … en OCaml)
• Bases de la logique des prédicats, par exemple Logique du L3 :
  • formules, solutions, implication logique
  • résolution de systèmes d'équations symboliques (algorithme d'unification)

Il n'est pas nécessaire d'avoir suivi un cours de Prolog.