zlozonosc-obliczeniowa

Złożoność obliczeniowa

Informacje ogólne

Typ:obowiazkowy

Kierunek:Informatyka studia drugiego stopnia

Specjalność:Algorytmy

Semestr:4

Wymiar zajęć:30 godzin wykładu, 30 godzin ćwiczeń

Punkty ECTS:7

Złożoność obliczeniowa, klasy złożoności, podstawowe własności, koszt determinizacji dla czasu i pamięci (twierdzenie Savitcha), zależność pomiędzy czasem i pamięcią, złożoność problemu przeciwnego (twierdzenie Immermana-Szelepcsenyi).
Klasy P i NP, certyfikaty, redukcja, problemy NP-zupełne.
Problemy funkcyjne z klasy FNP.
Problemy zupełne w innych klasach.
Algorytmy, przybliżone dla problemów NP-zupełnych.
Algorytmy probabilistyczne, klasy RP, ZPP, BPP.
Protokoły interakcyjne, protokoły z wiedzą zerową.
Algorytmy równoległe, klasy złożoności dla algorytmów równoległych, przykłady.
Problemy funkcyjne z klasy FNP.
Algorytmy probabilistyczne i przybliżone.

egzamin