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

Fakulta informatiky
podzim 2009
Rozsah
2/1. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. Mgr. Hana Rudová, Ph.D. (přednášející)
RNDr. Dalibor Klusáček, Ph.D. (pomocník)
Garance
prof. RNDr. Václav Matyáš, M.Sc., Ph.D.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Rozvrh
Po 12:00–13:50 B410
  • Rozvrh seminárních/paralelních skupin:
PA163/01: každý lichý čtvrtek 10:00–11:50 B116, H. Rudová
PA163/02: každý sudý čtvrtek 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
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í omezujících podmínek.
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.
Výukové metody
Výuka probíhá jednak ve formě přednášek a dále ve formě cvičení (2 hodiny každé 2 týdny). Výuka přednášek je zejména orientována na výklad algoritmů a jejich praktické použití pro řešení problémů v oblasti programování s omezujícími podmínkami. Výuka cvičení probíhá u počítačů, kde je kladen hlavní důraz na realizaci CLP(FD) programů v SICStus Prologu, a to buď samostatně nebo často modifikací existujícího kódu. Součástí cvičení jsou i domácí úkoly, jejiž řešení včetně řešení všech příkladů realizovaných na cvičení je vystaveno na webu předmětu.
Metody hodnocení
Předmět je absolvován složením úspěšné písemné práce ziskem alespoň 55 z celkového počtu 100 bodů (A: 100-90, B 89-80, C 79-70, D 69-60, E59-55). Přibližně třetinu bodů je možné získat za napsání modelu omezujících podmínek pro dané problémy. V písemné práci jsou uvedeny následující typy otázek: přehledové, srovnávací, algoritmy, pojmy, příklady. Účast na cvičeních je povinná, v případě více než jedné neomluvené absence jsou zadány doplňující příklady v rozsahu odpovídajícím množství zameškaných cvičení, jejichž úspěšné zpracování je nezbytnou podmínkou absolvování předmětu.
Navazující předměty
Informace učitele
https://is.muni.cz/el/1433/podzim2009/PA163/index.qwarp
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 2007, podzim 2008, 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.