PředmětyPředměty(verze: 809)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Programování s omezujícími podmínkami - NOPT042
Anglický název: Constraint Programming
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2014
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Další informace: http://ktiml.mff.cuni.cz/~bartak/podminky/
Garant: prof. RNDr. Roman Barták, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Optimalizace, Teoretická informatika
Anotace -
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.
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

Podmínky zakončení předmětu -
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (06.10.2017)

Pro úspěšné absolvování předmětu je potřeba získat zápočet a složit zkoušku. Zápočet není u zkoušky vyžadován. Zápočet se získá za vypracování zápočtového programu (constraintového modelu) s písemnou dokumentací.

Literatura
Poslední úprava: prof. RNDr. Roman Barták, Ph.D. (26.04.2007)

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

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.

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

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.

 
Univerzita Karlova | Informační systém UK