Sylabus	Omezující podmínky
Úvod | Sylabus | Zdroje | Přednáška | Zkoušky

Název přednášky: Programovaní s omezujícími podmínkami
Označení: OPT042
Rozsah: 2/0 Zk - letní semestr
Vyučující: Roman Barták

Historické souvislosti, vazba na další obory, praktické aplikace, možnosti a meze CP, základní vlastnosti omezujících podmínek.

Definice CSP, binární CSP, binarizace podmínek (duální kódování, kódování se skrytou proměnnou).

Řešení podmínek prohledáváním, metoda generuj a testuj, backtracking, backjumping, dynamický backtracking, backmarking, iterative broadening, limited discrepancy search.

Konzistenční techniky, vrcholová a hranová konzistence, konzistence po cestě, k-konzistence, (i,j)-konzistence, singleton konzistence. Algoritmy NC, AC1, AC3, DAC, PC1, PC2 ,DPC, RPC, SC.

Filtrační techniky v prohledávání, algoritmy FC, PLA, LA.

Techniky lokálního prohledávání, algoritmy HC, MC, RW, Tabu Search, GSAT, Genet

Řešení optimalizačních problémů, metoda branch & bound.

Příliš omezené problémy a jejich formalizace Partial CSP, Probabilistic CSP, Fuzzy CSP, Valued CSP, Weighted CSP, Semiring CSP, hierarchie podmínek. Algoritmy řešení hierarchií: DeltaStart, DeltaBlue, SkyBlue, Indigo, Houria, IHCS, projekční algoritmus.

Modelování reálných úloh, tipy a triky, realizace.

© 2001 Roman Barták

Omezující podmínky