Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Constraint Programming - NOPT042

Title:	Programování s omezujícími podmínkami
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2020
Semester:	winter
E-Credits:	5
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, Czech
Teaching methods:	full-time
Teaching methods:	full-time
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
Incompatibility :	NOPX042
Interchangeability :	NOPX042
Is incompatible with:	NOPX042
Is interchangeable with:	NOPX042

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

Last update: prof. RNDr. Roman Barták, Ph.D. (05.06.2017)

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.

Aim of the course -

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

Course completion requirements -

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

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.

Literature -

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

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

Teaching methods -

Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)

lecture

Requirements to the exam -

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

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

Syllabus -

Last update: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)

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.