Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (05.06.2017)
Přednáška podává přehled o technikách splňování omezujících podmínek. Zaměřena je na algoritmy splňování
podmínek a to jak algoritmy prohledávací (prohledávání do hloubky, lokální prohledávání) tak algoritmy propagační
(hranová konzistence, konzistence po cestě). Probíráno je také řešení příliš omezených problémů a různé
modelovací techniky. Předpokládány jsou základní programovací znalosti Prologu.
Poslední úprava: 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.
Cíl předmětu -
Poslední úprava: T_KTI (23.05.2008)
Naučit základní používané techniky používané při úlohách splňování podmínek
Poslední úprava: 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.
Podmínky zakončení předmětu -
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (08.08.2022)
Pro úspěšné absolvování předmětu je potřeba získat zápočet a složit zkoušku. Zápočet je udělován za domácí úkoly (constraintové modely) zadávané v rámci cvičení.
Poslední úprava: 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.
Literatura -
Poslední úprava: 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
Poslední úprava: 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
Metody výuky -
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)
přednáška
Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)
lecture
Požadavky ke zkoušce -
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (06.10.2017)
Zkouška se skládá z písemné přípravy a ústní části. Požadavky odpovídají sylabu předmětu.
Poslední úprava: 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.
Sylabus -
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)
1. Úvod: historické souvislosti, vazba na další obory, aplikační oblasti, definice problému splňování omezujících podmínek, binarizace problémů.
3. Algoritmy prohledávání do hloubky: backtracking, backjumping, dynamický backtracking, backmarking, prohledávání s diskrepancemi, neúplné prohledávání.
4. Konzistenční techniky: vrcholová a hranová konzistence, konzistence po cestě a algoritmy pro jejich dosažení, obecné konzistenční pojmy.
5. Kombinace propagace podmínek a prohledávání: kontrola dopředu, (častěný/úplný) pohled dopředu, heuristiky pro uspořádání proměnných a hodnot, prohledávání bez navracení.
6. Optimalizační problémy, metody větví a mezí. Příliš omezené problémy a jejich modely.
7. Globální podmínky.
8. Modelování problémů a praktické realizace.
Poslední úprava: 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.