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.
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
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
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.