Přednáška

Omezující podmínky

 

Úvod | Sylabus | Zdroje | Přednáška | Zkoušky

 

Letní semestr 2007/2008
úterý 10.40-12.10 v S5 (Malá Strana, 2. patro)

19.2. 2008 Úvod, historické souvislosti, ukázky aplikací, vlastnosti omezujících podmínek, možnosti a meze CP. Definice CSP. Binarizace podmínek.
26.2. 2008

Přehled algoritmů pro řešení podmínek prohledáváním, metoda generuj a testuj. Algoritmy lokálního prohledávání: HC, MC, MCRW, SDRW, Tabu search, GSAT, GENET, simulované žíhání

4.3. 2008

Algoritmy systematického prohledávání: backtracking, backjumping, dynamický backtracking, backmarking. Neúplné prohledávací techniky (BBS, IB, DBS, CS).

11.3. 2008

Prohledávání s diskrepancemi (LDS, ILDS, DDS). Úvod do konzistenčních technik, vrcholová konzistence (NC). Hranová konzistence (AC), algoritmy hranové konzistence AC-1, AC-2, AC-3, AC-4, AC-3.1, AC-2001.

18.3. 2008 Odpadá!
25.3. 2008 Směrová hranová konzistence (DAC). Konzistence po cestě (PC), reprezentace podmínek maticemi, algoritmy PC-1, PC-2, DPC.
1.4. 2008 Omezená konzistence po cestě (RPC). k-konzistence, (i,j)-konzistence, inverzní konzistence, bodová konzistence. Hledání řešení bez navracení. Zobecněná hranová konzistence a konzistence okrajů.
8.4. 2008 Spojení prohledávání a konzistenčních technik (FC, PLA, LA, MAC), heuristiky pro výběr proměnné a hodnoty. Metody cycle-cutset a MACE.
15.4. 2008 Optimalizační problémy. Modelování příliš omezených problémů (soft constraints). Řešení hierarchií podmínek.
22.4. 2008 Globální podmínky.
29.4. 2008 Omezující podmínky v praxi: modelování a řešení reálných problémů.
6.5. 2008 Ukázky programování SICStus Prolog. Benchmarky.
13.5. 2008 Odpadá!
20.5. 2008 Odpadá!
Tento rozvrh je předběžný a je možné (a také pravděpodobné), že bude v průběhu semestru modifikován.

© 2007 Roman Barták

Omezující podmínky