WikiMPRI

Responsable : Sylvain Soliman (INRIA)

• 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)

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.

• 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.

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 abstraiteou 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) ==== |Date ^ Contenu ^Intervenant | | 15/09/09 | cours 1 - Introduction, exemples | F. Fages | | 22/09/09 | relache | – | | 29/09/09 | cours 2 - Contraintes, logique, unification | F. Fages | | 06/10/09 | cours 3 - CSP : algorithmes de résolution par simplification et réduction des domaines | F. Fages | | 13/10/09 | cours 4 - Symétries ; CHR | F. Fages | | 20/10/09 | cours 5 - CLP : sémantique opérationnelle, exemples | S. Soliman | | 27/10/09 | cours 6 - CLP : sémantique de point fixe I | S. Soliman | | 03/11/09 | cours 7 - CLP : sémantique de point fixe II et sémantique logique I | S. Soliman | | 10/11/09 | cours 8 - CLP : sémantique logique II | S. Soliman | | 17/11/09 | remise du projet de programmation | – | | 24/11/09 | cours 9 - CC : exemples, sémantique opérationnelle | S. Soliman | | 01/12/09 | cours 10 - CC : sémantique(s) dénotationelle(s) | S. Soliman | | 08/12/09 | cours 11 - Correction du projet | T. Martinez et S. Soliman | | 15/12/09 | cours 12 - CC : sémantique logique linéaire I | S. Soliman | | 05/01/10 | cours 13 - CC : sémantique logique linéaire II | S. Soliman | | 12/01/10 | cours 14 - LCC | S. Soliman | | 19/01/10 | cours 15 - !SiLCC | S. Soliman | | 26/01/10 | cours 16 - liens entre !SiLCC et CHR | T. Martinez et S. Soliman | | 02/02/10 | relache | – | | 09/02/10 | examen | – | ==== Les années précédentes ==== * Année 2009-2010 * Année 2008-2009 * Année 2007-2008 * Année 2006-2007 —— * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.FrancoisFages, %MAINWEB%.SylvainSoliman