logo
v2.11.0 (6131)

Cours scientifiques - CSC_3F007_EP : Relational programming

Domaine > Informatique.

Descriptif

Ce cours présente le paradigme de la programmation relationnelle, basé sur la programmation logique par contraintes (CLP), depuis ses fondements en logique du premier ordre (FOL) faisant de la programmation essentiellement une tâche de modélisation utilisant des variables et des relations mathématiques, vers ses diverses applications en IA symbolique, bases de données déductives, représentation des connaissances, résolution de problèmes, optimisation combinatoire, démonstration automatique de théorèmes, et traitement du langage naturel.

Objectifs pédagogiques

Depuis les débuts de la programmation logique basée sur les formules de la logique des clauses de Horn jusqu'au Saint Graal de la programmation déclarative, par la simple modélisation du problème par des variables et des contraintes mathématiques, les étudiants apprendront à utiliser un dialecte récent de Prolog avec des contraintes sur les structures de données des termes logiques du premier ordre, des entiers et des nombres réels. L'équilibre entre programmation déclarative et efficacité nous amènera à examiner le fonctionnement interne des compilateurs Prolog basés sur la machine abstraite de Warren, tant pour la résolution de contraintes que pour la résolution de clauses. Plusieurs séances illustreront l'efficacité de cette approche pour la représentation des connaissances, le calcul formel, et la résolution d'exemples concrets de problèmes NP-difficiles.

Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vous devez avoir validé l'équation suivante : UE CSC_2F003_EP

Prerequisite:CSC_2F003_EP

Format des notes

Numérique sur 20

Littérale/grade américain

Pour les étudiants du diplôme Programmes d'échange internationaux

Vos modalités d'acquisition :

Note du cours: moyenne des 5 meilleurs sur 6 TDs

(cette année il n'y aura pas d'examen écrit final).

Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vos modalités d'acquisition :

Note du cours: moyenne des 5 meilleurs sur 6 TDs

(cette année il n'y aura pas d'examen écrit final).

 

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)
    L'UE est acquise si note finale transposée >= D
    • Crédits ECTS acquis : 3 ECTS

    La note obtenue rentre dans le calcul de votre GPA.

    Programme détaillé

    Les séances pratiques utiliseront un système Prolog moderne appelé SWI Prolog. Les étudiants sont invités à installer SWI Prolog sur leur ordinateur portable avant la première séance. Nous recommandons l'utilisation de brew avec la commande shell.

    brew install swi-prolog

    Notez cependant que nous utiliserons un petit sous-ensemble de prédicats Prolog, principalement pour la manipulation de termes et de listes, et que nous utiliserons le pack modeling.pl pour les contraintes arithmétiques entières et réelles, plutôt que les prédicats arithmétiques évaluables Prolog. Ce paquet peut être installé avec la commande shell.

    swipl pack install modeling

    Les transparents des cours et les corrigés des TD seront disponibles ici à chaque séance.

    Un nouveau polycopié du cours seront disponibles au début du cours.

    Le pack modeling.pl est accompagnée d'une documentation sur les contraintes et les métaprédicats utilisés pour la modélisation dans ce cours. Le manuel complet SWI-Prolog va bien au-delà de ce qui sera enseigné dans ce cours et doit être consulté principalement pour les prédicats de manipulation de listes et de fermes.

    La présence aux cours et aux TD est obligatoire. Les TD se dérouleront sur votre ordinateur portable, en utilisant SWI-Prolog et le pack modeling.pl. Vous trouverez les questions du TD dans un fichier Prolog, à compléter et télécharger sur le moodle à la fin du TD (pour éviter toute frustration, un bonus sera accordé pour les réponses supplémentaires téléchargées après la date limite jusqu'au week-end).

    Notes : moyenne de vos 5 meilleurs TD sur 6

    C1, TD1 : Termes du premier ordre, unification, bases de données déductives dans Datalog, calcul symbolique en Prolog

    C2, TD2 : Sémantique opérationnelle de Prolog par réécriture de buts, concurrence, traitement de listes

    C3, TD3 : Langages de programmation logiques à contraintes, résolution de contraintes linéaires sur les nombres réels, programmes CLP(R)

    C4, TD4 : résolution de contraintes sur les entiers, programmes CLP(T, Z) pour la résolution de problèmes d'optimisation combinatoire

    C5, TD5 : Résolution de contraintes booléennes, contraintes réifiées, programmes CLP(T, B, Z) pour la résolution de problèmes d'ordonnancement disjonctif NP-difficiles

    C6, TD6 : Théories logiques, décidabilité des structures, sémantique formelle de CLP(X), démonstration automatique de théorèmes.

     

    Mots clés

    programmation logique, programmation par contraintes; résolution de contraintes; algorithmes de recherche; modélisation à base de contraintes

    Méthodes pédagogiques

    Cours magistraux suivis de travaux dirigés sur ordinateurs personnels à remettre à la fin de chaque séance et comptant pour la note finale.

    Support pédagogique multimédia

    Oui

    Veuillez patienter