Předmět Programování s omezujícími podmínkami (NOPT042)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NOPT042 - Programování s omezujícími podmínkami, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základní používané techniky používané při úlohách splňování podmínek
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.
Literatura
R. Dechter: Constraint Processing, Elsevier Science, 2003K. Marriott, P.J. Stuckey: Programming with Constraints: An Introduction, The MIT Press, 1998E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993
Garant
prof. RNDr. Roman Barták, Ph.D.