SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Constraint Programming - NOPX042
Title: Programování s omezujícími podmínkami
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: English
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NOPT042
Additional information: http://ktiml.mff.cuni.cz/~bartak/podminky/
Guarantor: prof. RNDr. Roman Barták, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Optimalization, Theoretical Computer Science
Pre-requisite : {NXXX007, NXXX008, NXXX009, NXXX038, NXXX039, NXXX040, NXXX067, NXXX069}
Incompatibility : NOPT042
Interchangeability : NOPT042
Is incompatible with: NOPT042
Is interchangeable with: NOPT042
Annotation -
The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency). Solving over-constrained problems is also discussed as well as some modeling techniques are covered. Basic knowledge of programming language Prolog is expected.
Last update: Barták Roman, prof. RNDr., Ph.D. (05.06.2017)
Aim of the course -

The course gives a survey of constraint satisfaction techniques. The focus is on algorithms for constraint satisfaction, such as search algorithms (depth-first search and local search) and propagation algorithms (arc and path consistency). Solving over-constrained problems is also discussed as well as some modeling techniques are covered.

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)
Course completion requirements -

To successfully complete the course, the student is required to do the exam and to get credit. The credit is given for preparing constraint models during practical exercises.

Last update: Barták Roman, prof. RNDr., Ph.D. (08.08.2022)
Literature -

R. Dechter: Constraint Processing, Elsevier Science, 2003

K. Marriott, P.J. Stuckey: Programming with Constraints: An Introduction, The MIT Press, 1998

E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993

N. Zhou, H. Kjellerstrand, J. Fruhman: Constraint Solving and Planning with Picat, Springer, 2015

Last update: Barták Roman, prof. RNDr., Ph.D. (08.08.2022)
Teaching methods -

lecture

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)
Requirements to the exam -

The exam consists of a written preparation and an oral part. The requirements are given by the course syllabus.

Last update: Barták Roman, prof. RNDr., Ph.D. (06.10.2017)
Syllabus -

1. Introduction: history and relation to other research areas, application areas, definition of a Constraint Satisfaction Problem and binary problems.

2. Local search techniques: hill climbing, min-conflicts, random walk, Tabu Search, GSAT, Genet.

3. Tree search techniques: backtracking, backjumping, dynamic backtracking, backmarking, limited discrepancy search, incomplete search.

4. Consistency techniques; node, arc, and path consistencies and algorithms to achieve them, general consistency notions.

5. Combining constraint propagation and search: forward checking, (partial/full) look ahead, variable and value ordering heuristics, backtrack-free search.

6. Optimization problems, branch and bound. Over-constrained problems and their models.

7. Global constraints.

8. Modelling problems and constraint programming in practice.

Last update: Barták Roman, prof. RNDr., Ph.D. (26.04.2007)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html