SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Constraint Programming - NOPT042
Title in English: 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 2019
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: English, Czech
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
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)

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.

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

To successfully complete the course, the student is required to do the exam and to get credit. The credit is not necessary for registration to exam. The credit is given for preparing an executable constraint model for an assigned problem together with written documentation.

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

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

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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html