|
|
|
||
|
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)
|
|
||
|
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)
|
|
||
|
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)
|
|
||
|
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)
|
|
||
|
lecture Last update: BARTAK/MFF.CUNI.CZ (31.03.2008)
|
|
||
|
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)
|
|
||
|
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)
|