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 2018/2019):
pondělí 14:00 - 15:30, posluchárna S5 (Malá Strana, 2. patro)
Monday 14:00 - 15:30, lecture room S5 (Malá Strana, 2nd 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.

   
lecture
quiz

01.10. 2018

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

08.10. 2018

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

15.10. 2018

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

22.10. 2018

Introduction to consistency techniques. Node consistency (NC) and Arc consistency (AC)

29.10. 2018 Path consistency (PC)
05.11. 2018 Higher levels of consistencies
  N-ary constraints and global constraints
12.11. 2018 cancelled
19.11. 2018 Combining search and inference
26.11. 2018 cancelled
03.12. 2018 Incomplete and discrepancy search, branch-and-bound.
10.12. 2018 Over-constrained problems.
17.12. 2018 TBA
07.01. 2019 probably cancelled

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 2018/2019):
pondělí 15:40 - 17:10, 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.
Cancelled seminars: 12.-13.11. 2018, 26.-27.11.2018

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, partial 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.