FI:PA163 Omezující podmínky - Informace o předmětu
PA163 Programování s omezujícími podmínkami
Fakulta informatikypodzim 2011
- 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. Luděk Matyska, CSc.
Katedra počítačových systémů a komunikací – Fakulta informatiky - Rozvrh
- St 12:00–13:50 B410 a každý sudý čtvrtek 12:00–13:50 A104
- Předpoklady
- Vzhledem k obsahu cvičení: doporučená znalost základů výrokové a predikátové logiky, např. z předmětu IB101 Úvod do logiky a logického programování.
- 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á 27 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í 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ů.
- 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.
- 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). V písemné práci jsou uvedeny následující typy otázek: přehledové, srovnávací, algoritmy, pojmy, příklady (přibližně třetinu bodů je možné získat za napsání modelu omezujících podmínek pro dané problémy). Úč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. Při vysokém počtu absencí na cvičení předmět absolvovat nelze.
- Navazující předměty
- Informace učitele
- https://is.muni.cz/auth/el/1433/podzim2011/PA163/index.qwarp
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (podzim 2011, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2011/PA163