Sylabus
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ů.
2. Algoritmy lokálního prohledávání: metoda největšího stoupání, minimalizace konfliktů, náhodná procházka, Tabu seznam, GSAT, Genet.
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.
Anotace
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.