Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Langages de programmation - Programmation par Contraintes (24h, 3 ECTS)

Responsable : Sylvain Soliman (INRIA)

Intervenants

• Programmation concurrente et linéaire avec contraintes (18h, Sylvain Soliman, INRIA Paris-Rocquencourt)
• Fondements logiques, contraintes globales, symétries (6h, François Fages, INRIA Paris-Rocquencourt)

Motivations et objectifs

Le but de ce cours est de présenter les concepts, principes et formalismes sous-jacents à la programmation par contraintes. Nous partirons des fondements logiques pour aboutir aux extensions récentes permettant d'inclure concurrence et traits impératifs, en passant par la programmation logique avec contraintes et ses applications à la résolution de problèmes combinatoires.

Un projet de programmation simple (e.g. résolution de SUDOKU) et un examen écrit seront utilisés pour l'évaluation des élèves.

Plan du cours

• Fondements logiques des langages de contraintes et des problèmes de satisfaction de contraintes CSP.
• Exemples de programmes logiques avec contraintes en résolution de problèmes combinatoires.
• Algorithmes de résolution de contraintes par simplification.
• Algorithmes de propagation de contraintes par réduction des domaines des variables.
• Contraintes globales et propriétés de graphes.
• Symétries de variables, de valeurs, de couples variables-valeurs, et élimination.
• Sémantiques opérationnelle, de point fixe et logique des programmes logiques avec contraintes CLP.
• Preuves de protocoles cryptographiques en CLP.
• Langages concurrents avec contraintes; sémantiques opérationnelles et dénotationnelles des langages CC.
• Sémantique en logique linéaire; systèmes de contraintes pour les traits impératifs.

Pré-requis et cours liés

Des notions élémentaires de sémantique opérationnelle (avoir déjà vu des règles de réécriture et des règles d'inférence), et un goût pour la programmation sont requis pour suivre ce cours.

Il peut être utile d'avoir suivi les cours de première année PROLOG et programmation logique par contraintes ainsi que Sémantique des langages de programmation. Le cours Fondements de l'interprétation abstraite ou le fait de suivre le cours de deuxième année correspondant pourra aussi apporter un regard différent sur certains points qui seront abordés.

Cours liés : 2-1 2-2 2-3 2-4-2 2-5 2-6 2-7 2-31-1

Langues et supports du cours

Le cours sera en français.

Des notes de cours seront disponibles sous la forme de polycopiés ou de transparents, en principe en anglais.

Les notes de cours et les transparents de François Fages sont disponibles sur http://contraintes.inria.fr/~fages/Teaching

Bibliographie

• Principles of Constraint Programming, Krzysztof Apt, Cambridge University Press, 2003.
• Programmation Logique par Contraintes, François Fages, Collection "Cours de l'Ecole Polytechnique" Ellipses, Paris, 1996.

Planning prévisionnel (sujet à modification)

Les années précédentes

• Année 2008-2009
• Année 2007-2008
• Année 2006-2007