Informační systém Masarykovy univerzity 

Informace o předmětu

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

Fakulta informatiky
podzim 2005

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

Pá 8:00–9:50 X Datový projektor, Pá 8:00–9:50 B204 a každý lichý pátek 10:00–11:50 B116, každý lichý pátek 10:00–11:50 X Datový projektor

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á 7 mateřských oborů, zobrazit

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í a hybridní 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.
• Barták, Roman. On-line guide to constraint programming. http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html

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.

The written exam for each regular date. It is a preparation for all students, it includes about 5 questions: outline of certain part, comparison of some approaches, algorithms, terminology and its explanation, examples.
The oral exam in the same day as the written exam, preparation on individual questions, discussion about written exam.
Irregular dates as oral exam only.

Informace učitele

http://www.fi.muni.cz/~hanka/cp

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 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013.

---

• Statistika zápisu (podzim 2005, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2005/PA163

---