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. Złożoność drobnoziarnista, złożoność parametryzowana, hipoteza czasu wykładniczego.

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.

Pięć prac domowych i egzamin pisemny. Do dopuszczenia w pierwszym terminie wymagane jest co najmniej 40% z prac domowych. Wymogiem zaliczenia przedmiotu jest uzyskanie przynajmniej 35% z samego egzaminu oraz przynajmniej 50% łącznie z egzaminu i prac domowych; ocena zależy od łącznego wyniku z egzaminu i prac domowych. W pierwszym terminie sumowanie odbywa się według proporcji (60% prace domowe + 40% egzamin), w drugim maksimum z proporcji jak w pierwszym terminie oraz (40% prace domowe + 60% egzamin).

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.