Złożoność obliczeniowa

obowiązkowe

Teoria złożoności jest dziedziną komplementarną do algorytmiki. Podczas gdy algorytmika dostarcza najbardziej ekonomicznych rozwiązań problemów obliczeniowych, teoria złożoności tłumaczy, dlaczego niektóre problemy okazują się odporne na próby znalezienia dobrych algorytmów i klasyfikuje problemy obliczeniowe ze względu na ich trudność. Ocenia także walory różnych wzbogaceń tradycyjnego modelu obliczeń, jak obliczenia zrandomizowane, równoległe, interakcyjne, czy kwantowe.

1. Kodowanie obiektów przez słowa, problemy decyzyjne i funkcyjne.

2. Podstawowe modele obliczeń: maszyna Turinga, maszyna RAM, oraz obwody logiczne.

3. Złożoność czasowa i pamięciowa, pojęcie klasy złożoności.

4. Obliczalność w czasie wielomianowym i jej znaczenie praktyczne, nietrywialne przykłady.

5. Klasa NP, hipoteza P=/=NP, pojęcie redukcji, problemy NP-zupełne, problemy funkcyjne w NP.

6. Konstruktywne podejścia do trudnych problemów: algorytmy aproksymacyjne, efektywność względem wybranego parametru, średnia złożoność wielomianowa.

7. Obliczenia zrandomizowane, probabilistyczne klasy złożoności, generatory pseudolosowe i zagadnienie derandomizacji.

8. Klasa PSPACE i interakcyjne modele obliczeń: maszyny alternujące.

9. Funkcje jednokierunkowe i wykorzystanie trudnych problemów w kryptografii; dowody z zerową wiedzą.

10. Jak dowieść trudności: metoda przekątniowa, twierdzenia o hierarchii. Ograniczenie tej metody w stosunku do hipotezy P=/=NP.

11. Inne podejścia do dowodzenia trudności: złożoność informacyjna Kołmogorowa, zrandomizowane restrykcje w obwodach Boolowskich, złożoność komunikacyjna. Sukcesy i ograniczenia.

12. Fizyczne granice obliczalności, koncepcja obliczeń kwantowych.

Ostatnie trzy wykłady powinny zawierać pogłebiony materiał wybrany przez wykładowcę. Pogłebienie może dotyczyć zagadnień z głównego toku wykładu, ale też i spoza jego zakres. Do potencjalnych tematów należą:

- złożoność a kryptografia,

- złożoność a bazy danych,

- kody korekcyjne,

- problemy spełniania więzów (ang. constraint satisfaction problems),

- dowody interaktywne,

- gry z Naturą,

- PCP,

- złożoność kwantowa,

- złożoność parametryzowana,

- modele złożoności komunikacyjnej.

Ch. H. Papadimitriou, Złożoność obliczeniowa WNT, Warszawa 2002.

A.Arora, B.Barak Computational Complexity: A Modern Approach, Cambridge University Press, 2009 http://www.cs.princeton.edu/theory/complexity/

Oded Goldreich Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008 http://www.wisdom.weizmann.ac.il/~oded/cc-book.html

M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.

Wiedza.

1. Ma pogłębioną wiedzę z działów matematyki niezbędnych do studiowania informatyki (teoria złożoności) [K_W01].

2. Dobrze rozumie rolę i znaczenie konstrukcji rozumowań matematycznych [K_W02].

3. Rozumie kolejne poziomy ogólności: złożoność algorytmu, złożoność problemu, klasa złożoności.

4. Rozumie pojęcia złożoności czasowej i pamięciowej w modelu sekwencyjnym maszyny Turinga oraz odpowiedniki tych pojęć w modelu sieci logicznych.

5. Rozumie niejednorodny i probabilistyczny model obliczeń i zna zależność pomiędzy nimi.

6. Zna przykłady problemów w podstawowych klasach złożoności: NC, L, NL, P, NP, PSPACE, P/poly, BPP.

7. Rozumie pojęcia redukcji między problemami i pojęcie NP-zupełności.

8. Zna kryteria jakości algorytmów aproksymacyjnych.

9. Zna przykłady pozytywnego wykorzystania złożoności obliczeniowej w kryptografii.

Umiejętności.

1. Posiada umiejętność konstruowania rozumowań matematycznych [K_U01].

2. Potrafi wyrażać problemy obliczeniowe w języku matematyki [K_U02].

3. Projektuje algorytmy w podstawowych modelach obliczalności: maszynach Turinga, obwodach logicznych [K_U04].

4. Identyfikuje przynależność i trudność problemów obliczeniowych w stosunku do ważnych klas złożoności: NC, P, NP, PSPACE, wykorzystując ich różne charakteryzacje [K_U05].

5. Ma umiejętności językowe w zakresie informatyki zgodne z wymaganiami określonymi dla poziomu B2+ Europejskiego Systemu Opisu Kształcenia Językowego, w szczególności: identyfikuje główne i poboczne tematy wykładów, pogadanek, debat akademickich, dyskusji, czyta ze zrozumieniem i krytycznie analizuje teksty akademickie, zabiera głos w dyskusji lub debacie naukowej, streszcza ustnie informacje, wyniki badań, opinie i argumenty autora zawarte w tekście naukowym [K_U14].

6. Potrafi w naturalnych przypadkach rozpoznać problemy trudne obliczeniowo.

7. Potrafi w typowych przypadkach zakwalifikować dany problem do jednej z głównych klas złożoności.

8. Potrafi w typowych przypadkach zaprojektować aproksymacyjny lub zrandomizowany algorytm dla problemu, dla którego nie jest znane rozwiązanie deterministyczne.

Kompetencje.

1. Rozumie znaczenie złożoności obliczeniowej jako bariery dla standardowych technik informatycznych, wymuszającej znajdowanie innych technik.

2. Rozumie użyteczność informacji o złożoności obliczeniowej problemów o znaczeniu praktycznym.

3. Rozumie znaczenie hipotez teorii złożoności wśród priorytetowych problemów matematyki współczesnej.

Na ocenę końcową składają się: zadania domowe (40% = dwie serie po 20% każda), wyniki kolokwium (20 %) oraz wyniki egzaminu pisemnego (40 %). Dodatkowo, po każdym wykładzie opublikowany będzie prosty quiz w moodle; by być dopuszczonym do egzaminu w pierwszym terminie, należy uzyskać przynajmniej 75% punktów z testów. Do oceny w drugim terminie nie wlicza się kolokwium (ale wliczają się zadania domowe). Oddawane rozwiązania zadań powinny być napisane w języku angielskim.

W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.