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
Linia 20: Linia 20:
=== 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 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
**relacje między klasami, twierdzenie Savitcha i dopełnienia klas,
**relacje między klasami, twierdzenie Savitcha i dopełnienia klas
**twierdzenia o hierarchii czasowej i pamięciowej.
**twierdzenia o hierarchii czasowej i pamięciowej


*Redukcje i zupełność
*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ść
Linia 50: Linia 55:
**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
*Algorytmy probabilistyczne
**probabilistyczne klasy złożoności,
**probabilistyczne klasy złożoności
**rozpoznawanie liczb pierwszych.
**rozpoznawanie liczb pierwszych
**generowanie bitów losowych


*Modele obliczeń równoległych, klasy NC i RNC.
*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
*Problemy funkcyjne i złożoność zliczania
** klasy FP i FNP,
** klasy FP, FNP, TFNP
** klasa TFNP,
** klasa #P i twierdzenie Valianta
** klasa #P i twierdzenie Valianta,
** klasa <math>\oplus\textsc{P}</math>
** klasa <math>\oplus\textsc{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
** klasy coNP i DP,
** klasy coNP i DP
** maszyny alternujące,
** maszyny alternujące
** hierarchia wielomianowa
** hierarchia wielomianowa


*Pamięć wielomianowa  
*Pamięć wielomianowa  
**klasa PSPACE,  
**klasa PSPACE, problemy zupełne
**problemy PSPACE-zupełne,
**gry
**gry.
**problemy zwięzłe i złożoność wykładnicza  
*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===

Wersja z 11:44, 15 wrz 2006

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 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, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
  • Przemysław Broniek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
  • Grzegorz Gutowski - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,
  • Jan Jeżabek - Uniwersytet Jagielloński, Wydział Matematyki i Informatyki, Katedra Algorytmiki,

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 Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \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. 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

  1. Obliczenia w modelu maszyny Turinga
  2. Inne modele dla złożności
  3. Klasy złożoności obliczeniowej
  4. Redukcje i zupełność
  5. Problemy NP-zupełne
  6. NP-zupełność jako narzędzie analizy problemu
  7. Algorytmy aproksymacyjne
  8. Schematy aproksymacji i klasa MAXSNP
  9. Twierdzenie PCP i nieaproksymowalność
  10. Algorytmy probabilistyczne
  11. Obliczenia równoległe
  12. Problemy funkcyjne i złożoność zliczania
  13. Pamięć logarytmiczna i hierarchia wielomianowa
  14. Pamięć wielomianowa i złożoność wykładnicza
  15. Kryptografia a złożoność
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa&oldid=51126”