Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Problemy spełniania więzów

Nazwa angielska (title in English): Constraint Satisfaction Problems
Prowadzący (lecturer): Michał Wrona
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): tak
Przedmiot zostal uaktualniony na biezacy rok (updated): nie
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

Wszyscy wiemy, że problem spełnialności rachunku zdań jest trudny (NP-zupełny). Wiemy jednak również, że 2SAT oraz HORN-SAT są wielomianowe. Czy można więc, przy jakimś naturalnym kryterium, wyodrębnić wszystkie wielomianowe przypadki? Okazuje się, że można. W 1978 Thomas J. Schaefer podał takie kryterium i udowodnił, że istnieje tylko sześć wielomianowych ograniczeń problemu spełnialności rachunku zdań i w każdym innym przypadku problem spełnialności jest NP-zupełny.

Problem spełnialności rachunku zdań jest problemem spełniania więzów (ang. Constraint Satisfaction Problem). Innymi znanymi nam z wykładu Języki formalne i złożoność obliczeniowa problemami spełniania więzów są kolorowanie i klika. Okazuje się, że na te wszystkie, tak różne problemy, można spojrzeć przez pryzmat pewnych niezmienników algebraicznych i logicznych. Nie mamy przecież wystarczająco dużo czasu (my --- ludzkość), aby przyglądać się nieskończeniu wielu możliwym problemom (w tym przypadku: problemom spełniania więzów). Chcemy znaleźć ogólne prawa przy których problem spełniania więzów jest prosty (powiedzmy: wielomianowy). Okazuje się, że takie, na razie częściowe, prawa w przypadku problemów spełniania więzów istnieją i są wyrażalne w językach algebry i logiki.

Problemy spełniania więzów są szeroką klasą problemów obliczeniowych, które grają istotną rolę m.in w:

  1. sztucznej inteligencji,
  2. teorii grafów,
  3. biologii obliczeniowej oraz
  4. lingwistyce obliczeniowej.

Problemy spełniania więzów są współczesną dziedziną informatyki w której wiele się dzieje i wiele jeszcze zostało do zrobienia.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):