Programmation Logique et par Contraintes avancée

Université Paris-Diderot, M2 du master professionnel Ingénierie Informatique
Année 2011/2012

Examen

Tous les documents papier sont autorisés, par contre les ordinateurs et tout moyen de communication avec l'extérieur ne l'est pas.

L'antisèche Oz, par Antoine Dumoulin.

TP noté

Le TP du 23 novembre sera noté, c'est-à-dire que vous me rendez à la fin de la séance votre solution. La note de ce TP constitue la note de contrôle continu pour ce module.

[Énoncé du TP noté de l'année dernière]

Horaires et Salle

Mercredi, 13h30 à 16h30. On commence par un cours en salle 416B, puis en passe en salle de TP 447C.

Travaux Pratiques

TP1 : [Énoncé] [Corrigé Exercice 1] [Corrigé Exercice 2] [Corrigé Exercice 3] [Corrigé Exercice 4]
TP2 : [Énoncé] [Corrigé Exercice 1] [Corrigé Exercice 2]
TP3 : [Énoncé] [Corrigé Exercice 1] [Corrigé Exercice 2]
TP4 : [Énoncé] [Corrigé Exercice 1] [Corrigé Exercice 2]
(il n'y a pas de TP numéro 5)
TP6 (TP noté) [Énoncé] [Corrigé]
TP7 [Énoncé] [Solution naive] [Solution par branch-and-bound]

Planning du cours

Numéro	Jour	Contenu
1	28/09	Cours 1 : Introduction [Le fichier d'exemples Oz]
2	5/10	Cours 1 terminé
3	12/10	Cours 2 : Exécution de programmes Oz
4	19/10	Cours 3 : Programmation concurrente dataflow en Oz
5	26/10	Cours 4 : Programmation logique en Oz
6	2/11	Cours 5 : Contraintes de domaine fini en Oz
7	9/11	Cours 6 : Propagateurs, recherche multidimensionnelle
	16/11	-- annulé --
8	23/11	Cours 7 : Blocage des propagateurs, symétries, contraintes redondantes
9	30/11	Cours 8 : Contraintes réifiées, optimisation
10	7/12	Cours 8 terminé
	14/12	Examen

Pour information :

Calendrier de l'université

Logiciels utilisés

Mozart: est le système de programmation pour le langage Oz. Vous y trouvez le code source (mozart est du logiciel libre), des exécutables pour Linux et Windows, et plein de documentations.
Debian GNU/Linux contient des paquets de mozart pour certains architectures (parmi d'autres i386 et powerpc, mais malheureusement pas amd64). Installer les paquets mozart, mozart-stdlib, et éventuellement mozart-doc.

Ouvrages et documents utilisés pour ce cours

Ne soyez pas effrayé par cette liste, elle sert simplement à documenter les sources d'information principales que j'utilise pour préparer ce cours. Normalement les transparents (et les explications supplémentaires données au cours) contiennent tout ce qu'il faut savoir.

La Documentation de Mozart est la première source d'informations sur Oz et Mozart, en particulier
- le tutoriel
- le document décrivant l'environnement de base
PROGRAMMATION -- Concepts, techniques et modèles par Peter Van Roy et Seif Haridi est un livre d'introduction à la programmation à l'aide de la programmation multi-paradigme en Oz. Il peut servir comme une introduction à la programmation en Oz, mais le livre s'adresse plutôt à des débutants en programmation (niveau Licence). La programmation logique et par contrainte n'est pas traitée dans ce livre. Le contenu du livre est seulement une partie du livre en anglais (voir en bas).
Concepts, Techniques, and Models of Computer Programming par Peter Van Roy et Seif Haridi est le livre complet (~ 900 pages) qui était à la base de la version française (voir au-dessus). Ce livre contient beaucoup de matériel supplémentaire par rapport à la version française, et en particulier un chapitre sur la programmation par contraintes en Oz.
Records for Logic Programming, par Gert Smolka et R.T., donne la théorie et une technique d'implémentation des opérations Ask et Tell pour des enregistrements potentiellement infinis.
Finite Domain Constraint Programming Systems par Christian Schulte et Mats Carlsson, Handbook of Constraint Programming, 2006. Cette article explique la théorie derrière les propagateurs pour les contraintes de domaine fini et donne un résumé des techniques d'implémentation.

Ralf Treinen