Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-4-1 [2011/07/12 19:26] (current)
Line 1: Line 1:
 +
 +===== Langages de programmation - Programmation par Contraintes (24h, 3 ECTS) =====
 +
 +Responsable : Sylvain Soliman (INRIA)
 +
 +==== Intervenants ====
 +
 +   * Programmation concurrente et linéaire avec contraintes (18h, [[http://contraintes.inria.fr/~soliman/recherche.html|Sylvain Soliman]], INRIA Paris-Rocquencourt)
 +   * Fondements logiques, contraintes globales, symétries (6h, [[http://contraintes.inria.fr/~fages/|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 : [[C-2-1|2-1]] [[C-2-2|2-2]] [[C-2-3|2-3]] [[C-2-4-2|2-4-2]] [[C-2-5|2-5]] [[C-2-6|2-6]] [[C-2-7|2-7]] [[C-2-31-1|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/|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 ====
 +   * [[2009-2010-C-2-4-1|Année 2009-2010]]
 +   * [[2008-2009-C-2-4-1|Année 2008-2009]]
 +   * [[2007-2008-C-2-4-1|Année 2007-2008]]
 +   * [[2006-2007-C-2-4-1|Année 2006-2007]]
 +
 +
 +
 +------
 +   * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.FrancoisFages, %MAINWEB%.SylvainSoliman
 +
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA