Personal tools

Złożoność obliczeniowa

From Studia Informatyczne

Spis treści

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Złożoność obliczeniowa to dziedzina informatyki teoretycznej zajmująca się klasyfikacją języków formalnych ze względu na ilość zasobu — czasu i pamięci — potrzebnego do rozpoznawania języka. Ponieważ język formalny jest abstrakcyjnym odpowiednikiem problemu algorytmicznego, teoria ta dostarcza narzędzi do szacowania trudności obliczeniowej takich problemów. Niniejszy kurs zapoznaje uczestników z najważniejszymi rezultatami badań dotyczącymi klas złożoności, ich własności i wzajemnych zależności a także omawia wynikające z tych faktów wnioski dotyczące praktycznych problemów algorytmicznych.

Sylabus

Autorzy

  • Maciej Ślusarek - Uniwersytet Jagielloński
  • Przemysław Broniek - Uniwersytet Jagielloński
  • Grzegorz Gutowski - Uniwersytet Jagielloński
  • Jan Jeżabek - Uniwersytet Jagielloński

Wymagania wstępne

  • Matematyka dyskretna
  • Algorytmy i struktury danych
  • Języki, automaty i obliczenia.

Zawartość

  • Złożoność obliczeniowa w modelu maszyny Turinga:
    • zasoby obliczeniowe
    • warianty modelu: off-line, wielotaśmowa, niedeterministyczna
  • Inne modele dla złożoności:
    • maszyna RAM, kryterium jednostajne i logarytmiczne
    • obwody logiczne
    • zależności między funkcjami złożoności w różnych modelach
  • Klasy złożoności obliczeniowej:
    • klasy złożoności czasowej i pamięciowej
    • twierdzenia o liniowym przyspieszaniu i kompresji pamięci
    • relacje między klasami, twierdzenie Savitcha i dopełnienia klas
    • twierdzenia o hierarchii czasowej i pamięciowej
  • Redukcje i zupełność:
    • rodzaje redukcji: wielomianowa, logarytmiczna, Turinga
    • pojęcie zupełności
    • klasa NP, NP-zupełność, twierdzenie Cooka-Levina
    • charakteryzacja klasy NP w języku logiki
  • Dowody NP-zupełności i analiza złożoności problemu:
    • przykłady redukcji i techniki ich konstrukcji
    • analiza złożoności podproblemów
    • problemy liczbowe i silna NP-zupełność
  • Algorytmy aproksymacyjne:
    • wersje optymalizacyjne problemów decyzyjnych
    • przykłady algorytmów aproksymacyjnych
    • schematy aproksymacyjne
  • Dolne ograniczenia na aproksymowalność:
    • L-redukcje
    • klasa MAXSNP, problemy MAXSNP-zupełne
    • charakteryzacja klasy NP przez weryfikatory
    • twierdzenie PCP i przykłady jego zastosowania
  • Algorytmy probabilistyczne:
    • probabilistyczne klasy złożoności
    • rozpoznawanie liczb pierwszych
    • generowanie bitów losowych
  • Obliczenia równoległe:
    • modele obliczeń równoległych
    • klasy złożoności równoległej
    • P-zupełność
    • równoległość i randomizacja
  • Problemy funkcyjne i złożoność zliczania:
    • klasy FP, FNP, TFNP
    • klasa #P i twierdzenie Valianta
    • klasa \oplus\textsc{P}
  • Pamięć logarytmiczna i hierarchia wielomianowa:
    • klasy L, NL i coNL
    • twierdzenie Immermana-Szelepcsényi'ego
    • klasy coNP i DP
    • maszyny alternujące
    • hierarchia wielomianowa
  • Pamięć wielomianowa:
    • klasa PSPACE, problemy zupełne
    • gry
    • problemy zwięzłe i złożoność wykładnicza
  • Kryptografia a złożoność:
    • funkcje jednokierunkowe
    • protokoły interaktywne
    • IP=PSPACE

Literatura

  1. C.H. Papadimitriou, Złożoność obliczeniowa, Wydawnictwa Naukowo-Techniczne, Warszawa 2002.
  2. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa 1994.
  3. M.R. Garey, D.S. Johnson, Computers and Intractability A Guide to the Theory of NP-completeness, Freeman, 1979.
  4. M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.

Moduły

  1. Obliczenia w modelu maszyny Turinga (test)
  2. Inne modele dla złożności (test)
  3. Klasy złożoności obliczeniowej (test)
  4. Redukcje i zupełność (test)
  5. Problemy NP-zupełne (test)
  6. NP-zupełność jako narzędzie analizy problemu (test)
  7. Algorytmy aproksymacyjne (test)
  8. Schematy aproksymacji i klasa MAXSNP (test)
  9. Twierdzenie PCP i nieaproksymowalność (test)
  10. Algorytmy probabilistyczne (test)
  11. Obliczenia równoległe (test)
  12. Problemy funkcyjne i złożoność zliczania (test)
  13. Pamięć logarytmiczna i hierarchia wielomianowa (test)
  14. Pamięć wielomianowa i złożoność wykładnicza (test)
  15. Kryptografia a złożoność (test)