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 2014 to 2018
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, 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

Opinion survey results Examination dates 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)

Literature - Czech

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

Teaching methods -

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

lecture

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.