Złożoność obliczeniowa 2014/2015


Egzamin

Odpowiedzi do pytań testowych z komentarzami

Materiały

Plan wykładów (po angielsku)
Materiały Damiana Niwińskiego z zeszlego roku

Najważniejsze zagadnienia

  1. Co to jest uniwersalna maszyna Turinga?
  2. Co to jest problem decyzyjny, problem funkcyjny, klasa złożoności? Podstawowe inkluzje między klasami.
  3. Co to jest obwód logiczny i jak może symulować maszynę Turinga?
  4. Co to jest jednorodna rodzina obwodów i jak się ma do obliczeń równoległych?
  5. Jak działają niejednorodne modele obliczeń: obwody i maszyny?
  6. Co mówi twierdzenie o hierarchii?
  7. Co to jest klasa NP? (porównanie definicji) Jakie problemy zawiera, jakich nie?
  8. Co to znaczy, ze problem jest NP-zupelny? Dlaczego istnieje choć jeden taki?
  9. Jak działa algorytm Savitcha symulujący niedeterministyczną maszynę Turinga?
  10. Co to znaczy, ze problem jest PSPACE-zupelny? Jakie są przykłady takich problemów?
  11. Do czego służą redukcje w pamięci logarytmicznej? Przykłady problemów zupełnych dla klas NL i P.
  12. Jak rozstrzygać nieosiągalność w NL (tw. Immermana-Szelepcsenyiego)?
  13. Co to znaczy, że problem da się efektywnie rozwiązać algorytmem randomizowanym? (definicja probabilistycznej maszyny Turinga i klasy BPP)
  14. Do czego służy amplifikacja i jak działa?
  15. Jak się do siebie mają klasy PP, BPP, RP, co-RP i ZPP?
  16. Co to znaczy zderandomizować? Co wiadomo o derandomizacji w modelu jednorodnym, a co w niejednorodnym?
  17. Co to jest IP? (definicja i przykłady)
  18. Jak działa metoda algebraizacji i do czego słuzy?
  19. Jak sobie radzić z problemami NP-trudnymi, dokladnie i mniej wiecej?
  20. Jak dowodzić nieaproksymowalności? (Twierdzenie PCP)

Ogólne reguły dotyczące zadań domowych


Pierwsze zadanie domowe. Termin oddawania: 22 kwietnia 2015, 23:59.
Drugie zadanie domowe. Termin oddawania: 7 maja 2015, 23:59.
Trzecie zadanie domowe. Termin oddawania: 1 czerwca 2015, 23:59.
Czwarte zadanie domowe. Termin oddawania: 17 czerwca 2015, 23:59.

Filip Murlak 08-04-2015