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 2024/2025:
Monday (Monday) 15:40 - 17:10, lecture room S4 (3rd floor, Malá Strana)

Toto je předběžný program, který může být během roku upraven. Jazyk kurzu bude domluven na první přednášce (předběžně očekávám angličtinu).
This is a preliminary program that can be modified during the semester. The course language will be decided during the first lecture (I assume English).

   
lecture
quiz

30.09. 2024

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

Search algorithms for constraint satisfaction. Generate and Test. Local search algorithms (HC, MC, RW, TS, GSAT, GENET).
14.10. 2024 Systematic search methods, look-back algorithms (backtracking, backjumping, backmarking).
21.10. 2024

Canceled!
 
 
28.10. 2024 Canceled!
 
 
04.11. 2024 Introduction to consistency techniques. Node consistency (NC) and Arc consistency (AC)
11.11. 2024 Path consistency (PC)
18.11. 2024 Canceled!
 
 
25.11. 2024 Higher levels of consistencies 
02.12. 2024 Global constraints
09.12. 2024 Combining search and inference
16.12. 2024 Incomplete and discrepancy search, branch-and-bound.
06.01. 2025 Over-constrained problems.
  Constraint modeling.
  Constraint models for planning problems.
  A Theoretical Look at CSP (Jakub Bulín)

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):

Informace o cvičeních jsou uvedeny na stránkách cvičícího. Dále uváděné informace se týkají cvičení z předchozích let a dávají příklady CP modelů v jazyce SICStus Prolog.

A practical view of Constraint Programming including programming exercises. Information is availabe at dedicated web pages. Information listed further is from previous years, there are some examples of constraint models in SICStus Prolog.

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 (Exam):

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.

During exam, I will ask questions from all topics covered by lectures. The exam dates will be published before the exam period and students register to exams via SIS.
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.