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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
m Zastępowanie tekstu - "\textsc{" na "\text{"
 
(Nie pokazano 4 wersji utworzonych przez jednego użytkownika)
Linia 9: Linia 9:
=== Autorzy ===
=== Autorzy ===
    
    
*Maciej Ślusarek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
*Maciej Ślusarek - Uniwersytet Jagielloński
*Przemysław Broniek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
*Przemysław Broniek - Uniwersytet Jagielloński
*Grzegorz Gutowski - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
*Grzegorz Gutowski - Uniwersytet Jagielloński
*Jan Jeżabek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
*Jan Jeżabek - Uniwersytet Jagielloński


===Wymagania wstępne===
===Wymagania wstępne===


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


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


*Złożoność obliczeniowa w modelu maszyny Turinga
*Złożoność obliczeniowa w modelu maszyny Turinga:
**zasoby obliczeniowe
**zasoby obliczeniowe
**warianty modelu: off-line, wielotaśmowa, niedeterministyczna
**warianty modelu: off-line, wielotaśmowa, niedeterministyczna


*Inne modele dla złożoności
*Inne modele dla złożoności:
**maszyna RAM, kryterium jednostajne i logarytmiczne
**maszyna RAM, kryterium jednostajne i logarytmiczne
**obwody logiczne
**obwody logiczne
**zależności między funkcjami złożoności w różnych modelach
**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 obliczeniowej:
**klasy złożoności czasowej i pamięciowej
**klasy złożoności czasowej i pamięciowej
**twierdzenia o liniowym przyspieszaniu i kompresji pamięci
**twierdzenia o liniowym przyspieszaniu i kompresji pamięci
Linia 35: Linia 37:
**twierdzenia o hierarchii czasowej i pamięciowej
**twierdzenia o hierarchii czasowej i pamięciowej


*Redukcje i zupełność
*Redukcje i zupełność:
**rodzaje redukcji: wielomianowa, logarytmiczna, Turinga
**rodzaje redukcji: wielomianowa, logarytmiczna, Turinga
**pojęcie zupełności
**pojęcie zupełności
Linia 41: Linia 43:
**charakteryzacja klasy NP w języku logiki
**charakteryzacja klasy NP w języku logiki


*Dowody NP-zupełności i analiza złożoności problemu
*Dowody NP-zupełności i analiza złożoności problemu:
**przykłady redukcji i techniki ich konstrukcji
**przykłady redukcji i techniki ich konstrukcji
**analiza złożoności podproblemów
**analiza złożoności podproblemów
**problemy liczbowe i silna NP-zupełność
**problemy liczbowe i silna NP-zupełność


*Algorytmy aproksymacyjne
*Algorytmy aproksymacyjne:
**wersje optymalizacyjne problemów decyzyjnych
**wersje optymalizacyjne problemów decyzyjnych
**przykłady algorytmów aproksymacyjnych
**przykłady algorytmów aproksymacyjnych
**schematy aproksymacyjne
**schematy aproksymacyjne


*Dolne ograniczenia na aproksymowalność
*Dolne ograniczenia na aproksymowalność:
**L-redukcje
**L-redukcje
**klasa MAXSNP, problemy MAXSNP-zupełne
**klasa MAXSNP, problemy MAXSNP-zupełne
Linia 57: Linia 59:
**twierdzenie PCP i przykłady jego zastosowania
**twierdzenie PCP i przykłady jego zastosowania


*Algorytmy probabilistyczne
*Algorytmy probabilistyczne:
**probabilistyczne klasy złożoności
**probabilistyczne klasy złożoności
**rozpoznawanie liczb pierwszych
**rozpoznawanie liczb pierwszych
**generowanie bitów losowych
**generowanie bitów losowych


*Obliczenia równoległe
*Obliczenia równoległe:
**modele obliczeń równoległych
**modele obliczeń równoległych
**klasy złożoności równoległej
**klasy złożoności równoległej
Linia 68: Linia 70:
**równoległość i randomizacja
**równoległość i randomizacja


*Problemy funkcyjne i złożoność zliczania
*Problemy funkcyjne i złożoność zliczania:
** klasy FP, FNP, TFNP
** klasy FP, FNP, TFNP
** klasa #P i twierdzenie Valianta
** klasa #P i twierdzenie Valianta
** klasa <math>\oplus\textsc{P}</math>
** klasa <math>\oplus\text{P}</math>


*Pamięć logarytmiczna i hierarchia wielomianowa
*Pamięć logarytmiczna i hierarchia wielomianowa:
** klasy L, NL i coNL
** klasy L, NL i coNL
** twierdzenie Immermana-Szelepcsényi'ego
** twierdzenie Immermana-Szelepcsényi'ego
Linia 80: Linia 82:
** hierarchia wielomianowa
** hierarchia wielomianowa


*Pamięć wielomianowa  
*Pamięć wielomianowa:
**klasa PSPACE, problemy zupełne
**klasa PSPACE, problemy zupełne
**gry
**gry
**problemy zwięzłe i złożoność wykładnicza  
**problemy zwięzłe i złożoność wykładnicza  


*Kryptografia a złożoność
*Kryptografia a złożoność:
**funkcje jednokierunkowe
**funkcje jednokierunkowe
**protokoły interaktywne
**protokoły interaktywne
Linia 92: Linia 94:
===Literatura===
===Literatura===


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


== Moduły ==
== Moduły ==

Aktualna wersja na dzień 21:45, 11 cze 2020

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 ⊕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)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa&oldid=77658”