PA163 Programování s omezujícími podmínkami

Fakulta informatiky
podzim 2007
Rozsah
2/1. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. Mgr. Hana Rudová, Ph.D. (přednášející)
Garance
prof. RNDr. Václav Matyáš, M.Sc., Ph.D.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Rozvrh
Čt 8:00–9:50 B204 a každé liché úterý 10:00–11:50 X Datový projektor, každé liché úterý 10:00–11:50 B116
  • Rozvrh seminárních/paralelních skupin:
PA163/02: každé sudé úterý 10:00–11:50 X Datový projektor, každé sudé úterý 10:00–11:50 B116, H. Rudová
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 19 mateřských oborů, zobrazit
Cíle předmětu
Předmět se primárně zabývá problematikou splňování omezujících podmínek, je zde ale prezentována i řada obecně použitelných algoritmů, např. z oblasti umělé inteligence nebo optimalizací. Předmět lze také doporučit zájemcům o deklarativní styl programování a studentům se zájmem o nové možnosti při popisu problémů pomocí omezení.


Metody propagace podmínek a prohledávání jsou zastoupeny klasickými i nejnovějšími algoritmy. Je ukázáno modelování jednodušších příkladu i reálných problémů prostřednictvím programování s omezujícími pomínkami.


Cvičení jsou věnována praktickému vyzkoušení příkladů logického programování s omezujícími podmínkami u počítačů. Znalosti z logického programování přitom nejsou podmínkou pro absolvování předmětu.

Osnova
  • Problém splňování podmínek. Úvod do modelování problémů. Reprezentace podmínek. Složitost.
  • Algoritmy a konzistence: hranová, po cestě. Řešení nebinárních podmínek: k-konzistence, obecná hranová konzistence, konzistence mezí, globální podmínky. Směrové varianty, šířka grafu podmínek a polynomiální problémy.
  • Stromové prohledávání: backtracking, pohled dopředu, pohled zpět, neúplné algoritmy. Lokální prohledávání.
  • Optimalizační a příliš podmíněné problémy: přístupy k řešení a algoritmy.
  • Řešení dynamických a distribuovaných problémů s podmínkami.
  • Logické programování s omezujícími podmínkami.
  • Modelování a využití v reálných aplikacích.
Literatura
  • DECHTER, Rina. Constraint processing. San Francisco: Morgan Kaufmann Publishers, 2003, xx, 481 s. ISBN 1-55860-890-7. info
  • Edward, Tsang. Foundations of constraint satisfaction. Academic Press Ltd., 1993.
Metody hodnocení
Písemná práce pro každý řádný termín, představuje společnou přípravu pro všechny studenty, cca 5 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady.
Ústní zkouška ve stejný den jako písemná práce, příprava na individuální otázky, během zkoušky diskuse nad písemnou prací.
Opravný termín pouze jako ústní zkouška.
Navazující předměty
Informace učitele
http://is.muni.cz/elearning/warp.pl?fakulta=1433;obdobi=3724;kod=PA163;qurl=/el/1433/podzim2007/PA163/index.qwarp
Doplňující literatura viz: Barták, Roman. On-line guide to constraint programming. http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.