Zpet na stránku Vyuka
Back to Teaching

POZADAVKY KE ZKOUSCE (2000)

---

Programování s omezujícími podmínkami (OPT042)
LS 2/0 Zk

Roman Barták, KTI

Zkusebni okruhy

1. Splnovani podminek
   1. Zakladni definice CSP
   2. Binarizace podmínek
   3. Algoritmy systematickeho prohledavani (generuj a testuj, backtracking) a jejich vylepseni (backjumping, backmarking)
   4. Konzistencni techniky (vrcholova a hranova konzistence, konzistence po ceste, k-konzistence, algoritmy AC-1, AC-3, AC-4, DAC, PC-1, PC-2, DPC-1, RPC)
   5. Propagace podminek (backtracking, forward checking, partial a full look ahead)
   6. Usporadani promennych a hodnot, backtrack-free prohledavani
   7. Omezeni prohledavani (algoritmy cycle-cutset, MACE)
   8. Heuristiky a stochasticke algoritmy (hill-climbing, min-conflicts, random-walk, MCRW, SDRW, Tabu, GSAT, GENET, lokální prohledavani)
2. Optimalizacni problemy
   1. Zakladni definice CSOP
   2. Algoritmus Branch & Bound
3. Prilis omezene systemy podminek
   1. Partial CSP a oslabeni problemu
   2. Hierarchie podminek
      1. Zakladni definice, komparatory, existence reseni, nemonotonie
      2. Principy reseni hierarchii (zjemnovaci metoda, lokalni propagace)
      3. Zakladni resici algoritmy

Terminy

Termin zkousky si se mnou domluvte osobne (mistnost c. 51, 3. patro, budova MFF UK, Malostranske namesti 2/25), e-mailem (bartak@kti.mff.cuni.cz) nebo telefonem (02-2191 4242 nebo 0603 428 336). Nejlepe vyhovuji utery/stredy dopoledne (behem cervna).

Základní literatura

• R. Bartak: Expertni systemy zalozene na omezujicich podminkach, Disertacni prace, MFF UK, 1997
• R. Bartak: Constraint Course, v priprave (predbezna PDF verze k dispozici u mne)
• J. Jaffar, M.J. Maher: Constraint Logic Programming: A Survey, in: Journal of Logic Programming, 1994, vol. 19/20. pp. 503 - 581
• E. Tsang: Foundations of Constraint Satisfaction, Academic Press, 1993
• P. Van Hentenryck: Constraint Satisfaction in Logic Programming, Logic Programming Series, The MIT Press, 1989
• Sborníky konferencí PACT a CP

Studijni materialy

Obsah prednasky je z vetsi casti (ale ne uplne) pokryt on-line vyukovymi materialy On-line Guide to Constraint Programming. Temer kompletni obsah prednasky lze ziskat u mne ve forme PDF souboru.