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

Fakulta informatiky
podzim 2014
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. Pavel Troubil (cvičící)
Garance
doc. RNDr. Eva Hladká, Ph.D.
Katedra počítačových systémů a komunikací - Fakulta informatiky
Dodavatelské pracoviště: Katedra počítačových systémů a komunikací - Fakulta informatiky
Rozvrh
Čt 14:00–15:50 A318
  • Rozvrh seminárních/paralelních skupin:
PA163/01 každý sudý pátek 8:00–9:50 B117, H. Rudová
PA163/02 každý lichý pátek 8:00–9:50 B117, H. Rudová
PA163/03 každou lichou středu 12:00–13:50 B117, P. Troubil
Předpoklady
Při zařazení do skupiny cvičení založeném na logickém programování předpokládaná znalost základů výrokové a predikátové logiky, např. z předmětu IB101.
Znalost logického programování není podmínkou pro absolvování předmětu.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory
předmět má 22 mateřských oborů, zobrazit
Cíle předmětu
Absolvent bude vědět, jakým způsobem používat deklarativní přístup k řešení problémů prostřednictvím programování s omezujícími podmínkami.
Absolvent bude rozumět algoritmům používaným při řešení problémů prostřednictvím omezujících podmínek tak, aby mohl lépe navrhnout vhodný deklarativní model a kombinovat ho s vhodnými řídícími strategiemi. Absolvent se tak naučí různé typy propagačních a prohledávacích algoritmů.
Absolvent bude umět popsat řešení problému pomocí programování s omezujícími podmínkami, a to buď prostřednictvím logického programování s omezujícími podmínkami nebo prostřednictvím jazyka OPL (optimization programming language) v závislosti na výběru skupiny cvičení.
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, jazyk OPL (Optimization Progamming Language).
  • 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)/OPL programů v SICStus Prologu/ILOGu, 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í
Závěrečná písemná zkouška (cca 7 příkladů, 100 bodů). Předpokládané hodnocení je následující: A 90 a více, B 80-89, C 70-79, D 60-69, E 55-59. 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).
Na třech náhodných přednáškách budou oznámeny zadání bonusových příkladů, k jejich odevzdání budou oprávněni pouze studenti účastnící se přednášky. Za jedno bonusové zadání lze získat až 6 bodů. Každý student je povinen získat body alespoň 5 bodů z celkového počtu 18 bodů. Bonusové body lze přičíst k celkovému počtu získaných bodů za závěrečnou písemnou práci, získání bonusových bodů tedy usnadní získání lepšího hodnocení.
Znalosti logického programování s omezujícími podmínkami (CLP) jsou předpokládány pouze u seminární skupiny se zaměřením na CLP a podobně znalosti Optimization Programming Language (OPL)jsou předpokládány pouze u seminární skupiny se zaměřením na OPL.
Úč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
http://is.muni.cz/el/1433/podzim2014/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 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/podzim2014/PA163

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 22. 10. 2014 08:20, 43. (lichý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Více o informačním systému