Programování s omezujícími podmínkami / Constraint Programming
NOPT042, 2/2 Z+Zk, zimní semestr

Roman Barták, KTIML


Zdroje  |  Přednáška   |  Cvičení |  Zkouška  |  Kontakt

Programování s omezujícími podmínkami představuje jeden nejbližších přístupů, které počítačová věda udělala ke Svatému grálu programování: uživatel popíše problém a počítač ho vyřeší.

Constraint Programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.

Eugene C. Freuder, Constraints 1997


Zdroje (References):

Výborným doplňkovým zdrojem informací k přednášce je kniha R. Dechter: Constraint Processing, Morgan Kaufmann, 2003. Materiály ke knize jsou dostupné na webu.

Pro pokročilejší studenty je vhodným zdrojem informací kniha F. Rossi, P. van Beek, T. Walsh (eds.): Handbook of Constraint Programming, Elsevier, 2006.

V českém jazyce zatím není dostupná žádná kniha, v přípravě je kniha Omezující podmínky.


Přednáška-Lectures (ZS 2016/2017):
pondělí 15:40 - 17:10, posluchárna S4 (Malá Strana, 2. patro)
Monday 15:40 - 17:10, lecture room S4 (Malá Strana, 2nd floor)

Toto je předběžný program, který může být během roku upraven. Přednáška i cvičení běží v angličtině.
The course is given in English.

03.10. 2016

Introduction, history, context, and applications of CP. Definition of a CSP and its features. Binarization of constraints.

10.10. 2016

Search algorithms for constraint satisfaction. Generate and Test. Local search algorithms (HC, MC, RW, TS, GSAT, GENET).

17.10. 2016

Systematic search methods, look-back algorithms (backtracking, backjumping, backmarking).

24.10. 2016

cancelled

31.10. 2016 Introduction to consistency techniques. Node consistency (NC) and Arc consistency (AC)
07.11. 2016 cancelled
14.11. 2016 Path consistency (PC)
21.11. 2016 Higher levels of consistencies
N-ary constraints and global constraints
28.11. 2016 Combining search and inference
05.12. 2016 cancelled
12.12. 2016 Incomplete and discrepancy search, branch-and-bound.
19.12. 2016 Over-constrained problems.
09.01. 2017 Some surprise at the end

Slajdy v českém jazyce z předchozích let.

Úvod, historické souvislosti, ukázky aplikací, vlastnosti omezujících podmínek. Definice CSP. Binarizace podmínek.

Přehled algoritmů pro řešení podmínek prohledáváním. Metoda generuj a testuj. Algoritmy lokálního prohledávání (HC, MC, RW, TS)

Algoritmy lokálního prohledávání (GSAT, GENET). Úvod do systematického prohledávání do hloubky (backtracking).

Úvod do systematického prohledávání do hloubky (backtracking). Metody pohledu zpět u algoritmů prohledávání do hloubky (backjumping, backmarking).

Úvod do konzistenčních technik, vrcholová konzistence (NC). Hranová konzistence (AC).
Konzistence po cestě (PC), její směrové a omezené verze.  
Vyšší stupně konzistence a jejich vztah ke složitosti problému.
Zobecněná hranová konzistence. Globální podmínky.
Spojení prohledávání a konzistenčních technik, metody pohledu dopředu. Strukturálně založené algoritmy (CC, MACE).
Prohledávací heuristiky a prohledávání s diskrepancemi. Další větvící strategie. Optimalizační problémy.
Modelování a řešení příliš omezených problémů a problémů s preferenčními podmínkami, hierarchie podmínek.

Praktická cvičení, Exercises (ZS 2016/2017):
pondělí 17:20 - 18:50, laboratoř SW2 nebo (alternativně) úterý 15:40 - 17:10, laboratoř SW1
Tuesday 15:40 - 17:10, computer lab SW1

A practical view of Constraint Programming including programming exercises.

A brief introduction to Prolog (database of facts and rules, queries, unification, backtracking, lists, cut, negation, blacboard)

Introduction to CLP.

Constraint Modelling 1 (letter puzzle, table/element constraints, 4-queens).
Constraint Modelling 2 (knapsack, assignment.
Constraint Modelling 3 (home movement, seesaw, Golomb ruler).
Constraint Modelling 4 (toaster, parial digest, double digest).
Constraint Modelling 5 (sky observatory)
Programming search procedures.
Design of custom constraints.

Slajdy v českém jazyce z předchozích let.

Úvod do Prologu (Prologovská databáze, dotazy, pravidla)

Úvod do Prologu (unifikace, seznamy, řez, negace, blackboard)

Úvod do CLP

První kroky v CLP: aritmetické, logické a tabulární podmínky

Úvod do modelování problémů (přiřazovací problém, 4-královny).
Modelování problémů (problém baťohu a jednoduché rozvrhování, toustovač).
Modelování problémů (houpačka, přiřazování, Golombovo pravítko).
Návrh vlastních "globálních" podmínek.
Návrh primitivních podmínek, reifikace. Informace k zápočtovým programům.
Návrh prohledávacích algoritmů.
Neúplné prohledávací algoritmy a branch-and-bound.

Na cvičení budeme používat SICStus Prolog, který je dostupný v laboratořích. Studenti MFF UK si mohou nainstalovat kopii SICStus Prologu na vlastní počítače (je potřeba nejprve prostudovat studentskou licenci a po té e-mailem požádat vyučujícího o zaslání kódu pro download systému a instalační klíč - v mailu je potřeba uvést požadovanou platformu).

Pro zápočet je potřeba navrhnout constraintový model v SICStus Prologu pro kombinatorický problém dle vlastní volby (zadání musí předem schválit cvičící) a k němu napsat krátkou dokumentaci. Upřesnění zadání je zde.

For credit from excercices the student need to write a constraint model in SICStus Prolog for a selected combinatorial problem (must be approaved by the teacher) and accompany it by the text documentation. For details see here.


Zkouška:

Zkoušena bude látka probraná na přednášce a cvičních, podrobnosti a termíny budou vypsány před zkouškovým obdobím. Na zkoušku se zapisuje prostřednictvím Studijního informačního systému.


Kontakt:
 

prof. RNDr. Roman Barták, Ph.D.

Katedra teoretické informatiky a matematické logiky
Matematicko-fyzikální fakulta Univerzity Karlovy

Malostranské nám. 2/25, 118 00 Praha 1
Czech Republic

e-mail: bartak (AT) ktiml.mff.cuni.cz
tel: +420 951 554 242

V případě potřeby je možné domluvit individuální konzultace k přednášce, případně témata projektů, bakalářských či diplomových prací vycházejících z témat přednášky.

Samozřejmě veškeré komentáře k přednášce, hlášení chyb, nejasných pasáží apod. jsou vítány.