Programowanie ograniczeń

Stacks Image 10406
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

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

  • Zaliczenie na podstawie rozwiązanych list zadań laboratoryjnych.
  • Osoby, które chcą uzyskać ocenę celującą, muszą rozwiązać dodatkową ostatnią listę zadań.

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)

Literatura

Podstawowa

Uzupełniająca

Inne przydatne pozycje

Listy zadań na laboratorium

Narzędziem używanym do rozwiązywania zadań jest darmowy i otwarty MiniZinc.

  1. The MiniZinc Handbook.

Podobnie jak w latach poprzednich, dopuszczam używania innych dostępnych narzędzi takich jak na przykład:
  • IBM ILOG Constraint Programming (OPL, C++, java)
  • język Prolog (swi-prolog, gnu-prolog, sisctus prolog, …)
  • OR-Tools (python, c++, c#, java)

Listy zadań:

Wskazówki do zadań

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

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

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

Poniżej porównano dostępne ograniczenia globalne, które są dostępne w wybranych implementacjach języka Prolog:
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
  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