PA163 Programovaní s omezujícími
podmínkami
podzim 201 3
Základní informace
Web předmětu: na IS
3 průsvitky průběžně na ISu (interaktivní osnova, učební materiály) 3 elektronicky dostupné materiály k jednotlivým částem přednášky
Ukončení předmětu:
písemná práce pro každý řádný termín
& cca 7 otázek: přehledové, srovnávací, algoritmy, pojmy, příklady (model) S vzor písemné práce dostupný na webu předmětu * hodnocení: 1 00 bodů (A 90, B 80, C 70, D 60, E 55)
cca 30 bodů: příklad(y) návrhu modelu problému - probíráno ve cvičení
Omezující podmínky v navazujících přednáškách:
M PA1 67 Rozvrhování
Hana Rudová, Omezující podmínky, 1 8. září 201 3
2
Organizace předmětu
Literatura
Dechter, R. Constraint processing. Morgan Kaufmann Publishers, 2003.
M http://www.ics.uci.edu/~dechter/books/
M Tsang, E. Foundations of Constraint Satisfaction.
Academic Press, 1993.
3 na webu dostupný plný text knihy
M http://cswww.essex.ac.uk/Research/CSP/edward/FCS.html
M Barták, R. On-line guide to constraint programming.
M http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/
M Barták, R. Programovaní s omezujícími podmínkami, přednáška na MFF UK.
M http://kti.ms.mff.cuni.cz/~bartak/podminky/index.html
M Elektronické materiály viz web předmětu
Hana Rudová, Omezující podmínky, 18. září 201 3 3 Organizace předmětu
Přehled přednášky
M Problém splňování podmínek. Příklady a modelování. Složitost. Grafová reprezentace podmínek.
Základní typy konzistence a algoritmy: hranová, po cestě, k-konzistence.
M Konzistence pro nebinární podmínky: doménová konzistence, konzistence mezí, globální podmínky.
M Směrová konzistence a algoritmy. Šířka grafu podmínek a polynomiální CSP.
Stromové prohledávací algoritmy: backtracking, pohled dopředu, pohled zpět, neúplné prohledávání.
M Lokální prohledávání.
M Optimalizace, soft omezení: modely, algoritmy. Opakování v příkladech
Hana Rudová, Omezující podmínky, 1 8. září 201 3
4
Organizace předmětu
Cvičení
3 Cíl
«• praktické procvičení příkladů s omezujícími podmínkami u počítačů Účast na cvičeních povinná
3 v případě více nezjedná absence nutné zpracovat doplňující příklady při vysokém počtu absencí na cvičení předmět absolvovat nelze
M Znalosti logického programování výhodou (nikoliv podmínkou) možné získat např. v předmětech
M IB01 5 Neimperativní programování
M IB101 Úvod do logiky a logického programování
M PB016 Úvod do umělé inteligence
předpokládá se znalost základů výrokové a predikátové logiky
«• např. z předmětu IB101 Úvod do logiky a logického programování
Hana Rudová, Omezující podmínky, 18. září 201 3 5 Organizace předmětu
Cvičení: obsah
«• Logické programování s omezujícími podmínkami
úvod do Prologu M CLP program 3 globální podmínky 3 implementace podmínek M modelování 3 prohledávání
Optimization Programming Language OPL IBM ILOGu
3 úvod do programovacího jazyka OPL
3 modelování pomocí globálních omezujících podmínek
3 modelování pro zvýšení efektivity
3 řešení rozvrhovacích problémů pomocí omezujících podmínek 3 dekompozice problémů
Hana Rudová, Omezující podmínky, 18. září 201 3 6 Organizace předmětu
Software: SICStus Prolog
Doporučovaná implementace Prologu
Dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html
3 Komerční produkt
dostupná i licence pro instalace na domácí počítače studentů
IDE pro SICStus Prolog SPIDER
M aktuální verze 4.2.3
± IDE dostupné až s verzí SICStus 4.1.3 http://www.sics.se/sicstus/spider používá Eclipse SDK
3 Podrobné informace dostupné přes web předmětu
stažení SICStus Prologu (sw + licenční klíče) 3 pokyny k instalaci (SICStus Prolog, Eclipse, Spider)
Hana Rudová, Omezující podmínky, 18. září 201 3 7 Organizace předmětu
Software: IBM ILOG CPLEX Optimization Studio
M Dostupné ke stažení ve Studijních materiálech
Licence dostupná výhradně pro studenty předmětu! Šířením porušíte licenci.
„The Optimization Programming Language (OPL) provides a natural mathematical description of optimization models. Using high-level syntax for mathematical models produces substantially simpler and shorter code than general-purpose programming languages, reducing the effort and improving the reliability of application development, upgrades, and maintenance. Its powerful syntax supports all expressions needed to model and solve problems using both mathematical programming and constraint programming."
viz http://www-01.i bm.com/software/comme rce/opti mi zati on/model i ng/
^ Tutoriál ve Studijních materiálech:
Detailed Scheduling in IBM ILOG CPLEX Optimization Studio with IBM ILOG CPLEX CP Optimizer, WSW14077-USEN-01, 28 stran. IBM Corporation, 201 0.
Hana Rudová, Omezující podmínky, 1 8. září 201 3
8
Organizace předmětu
OPL: příklad
using cp;
dvar int+ gas; dvar int+ chloride;
maxi mi z e
40 * gas + 50 * chloride subject to {
gas + chloride <= 50;
3 * gas +   4 * chloride <= 180;
chloride <= 40;
};
Hana Rudová, Omezující podmínky, 1 8. září 201 3
9
Organizace předmětu