Złożoność obliczeniowa: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Slusarek (dyskusja | edycje)
54 edycje
Slusarek (dyskusja | edycje)
54 edycje
Nie podano opisu zmian
Linia 7: Linia 7:


== Autor ==
== Autor ==
 
Maciej Ślusarek
Maciej Ślusarek


== Zawartość: ==
== Zawartość: ==


Złożoność obliczeniowa w modelu Maszyny Turinga, warianty modelu (off-line, wielotaśmowa, niedeterministyczna).
*Złożoność obliczeniowa w modelu Maszyny Turinga, 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 poszczególnych modelach. Problem decyzyjny w notacji "naturalnej", kodowanie problemu.
*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 poszczególnych modelach
**problem decyzyjny w notacji "naturalnej", kodowanie problemu.


Klasy złożoności, relacje między klasami. Twierdzenia o przyspieszaniu. Twierdzenia o hierarchii pamięciowej i czasowej. Domkniętość ze względu na dopełnienie.
*Klasy złożoności
**relacje między klasami
**twierdzenia o przyspieszaniu
**twierdzenia o hierarchii pamięciowej i czasowej
**domkniętość ze względu na dopełnienie.


Redukcje (wielomianowa, logarytmiczna, Turinga). Pojęcie zupełności. Klasa NP, NP-zupełność, twierdzenie Cooka-Levina.
*Redukcje
**rodzaje: wielomianowa, logarytmiczna, Turinga
**pojęcie zupełności
**klasa NP, NP-zupełność, twierdzenie Cooka-Levina.


Dowody NP-zupełności,  techniki konstrukcji redukcji wielomianowych, analiza złożoności podproblemów, problemy liczbowe i silna NP-zupełność.
*Dowody NP-zupełności
**techniki konstrukcji redukcji wielomianowych
**analiza złożoności podproblemów
**problemy liczbowe i silna NP-zupełność.


Algorytmy aproksymacyjne. Schematy aproksymacyjne.
*Algorytmy aproksymacyjne. Schematy aproksymacyjne.


Dolne ograniczenia na aproksymowalność. L-redukcje. Klasa MAXSNP, problemy MAXSNP-zupełne. Charakteryzacja klasy NP przez weryfikatory. Twierdzenie PCP i przykłady zastosowania do nieaproksymowalności.
*Dolne ograniczenia na aproksymowalność
**L-redukcje
**klasa MAXSNP, problemy MAXSNP-zupełne
**charakteryzacja klasy NP przez weryfikatory
**twierdzenie PCP i przykłady zastosowania do nieaproksymowalności


Algorytmy probabilistyczne. Rozpoznawanie liczb pierwszych. Probabilistyczne klasy złożoności.
*Algorytmy probabilistyczne
**rozpoznawanie liczb pierwszych.
**robabilistyczne klasy złożoności.


Modele obliczeń równoległych, klasy NC i RNC.
*Modele obliczeń równoległych, klasy NC i RNC.


Klasy złożoności pamięciowej. Struktura klasy LOGSPACE. Hierarchia wielomianowa. Problemy zupełne w klasie PSPACE. Alternacja i gry.
*Klasy złożoności pamięciowej
**struktura klasy LOGSPACE
**hierarchia wielomianowa
**problemy zupełne w klasie PSPACE
**alternacja i gry.


Złożoność zliczania. Klasa #P.
*Złożoność zliczania. Klasa #P.


Kryptografia a złożoność. Funkcje jednokierunkowe. Protokoły interaktywne. IP=PSPACE.
*Kryptografia a złożoność
**funkcje jednokierunkowe
**protokoły interaktywne
**IP=PSPACE.


==Literatura==
==Literatura==

Wersja z 23:05, 11 cze 2006

Forma zajęć

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

Opis

Sylabus

Autor

Maciej Ślusarek

Zawartość:

  • Złożoność obliczeniowa w modelu Maszyny Turinga, 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 poszczególnych modelach
    • problem decyzyjny w notacji "naturalnej", kodowanie problemu.
  • Klasy złożoności
    • relacje między klasami
    • twierdzenia o przyspieszaniu
    • twierdzenia o hierarchii pamięciowej i czasowej
    • domkniętość ze względu na dopełnienie.
  • Redukcje
    • rodzaje: wielomianowa, logarytmiczna, Turinga
    • pojęcie zupełności
    • klasa NP, NP-zupełność, twierdzenie Cooka-Levina.
  • Dowody NP-zupełności
    • techniki konstrukcji redukcji wielomianowych
    • analiza złożoności podproblemów
    • problemy liczbowe i silna NP-zupełność.
  • Algorytmy aproksymacyjne. Schematy aproksymacyjne.
  • Dolne ograniczenia na aproksymowalność
    • L-redukcje
    • klasa MAXSNP, problemy MAXSNP-zupełne
    • charakteryzacja klasy NP przez weryfikatory
    • twierdzenie PCP i przykłady zastosowania do nieaproksymowalności
  • Algorytmy probabilistyczne
    • rozpoznawanie liczb pierwszych.
    • robabilistyczne klasy złożoności.
  • Modele obliczeń równoległych, klasy NC i RNC.
  • Klasy złożoności pamięciowej
    • struktura klasy LOGSPACE
    • hierarchia wielomianowa
    • problemy zupełne w klasie PSPACE
    • alternacja i gry.
  • Złożoność zliczania. Klasa #P.
  • Kryptografia a złożoność
    • funkcje jednokierunkowe
    • protokoły interaktywne
    • IP=PSPACE.

Literatura

1. Złożoność obliczeniowa, Christos H. Papadimitriou, Wydawnictwa Naukowo-techniczne, 2002.

2. Wprowadzenie do teorii automatów, języków i obliczeń, John E. Hopcroft, Jeffrey D. Ullman, Wydawnictwo naukowe PWN, 1994.

3. Computers and Intractability A Guide to the Theory of NP-completeness, Michael R. Garey, David S. Johnson, Freeman, 1979.

4. Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company, 1997.

Moduły

Literatura uzupełniająca

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa&oldid=1820”