Programování s omezujícími podmínkami

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.