Programování
s omezujícími podmínkami
Constraint Programming
NOPT042,
2/2 Z+Zk, zimní semestr
Roman
Barták, KTIML
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
|
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 |
Higher levels of consistencies |
|
|
25.11.
2024 |
Global constraints |
|
|
02.12.
2024 |
Combining search and inference |
|
|
09.12.
2024 |
Incomplete and discrepancy search, branch-and-bound. |
|
|
16.12.
2024 |
Over-constrained problems. |
|
|
06.01. 2025 |
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š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.
|
|
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.
|
|