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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Broniek (dyskusja | edycje)
50 edycji
m Zastępowanie tekstu - "\textsc{" na "\text{"
 
(Nie pokazano 70 wersji utworzonych przez 8 użytkowników)
Linia 3: Linia 3:


== Opis ==
== 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 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.
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 ==
== Sylabus ==


=== Autor ===
=== Autorzy ===
    
    
Maciej Ślusarek
*Maciej Ślusarek - Uniwersytet Jagielloński
 
*Przemysław Broniek - Uniwersytet Jagielloński
Przemysław Broniek
*Grzegorz Gutowski - Uniwersytet Jagielloński
 
*Jan Jeżabek - Uniwersytet Jagielloński
Grzegorz Gutowski
 
Jan Jeżabek


===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, warianty modelu (off-line, wielotaśmowa, niedeterministyczna).
*Złożoność obliczeniowa w modelu maszyny Turinga:
**zasoby obliczeniowe
**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 poszczególnych modelach
**zależności między funkcjami złożoności w różnych modelach
**problem decyzyjny w notacji "naturalnej", kodowanie problemu.


*Klasy złożoności
*Klasy złożoności obliczeniowej:
**relacje między klasami
**klasy złożoności czasowej i pamięciowej
**twierdzenia o przyspieszaniu
**twierdzenia o liniowym przyspieszaniu i kompresji pamięci
**twierdzenia o hierarchii pamięciowej i czasowej
**relacje między klasami, twierdzenie Savitcha i dopełnienia klas
**domkniętość ze względu na dopełnienie.
**twierdzenia o hierarchii czasowej i pamięciowej


*Redukcje
*Redukcje i zupełność:
**rodzaje: wielomianowa, logarytmiczna, Turinga
**rodzaje redukcji: wielomianowa, logarytmiczna, Turinga
**pojęcie zupełności
**pojęcie zupełności
**klasa NP, NP-zupełność, twierdzenie Cooka-Levina.
**klasa NP, NP-zupełność, twierdzenie Cooka-Levina
**charakteryzacja klasy NP w języku logiki


*Dowody NP-zupełności
*Dowody NP-zupełności i analiza złożoności problemu:
**techniki konstrukcji redukcji wielomianowych
**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. Schematy aproksymacyjne.
*Algorytmy aproksymacyjne:
**wersje optymalizacyjne problemów decyzyjnych
**przykłady algorytmów aproksymacyjnych
**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
**charakteryzacja klasy NP przez weryfikatory
**charakteryzacja klasy NP przez weryfikatory
**twierdzenie PCP i przykłady zastosowania do nieaproksymowalności
**twierdzenie PCP i przykłady jego zastosowania
 
*Algorytmy probabilistyczne:
**probabilistyczne klasy złożoności
**rozpoznawanie liczb pierwszych
**generowanie bitów losowych


*Algorytmy probabilistyczne
*Obliczenia równoległe:
**rozpoznawanie liczb pierwszych.
**modele obliczeń równoległych
**probabilistyczne klasy złożoności.
**klasy złożoności równoległej
**P-zupełność
**równoległość i randomizacja


*Modele obliczeń równoległych, klasy NC i RNC.
*Problemy funkcyjne i złożoność zliczania:
** klasy FP, FNP, TFNP
** klasa #P i twierdzenie Valianta
** klasa <math>\oplus\text{P}</math>


*Klasy złożoności pamięciowej
*Pamięć logarytmiczna i hierarchia wielomianowa:
**struktura klasy LOGSPACE
** klasy L, NL i coNL
**hierarchia wielomianowa
** twierdzenie Immermana-Szelepcsényi'ego
**problemy zupełne w klasie PSPACE
** klasy coNP i DP
**alternacja i gry.
** maszyny alternujące
** hierarchia wielomianowa


*Złożoność zliczania. Klasa #P. Problemy funkcyjne.
*Pamięć wielomianowa:
**klasa PSPACE, problemy zupełne
**gry
**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
**IP=PSPACE.
**IP=PSPACE


===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 ==
 
# [[Złożoność obliczeniowa/Wykład 1: Obliczenia w modelu maszyny Turinga|Obliczenia w modelu maszyny Turinga]] ([[Złożoność obliczeniowa/Test 1: Obliczenia w modelu maszyny Turinga|test]])
* [[Złożoność obliczeniowa/Moduł Modele złożoności obliczeniowej|Modele złożoności obliczeniowej]] ([[Złożoność obliczeniowa/Ćwiczenia Modele złożoności obliczeniowej|ćwiczenia]])
# [[Złożoność obliczeniowa/Wykład 2: Inne modele dla złożoności|Inne modele dla złożności]] ([[Złożoność obliczeniowa/Test 2: Inne modele dla złożoności|test]])
* (...)
# [[Złożoność obliczeniowa/Wykład 3: Klasy złożoności obliczeniowej|Klasy złożoności obliczeniowej]] ([[Złożoność obliczeniowa/Test 3: Klasy złożoności obliczeniowej|test]])
* [[Złożoność obliczeniowa/Klasy złożoności|Klasy złożoności]]
# [[Złożoność obliczeniowa/Wykład 4: Redukcje i zupełność|Redukcje i zupełność]] ([[Złożoność obliczeniowa/Test 4: Redukcje i zupełność|test]])
* (...)
# [[Złożoność obliczeniowa/Wykład 5: Problemy NP-zupełne|Problemy NP-zupełne]] ([[Złożoność obliczeniowa/Test 5: Problemy NP-zupełne|test]])
* [[Złożoność obliczeniowa/Moduł Algorytmy aproksymacyjne|Algorytmy aproksymacyjne]] ([[Złożoność obliczeniowa/Ćwiczenia Algorytmy aproksymacyjne|ćwiczenia]])
# [[Złożoność obliczeniowa/Wykład 6: NP-zupełność jako narzędzie analizy problemu|NP-zupełność jako narzędzie analizy problemu]] ([[Złożoność obliczeniowa/Test 6: NP-zupełność jako narzędzie analizy problemu|test]])
* [[Złożoność obliczeniowa/Moduł Schematy aproksymacji i klasa MAXSNP|Schematy aproksymacji i klasa MAXSNP]] ([[Złożoność obliczeniowa/Ćwiczenia Schematy aproksymacji i klasa MAXSNP|ćwiczenia]])
# [[Złożoność obliczeniowa/Wykład 7: Algorytmy aproksymacyjne|Algorytmy aproksymacyjne]] ([[Złożoność obliczeniowa/Test 7: Algorytmy aproksymacyjne|test]])
* [[Złożoność obliczeniowa/Moduł Twierdzenie PCP|Twierdzenie PCP]] ([[Złożoność obliczeniowa/Ćwiczenia Twierdzenie PCP|ćwiczenia]])
# [[Złożoność obliczeniowa/Wykład 8: Schematy aproksymacji i klasa MAXSNP|Schematy aproksymacji i klasa MAXSNP]] ([[Złożoność obliczeniowa/Test 8: Schematy aproksymacji i klasa MAXSNP|test]])
* (...)
# [[Złożoność obliczeniowa/Wykład 9: Twierdzenie PCP i nieaproksymowalność|Twierdzenie PCP i nieaproksymowalność]] ([[Złożoność obliczeniowa/Test 9: Twierdzenie PCP i nieaproksymowalność|test]])
* [[Złożoność obliczeniowa/Złożoność pamięciowa|Złożoność pamięciowa]]
# [[Złożoność obliczeniowa/Wykład 10: Algorytmy probabilistyczne|Algorytmy probabilistyczne]] ([[Złożoność obliczeniowa/Test 10: Algorytmy probabilistyczne|test]])
* (...)
# [[Złożoność obliczeniowa/Wykład 11: Obliczenia równoległe|Obliczenia równoległe]] ([[Złożoność obliczeniowa/Test 11: Obliczenia równoległe|test]])
 
# [[Złożoność obliczeniowa/Wykład 12: Problemy funkcyjne i złożoność zliczania|Problemy funkcyjne i złożoność zliczania]] ([[Złożoność obliczeniowa/Test 12: Problemy funkcyjne i złożoność zliczania|test]])
== Literatura uzupełniająca ==
# [[Złożoność obliczeniowa/Wykład 13: Pamięć logarytmiczna i hierarchia wielomianowa|Pamięć logarytmiczna i hierarchia wielomianowa]] ([[Złożoność obliczeniowa/Test 13: Pamięć logarytmiczna i hierarchia wielomianowa|test]])
# [[Złożoność obliczeniowa/Wykład 14: Pamięć wielomianowa i złożoność wykładnicza|Pamięć wielomianowa i złożoność wykładnicza]] ([[Złożoność obliczeniowa/Test 14: Pamięć wielomianowa i złożoność wykładnicza|test]])
# [[Złożoność obliczeniowa/Wykład 15: Kryptografia a złożoność|Kryptografia a złożoność]] ([[Złożoność obliczeniowa/Test 15: Kryptografia a złożoność|test]])

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”