logo
v2.11.0 (5976)

Cours scientifiques - CSC_3F007_EP : Relational programming

Domaine > Informatique.

Descriptif

This course presents the relational programming paradigm, also called Constraint Logic Programming (CLP), from its logical foundations for programming with mathematical variables and relations in a declarative fashion, to its relevance to symbolic artificial intelligence with various applications in deductive databases, knowledge representation, symbolic computation, combinatorial optimisation, automated deduction and natural language processing.

Objectifs pédagogiques

From the early days of Logic Programming based on Horn clause logic formulae, towards the holy grail of declarative programming by simply modelling the problem at hand by mathematical variables and constraints, the students will learn how to use a recent dialect of Prolog with constraints over the data structures of first-order logic terms, integers and real numbers. The balance between declarative programming and efficiency will lead us into looking at how things work internally both for constraint solving and for clause resolution in Prolog compilers based on the Warren Abstract Machine. Several sessions will illustrate the efficiency of this approach to solving practical instances of real-life NP-hard problems.

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 :

Grades: mean of your best 5 over 6 TDs.

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

Vos modalités d'acquisition :

Grades: mean of your best 5 over 6 TDs.

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é

    The practical sessions will use a modern Prolog system called SWI Prolog. The students are invited to install SWI Prolog on their own laptop before the first session. We recommend to use brew with shell command

    brew install swi-prolog

    Note however that we will use a small subset of Prolog predicates, mainly for term and list manipulation, and will use pack modeling for integer and real arithmetic constraints, instead of Prolog evaluable arithmetic predicates. This pack can be installed with shell command

    swipl pack install modeling

    Bibliography:

    The slides of the lectures and solutions of the TPs are made available here at each session and should be sufficient to study this course.
    Those lecture notes can be consulted although they go a bit beyond what will be presented in this course and also in a different order, starting from the theory rather than with the examples as we will do in the course to finish with the theory.
    The pack modeling comes with documentation of the constraints and comprehension metapredicates used for modeling in this course.
    The extensive SWI-Prolog manual goes well beyond what will be taught in this course, and should be consulted mainly for term and list manipulation predicates.

    Attendance to the lectures and TPs is mandatory. The TPs will be done on your own laptop using SWI-Prolog and pack modeling. You will find the questions of the TP in the Prolog file to complete in the assignment activity.

    Grades:

    50% mean of your best 5 over 6 TPs
    50% final written examination

    Lecture notes File
    4 novembre (15.30-17.30 room info 32) 8 nov. (10.15-12.15 BEM-1022004)
    C1: Introduction to Prolog: deductive databases in first-order logic, term unification, symbolic computation

    TP1: deductive databases, symbolic differentiation, constraints over the real numbers


    Slides of Lecture 1 File

    TP1 Initiation to Prolog: deductive databases, symbolic differentiation, constraints over the real numbersAssignment
    *14 Nov. (8.00-10.00 BEM 1022004)* 15 Nov. (10.15-12h15 info 35)
    C2: List processing in Prolog, reversibility

    TP2: Path finding in a map


    Slides of Lecture 2 File

    TP2Assignment
    18 November (info 32) 22 Nov. (info 36)
    C3: From Prolog to CLP(R): linear constraints over the real numbers using Fourier's and Simplex algorithms

    TP3: production planning and cost benefit analysis in CLP(R)


    Slides of Lecture 3 File

    TP3Assignment
    25 November (BEM 1022004 15.30-17h30) 29 November (info 32)
    C4: Constraint propagation with domain filtering algorithms in CLP(Z)

    TP4: Programming a constraint solver over the integers and solving disjunctive scheduling problems


    Slides of lecture 4 File

    TP4Assignment
    2 Dec (BEM 1022004), 6 Dec. (info 32)
    C5: Meta-interpretation, search procedures, computational complexity, search heuristics .

    TP5: Heuristics for the N-queens. Meta-interpreter for complete search and theorem proving in group theory


    Slides of Lecture 5 File

    TP5Assignment
    9 Dec (15.30-17.30 BEM 1022004) 10 Dec. (10.15-12.15 info 31)
    C6 Formal semantics of CLP(X) languages and abstract interpretation

    TD6: Natural language processing in concurrent Prolog for querying a database


    Slides of Lecture 6 File

    TP6Assignment
    Friday 20 Dec 14h-16h Amphi Carnot - Final written examination
    Written examination.

    All printed documents are allowed.
    Any electronic device prohibited.
    For preparing the examination, revising the slides of the lectures, the TPs and the exams of the previous years is sufficient.

    The subject of the examination will be self-contained.

    Written examination 2024 with solution File

    Written examination 2023 with solution File

    Written examination 2022 with solution File

    Written examination 2021 with solution File

    Online Examination 2020 (due to Covid crisis) File

    Written examination 2019 with solution File

     

    Mots clés

    logic programming; constraint programming; constraint solving; search algorithms; constraint-based modeling

    Méthodes pédagogiques

    Lecture course followed by experimental work on personal computer

    Support pédagogique multimédia

    Oui

    Veuillez patienter