Technologia Więzów

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

Aktualności

25.03.2021 zamieszczono trzecią listę zadań
08.03.2021 zamieszczono wskazówki do zadań
07.03.2021 zamieszczono drugą listę zadań
02.03.2021 zamieszczono pierwszą listę zadań
02.03.2021 zamieszczono zerową listę zadań
25.02.2021 zaktualizowano stronę kursu

Opis kursu

Moduł wprowadzający w zagadnienie technologii więzów. Celem jest zaprezentowanie tej nowej i szybko rozwijającej się metodologii programowania. Dzięki swej deklaratywności pozwala ona w krótkim czasie tworzyć złożone aplikacje rozwiązujące trudne zagadnienia z takich dziedzin jak np. optymalizacja, sztuczna inteligencja (rozpoznawanie obrazów) czy teoria programowania (analiza i synteza programów). W ramach wykładu zaprezentowane zostaną teoretyczne podstawy technologii więzów. Podczas zajęć laboratoryjnych rozwiązywane będą listy zadań zawierające zarówno ćwiczenia wprowadzające w zagadnienie technologii więzów jak i trudniejsze problemy, jakie można napotkać w praktyce.

Warunki zaliczenia

Ocena z grupy kursów zależy od liczby uzyskanych punktów z laboratorium za 1. i 2. listę zadań: 0 - 59 ocena 2.0, 60 - 71 ocena 3.0, 72 - 83 ocena 3.5, 84 - 95 ocena 4.0, 96 - 107 ocena 4.5, 108 - 120 ocena 5.0. Osoby, które uzyskały co najmniej 108 punktów mogą rozwiązać listę 3. na ocenę celującą.

Plan wykładu

Wykład prowadzony będzie na podstawie książki Krzysztofa Apta.

Przykłady problemów spełnienia ograniczeń (4g)
Programowanie ograniczeń (2g)
Zupełne solvery ograniczeń (4g)
Zgodność lokalna (4g)
Niezupełne solvery ograniczeń (6g)
Algorytmy propagacji ograniczeń (2g)
Przeszukiwanie (4g)
Uwagi praktyczne (4g)

Więzy globalne

Kategoria	SWI-Prolog	GNU Prolog	SICStus Prolog
Różne	all_different/1	fd_all_different/1	all_different/1
			all_different/2
	all_distinct/1		all_distinct/1
			all_distinct/2
			nvalue/2
			assignment/2
			assignment/3
			sorting/3
			keysorting/2
			keysorting/3
Sumowanie	sum/3		sum/3
	scalar_product/4		scalar_product/4
			scalar_product/5
Element	element/3	fd_element_var/3	element/3
Element		fd_element/3
Relacje	lex_chain/1		lex_chain/1
			lex_chain/2
	tuples_in/2	fd_relation/2	table/2
			table/3
			case/3
			case/4
		fd_relationc/2
	chain/2
Zliczanie	global_cardinality/2		global_cardinality/2
	global_cardinality/3		global_cardinality/3
			count/4
		fd_atmost/3
		fd_atleast/3
		fd_exactly/3
		fd_cardinality/2
		fd_cardinality/3
		fd_at_least_one/1
		fd_at_most_one/1
		fd_only_one/1
Szeregowanie	serialized/2
	cumulative/1		cumulative/1
	cumulative/2		cumulative/2
			cumulatives/2
			cumulatives/3
			multi_cumulative/2
			multi_cumulative/3
	circuit/1		circuit/1
			circuit/2
Rozmieszczanie			disjoint1/1
			disjoint1/2
	disjoint2/1		disjoint2/1
			disjoint2/2
			geost/2
			geost/3
			geost/4
Automaty	automaton/3		automaton/3
	automaton/8		automaton/8
			automaton/9

Literatura

Podstawowa

K. Apt. Principles of Constraint Programming. Cambridge University Press, 2010. (prezentacja)

Uzupełniająca

R. Dechter. Constraint Processing. Morgan Kaufmann Publishers, 2003.
K. Marriott, P.J. Stuckey. Programming with Constraints. An Introduction. The MIT Press, 1998.
Edited by F. Rossi, P. van Beek and T. Walsh. Handbook of Constraint Programming. Elsevier, 2006.

Inne przydatne pozycje

D. Maier. The Theory of Relational Databases.

Listy zadań na laboratorium

Termin	Zadania	Zadania
pierwsze zajęcia	tw_lista_0.pdf	wip_lab0.pdf
piąte zajęcia	tw_lista_1.pdf	wip_lab1.pdf
dziesiąte zajęcia	tw_lista_2.pdf	wip_lab2.pdf
piętnaste zajęcia	tw_lista_3.pdf (na ocenę celującą)	wip_lab3.pdf

Wskazówki do zadań

Poniżej podano klasy obiektów jakie wystarczą do rozwiązania poszczególnych zadań w języku C++.


Lista 1

	Zadanie 1
		IloIntVarArray

		real    0m0.134s
		user    0m0.171s
		sys     0m0.025s

	Zadanie 2
		IloIntVarArray
		IloIntArray

		real    0m0.039s
		user    0m0.016s
		sys     0m0.012s

	Zadanie 3
		IloIntVarArray
		IloIntArray
		IloIntExpr

		real    0m0.039s
		user    0m0.015s
		sys     0m0.013s

Lista 2

	Zadanie 1
		IloIntVarArray
		IloArray
		IloIntTupleSet
		IloAllowedAssignments
		IloCount

		real    0m0.032s
		user    0m0.017s
		sys     0m0.011s

	Zadanie 2 [1]

	Zadanie 3 [2]

Przy każdym zadaniu podano czasy działania programu zmierzone dostępnym w powłoce poleceniem time.

Ograniczenie geost można znaleźć między innymi w SICStus-Prolog i MiniZinc.

Ograniczenie automaton można znaleźć między innymi w SWI-Prolog, SICStus-Prolog. Odpowiadające mu ograniczenie regular można znaleźć w MiniZinc.

M. Carlsson, N. Beldiceanu, J. Martin. A Geometric Constraint over k-Dimensional Objects and Shapes Subject to Business Rules.
N. Beldiceanu, M. Carlsson, P. Flener, J. Pearson. On Matrices, Automata, and Double Counting, Constraints 18(1): 108-140, 2013.