Master 1 Informatique

Cours de «Programmation, logique et calcul» (5 crédits)

Cours magistral : Olivier Ridoux

Travaux dirigés et travaux pratiques : Catherine Belleannée

Le cours de «Programmation, logique et calcul» de Master 1ère année examine les liens qui existent entre logique et calcul et la manière dont ils se réalisent dans les paradigmes des programmations fonctionnelle et logique.  Il suppose une bonne pratique préalable de la programmation et une connaissance élémentaire des calculs des propositions et des prédicats.   La programmation par contrainte est abordée.

Cet enseignement est supposé faire suite à un enseignement de Licence sur la programmation fonctionnelle ; celle-ci prend donc moins de place que la programmation logique.  Un autre biais pourrait être apporté dans un autre contexte.

Concernant la relation entre logique et programmation logique, le parti pris est de laisser tomber le point de vue historique qui voit la programmation logique comme une mise en oeuvre de la résolution et d'adopter le point de vue, que nous trouvons plus direct et plus porteur de réflexion sur la nature du calcul, qui consiste en voir dans l'exécution d'un programme la recherche d'une preuve.  Le point de vue qui conduit à la programmation fonctionnelle en considérant l'exécution d'un programme comme la normalisation d'une preuve est aussi présenté, même si on ne développe pas la programmation fonctionnelle dans ce cours. 

Des travaux pratiques permettent d'utiliser un environnement de programmation logique concret.  On insiste sur l'utilisation effective des outils de l'environnement comme par exemple le traceur.  L'environnement choisi est SICStus PROLOG pour lequel l'IFSIC a acquis une licence permettant l'installation de l'environnement par les étudiants sur leurs machines personnelles.  Cependant, d'autres systèmes peuvent faire l'affaire, comme GNU-PROLOG et SWI-PROLOG, sauf en ce qui concerne la programmation par contrainte qui se présente différemment dans chaque système.  Les travaux pratiques sont à rendre par la procédure informatique de dépot de compte-rendu.

Un polycopié accompagne ce cours.  Quelques transparents présentent les objectifs de ce cours, et un article publié aux Journées Francophones de Programmation Logique et par Contrainte le résume en 15 pages.

Bibliographie :
«La machine en logique», de P. Wagner (PUF) ; «Logique, réduction et résolution», de R. Lalement (Masson) ;
«La logique ou l'Art de raisonner», de Y. Delmas-Rigoutsos (Le Pommier) ;
«The Craft of Prolog», de R. O'Keefe (MIT Press) ; et
«Programming Languages Pragmatics», de M. Scott (Morgan Kaufmann).

semaine cours TD TP auto-évaluation
37 CM1 (lundi 10h15-12h15)
Introduction : prouver=calculer (constructivité, décidabilité, modèle de performance)

CM2 (vendredi 8h-10h)
Calcul des séquents (séquent, preuve)

Lire chapitres 1 et 2.1.1. 		TD1 (vendredi 14h-16h)
Introduction, premiers essais de programmation logique, arbre de recherche
Avoir compris le chapitre 1.

Savoir refaire les preuves en calcul des séquents du polycopié.
38
TD2 (lundi 10h15-12h15)
récursivité, coupure

Donner exercice sur arbre de recherche 		TP1 (vendredi 8h-10h et vendredi 14h-16h)
problème des familles, problème des tenues bien accordées 		Savoir construire l'arbre de recherche d'un programme Prolog simple.
39 CM3 (lundi 10h15-12h15)
Du calcul des séquents vers Prolog (preuves constructives, uniformes, clauses de Horn, unification comme élimination paresseuse des quantificateurs).

Lire chapitres 2.1.2 et 3.1 		Rendre résultat de l'exercice arbre de recherche

TD3  (vendredi 8h-10h)
Unification, modes.

TD4 (vendredi 14h-16h)
Listes (longueur, concaténation, ...)

40 CM4 (lundi 10h15-12h15)
Suite unification, arbre de recherche Prolog, coupure, trace.

Lire chapitre 2.1.3
TP2 (vendredi 8h-10h et vendredi 14h-16h)
Termes construits, listes. 		Savoir construire l'arbre de recherche d'un programme Prolog moins simple.  Voir les  questions posées sur ce sujet dans les examens passés.

Avoir compris le chapitre 2.1.
41 CM5 (lundi 10h15-12h15)
Programmation logique (graphe, automate, ...)

Lire chapitre 3.2.

CM6 (vendredi 8h-10h)
Analyse syntaxique (analyse descendante, DCG, récursivité gauche, Greibach, ...) 		TD5 (vendredi 14h-16h)
Analyse syntaxique

Donner exercice arbre de recherche

42
TD6 (lundi 10h15-12h15)
Analyse syntaxique (attribut, structure incomplète) 		TP3 (vendredi 8h-10h et vendredi 14h-16h)
Analyse syntaxique, manipulation de formules

À rendre avant le TD 6
43

Rendre le compte-rendu du TP3 le vendredi avant 8h.

TP4 (vendredi 8h-10h et vendredi 14h-16h)
Analyse syntaxique, manipulation de formules (suite)

À rendre avant le TD8. 		Savoir construire systèmatiquement un programme prolog par induction sur une structure (arbre, graphe, grammaire, etc).

Avoir compris le chapitre 3.
44
Vacances de Toussaint



45 CM7 (lundi 10h15-12h15)
La négation, la contrainte de différence (diff), domaines finis

CM8 (vendredi 14h-16h)
Pragmatique de la programmation par contrainte (position des contrainte, énumération) 		TD7 (vendredi 8h-10h)
Listes en différence, structures incomplètes

46
TD8 (lundi 10h15-12h15)
Programmation par contraintes 		TP5 (vendredi 8h-10h et vendredi 14h-16h)
Projet Contraintes 		Savoir construire systématiquement un programme logique par contrainte (créer les variables, les contraintes, énumérer les solutions).
47 CM9 (lundi 10h15-12h15)
Programmation par contraintes 		TD9 (vendredi 8h-10h)
Suivi du TP5-6

48

TP6 (vendredi 8h-10h et vendredi 14h-16h)

Rendre le compte-rendu du TP5-6 le vendredi suivant avant 8h. 		Sentir la complexité d'un jeu de contraintes.


Sujets d'examens : 2005-2006-1, 2005-2006-2, 2004-2005-1, 2004-2005-2, 2003-2004-1, 2003-2004-2, 2002-2003-1, 2002-2003-2.