PA163 Programování s omezujícími
podmínkami
podzim 2010
Základní informace
JS> Web predmetu: na IS
-fc průsvitky průběžně na ISu (interaktivní osnova, učební materiály) ä- elektronicky dostupné materiály k jednotlivým částem prednášky
UkonCení predmetu:
a písemná práce pro každý rádný termín
cca 6 otázek: přehledové, srovnávací, algoritmy, pojmy, príklady (model)
vzor písemné práce dostupný na webu predmetu
hodnocení: 100 bodu (A 90, B 80, C 70, D 60, E 55)
cca 30 bodu: príklad(y) návrhu modelu problému - probíráno ve cvicení
& Omezující podmínky v jiných prednáškach:
PA167 Rozvrhování -i- IB013 Logické programování I
Hana Rudová, Omezující podmínky, 21. zárí 2010
2
Organizace predmetu
Literatura
JS> Dechter, R. Constraint processing. Morgan Kaufmann Publishers, 2003. ± http://www.ics.uci.edu/~dechter/books/
-i* Tsang, E. Foundations of Constraint Satisfaction.
Academic Press, 1993.
& na webu dostupný plný text knihy
-i- http://cswww.essex.ac.uk/Research/CSP/edward/FCS.html
& Barták, R. On-line guide to constraint programming.
a http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/
Barták, R. Programovaní s omezujícími podmínkami, prednáška na MFF UK. -i* http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html
-í* Elektronické materiály viz web predmetu
Hana Rudová, Omezující podmínky, 21. zárí 2010 3 Organizace predmetu
Přehled přednášky
C- Problém splňování podmínek. Príklady a modelování. Složitost. Grafová reprezentace podmínek.
& Základní typy konzistence a algoritmy: hranová, po ceste, k-konzistence.
& Konzistence pro nebinární podmínky: doménová konzistence, konzistence mezí, globální podmínky.
-i* Smerová konzistence a algoritmy. Šírka grafu podmínek a polynomiální CSP.
Stromové prohledávací algoritmy: backtracking, pohled dopredu, pohled zpet, neúplné prohledávání.
& Lokální prohledávání.
& Optimalizace, soft omezení: modely, algoritmy.
Hana Rudová, Omezující podmínky, 21. zárí 2010
4
Organizace predmetu
Cvičení: pokyny
Cíl: praktické procvičení příkladů s omezujícími podmínkami u počítačů
& Účast na cvičeních povinná
* v případe více než jedné absence nutné zpracovat doplňující příklady & Používaný software: SICStus Prolog
A komercní produkt
J> zakoupena licence pro instalace na domácí pocítace studentu A dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html doporucená verze: 4.1.*
verze 3.* má odlišné rozhraní rady omezujících podmínek verze 4.0.* obsahuje problematické chyby podrobné informace na webu predmetu
Hana Rudová, Omezující podmínky, 21. zárí 2010
5
Organizace predmetu
Cvičení: obsah
C Znalosti logického programování výhodou (nikoliv podmínkou)
možné získat napr. v předmětech
-i- IB013 Logické programování I.
IB101 Úvod do logiky a logického programování -i- PB016 Úvod do umělé inteligence
* Logické programování s omezujícími podmínkami
-fc úvod do Prologu
ä- CLP program
a globální podmínky
J* implementace podmínek
ä- modelování
a prohledávání
Hana Rudová, Omezující podmínky, 21. zárí 2010 6 Organizace predmetu