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

Fakulta informatiky
podzim 2006
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
St 10:00–11:50 B204 a každý sudý pátek 9:00–10:50 X Datový projektor, každý sudý pátek 9:00–10:50 B116
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 zabývá problematikou splňování 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čů.
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.
Informace učitele
http://www.fi.muni.cz/~hanka/cp
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 2007, 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.