Złożoność obliczeniowa

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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