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 2017/2018):
pondělí 14:00 - 15:30, posluchárna S9 (Malá Strana, 1. patro)
Monday 14:00 - 15:30, lecture room S9 (Malá Strana, 1st floor)

Toto je předběžný program, který může být během roku upraven. Volba jazyka (čeština nebo angličtina) bude provedena na první přednášce.
The course can be given in English, the decision will be done at the first lecture.

02.10. 2017

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

09.10. 2017

cancelled

 
16.10. 2017

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

23.10. 2017

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

30.10. 2017 Introduction to consistency techniques. Node consistency (NC) and Arc consistency (AC)
06.11. 2017 cancelled
13.11. 2017 Path consistency (PC)
20.11. 2017 Higher levels of consistencies
27.11. 2017 N-ary constraints and global constraints
04.12. 2017 cancelled
11.12. 2017 Combining search and inference
18.12. 2017 Incomplete and discrepancy search, branch-and-bound.
08.01. 2018 Over-constrained problems.

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í 15:40 - 17:10, laboratoř SW2 nebo (alternativně) úterý 15:40 - 17:10, laboratoř SU1
Tuesday 15:40 - 17:10, computer lab SU1

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.