Parisian Master of Research in Computer Science

Master Parisien de Recherche en Informatique (MPRI)

Programming languages - Constraint Programming (24h, 3 ECTS)

Teacher in charge: Sylvain Soliman (INRIA)

Teachers

• Linear and Concurrent Constraint Programming (18h, Sylvain Soliman, INRIA)
• Logical foundations, Global Constraints, Symmetries (6h, François Fages, INRIA)

Goals

The aim of this course is to introduce the concepts, principles and formalisms underlying constraint programming. The course will start from logical foundations and go up to recent extensions including concurrency and imperative features, while browsing through constraint logic programming and its applications to solving hard combinatorial problems.

A simple programming project (like SUDOKU solving) and a written exam will be used for grading the students.

Outline

• Logical foundations of constraint programming and of constraint solving problems (CSP).
• Examples of constraint logic programs for solving combinatorial problems.
• Constraint solving algorithms, simplification.
• Constraint propagation algorithms, variables' domain reduction.
• Global constraints, graph properties.
• Symmetries (variables, values, and both), and their elimination.
• Operational and fixpoint semantics of constraint logic programs (CLP).
• Protocol verification in CLP.
• Concurrent constraint languages (CC); operational and denotational semantics.
• Linear logic semantics; constraint systems for imperative features and modules.

Prerequisites and related courses

Basics about operational semantics (rewriting rules and inference rules) and a certain taste for programming are required for this course.

Having attended the first year courses on PROLOG and constraint logic programming and on Programming languages semantics can be useful. The Abstract interpretation foundations or the corresponding M2 course can also reveal interesting.

Related courses : 2-1 2-2 2-3 2-4-2 2-5 2-6 2-7 2-31-1^?

Language and material

The classes will be given in French.

Slides will be in English and made available in PS or PDF.

Bibliography

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

Schedule

Previous years

• 2009-2010
• 2008-2009
• 2007-2008

Web page maintained by webmastermprimasteruniv-paris7fr.