Constraint Logic Programming

Code:

M.EIC023

Acronym:

PLR

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2023/2024 - 2S

Active?	Yes
Web Page:	https://moodle.up.pt/course/view.php?id=1751
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M.EIC	13	Syllabus	1	-	6	39	162

Teaching language

Suitable for English-speaking students
Obs.: Suitable for english-speaking students

Objectives

This course addresses the Logic Programming (LP) and Constraint Programming (CP) paradigms, specifically Constraint Logic Programming (CLP).

The LP paradigm presents a declarative approach to programming, based on formal reasoning processes, more appropriate to the resolution of certain types of problems.

CLP allows for an efficient approach to constraint satisfaction problems and optimization problems, modeling them in a direct and elegant manner.

Learning outcomes and competences

At the end of this course, students should:

- Be familiar with declarative programming paradigms, namely LP and CLP.

- Identify classes of problems where LP and CLP are particularly relevant.

- Possess abstract reasoning skills and the ability to solve problems in a declarative manner.

- Be able to correctly apply LP and CLP techniques.

- Be able to build full Prolog applications, with and without constraints.

Working method

Presencial

Program

1. Logic Programming (LP)
   
   
   
   • Propositional and predicate logic. Horn clauses. Unification. Resolution.
   
   
   • Clauses. Predicates. Facts. Queries. Rules. Logic variables. Instantiation.
   
   
   • LP and databases. Recursion. Lists. Trees. Symbolic expressions.
   
   
   • Computation model. Unification. Abstract interpreter. Traces. Search trees. Negation.
   
   
   
   


2. The Prolog Language
   
   
   
   • Language Elements.
   
   
   • Execution model. Backtracking. Termination.
   
   
   • Arithmetic. Iteration. Term processing. Operators.
   
   
   • Meta- and extra-logical predicates.
   
   
   • Non-deterministic programming. Incomplete structures. Meta-interpreters. Search techniques.
   
   
   
   


3. Constraint Programming
   
   
   
   • Combinatorial problems. Mathematical, linear, and integer programming.
   
   
   • Constraints, satisfaction, propagation, and consistency maintenance.
   
   
   • Constraints in Boolean, finite and real domains.
   
   
   • Optimization. Solution search. Complete and incomplete methods.
   
   
   • Languages.
   
   
   • Constraint Programming using Google OR-Tools and IBM ILOC CP Optimizer
   
   
   
   


4. Constraint Logic Programming (CLP)
   
   
   
   • Modeling problems in CLP.
   
   
   • CLP using SICStus Prolog.
   
   
   
   

Mandatory literature

Sterling, Leon; The Art of Prolog. ISBN: 0-262-69163-9
Marriot, Kim; Programming with constraints. ISBN: 0-262-13341-5
Clocksin, W. F.; Programming in prolog. ISBN: 0-387-58350-5

Complementary Bibliography

Torres, Delfim Fernando Marado; Introdução à programação em lógica. ISBN: 972-8021-93-3
Bratko, Ivan; Prolog programming for artificial intelligence. ISBN: 0-201-40375-7
O.Keefe, Richard A.; The craft of Prolog. ISBN: 0-262-15039-5
Stuart Russell, Peter Norvig; Artificial intelligence. ISBN: 978-0-13-207148-2

Teaching methods and learning activities

Classes are used both for the presentation of the main (constraint) logic programming concepts, accompanied by the discussion of practical examples as well as to solve programming exercises and assist students on their practical assignments.

Software

SICStus Prolog - http://www.sics.se/sicstus/
Google OR-Tools
IBM ILOG CP Optimizer

keywords

Technological sciences > Engineering > Knowledge engineering
Physical sciences > Computer science > Programming
Physical sciences > Mathematics > Mathematical logic
Physical sciences > Computer science > Cybernetics > Artificial intelligence

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Teste	35,00
Trabalho laboratorial	65,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	60,00
Frequência das aulas	42,00
Trabalho laboratorial	60,00
Total:	162,00

Eligibility for exams

Enrolled students are admitted to exam if they do not exceed the allowed number of non-attendance to lab classes (maximum 25% of non-attendance).

Calculation formula of final grade

Final Grade = 35% * MT + 50% * TP + 15% * A

MT: Mini-test grade (min. 7 values)
TP: Practical assignment global grade (min. 7 values)
A: Practical assignment presentations global grade

Special assessment (TE, DA, ...)

All assessment components are required to all students. Students enrolled using special frequency modes, without obligation to attend to the practical classes, must arrange with the teachers appropriate consultation and evaluation sessions. They should also attend the scheduled evaluation points.

Classification improvement

The improvement of classification can only be obtained in the next edition of the course.