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

Program

  • 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.

Sposób zaliczenia

egzamin

Literatura

  • C. Papadimitriou, Computational Complexity, Addison- Wesley, 1994.