Złożoność obliczeniowa 1000-218bZO
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.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
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.
Literatura
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.
Uwagi
|
W cyklu 2024Z:
Zajęcia na przedmiocie odbywają się w języku angielskim |
W cyklu 2025Z:
Zajęcia na przedmiocie odbywają się w języku angielskim |
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: