Ukončení předmětu

V průběhu semestra studenti samostaně řeší  3 sady problémů. Nutnou podmínkou pro úspěšné ukončení předmětu je získat za řešení příkladů alespoň  110 bodů (z celkového počtu 80 + 60 +40 bodů).

Ústní zkouška na konci semestru. 

---

Harmonogram výuky

přednáška, úterý v 16:00  hod, místnost D2, plán bude průběžně aktualizován dle reality

1. rekapitulace:  definice časové a prostorové složitosti, definice složitostní třídy, linear speedup  [20. 2. 2018]

2. vztahy mezi složitostními třídami (determinizmus vs nedeterminizmus, čas vs prostor)  [27. 2. 2018]

3. uzávěrové vlastnosti složitostních tříd,  Immermanova - Szelepcsényiho věta [6. 3. 2018]

4. separace složitostních tříd, hierarchie složitostních tříd [13. 3. 2018]

5.   dolní odhady složitosti pro konkrétní jazyky, úplné a těžké problémy složitostních tříd, polynomiální a logaritmická redukce  [20. 3. 2018]

6.  Turingova redukce; orákulový Turingův stroj a relativizované složitostní třídy, relativizace vztahu P a NP  [27. 3. 2018]

7.  Polynomiální hierarchie. [3. 4. 2018]

8. Randomizace: TS s pravděpodobností, pravděpodobnostní složitostní třídy, vztah BPP a polynomiální hierarchie y [10. 4. 2018]

9. Paralelizmus: logické obvody,  třída NC a její vztah k P, vysoce sekvenční problém [17. 4. 2018]

10.  Interaktivní protokoly, vztah tříd PSPACE a IP [24. 4. 2018]

11. 1. 5. 2018 státní svátek

12. 8. 5. 2018 státní svátek

13. PCP theorem & nonaproximabilty [15. 5. 2018] 

---

Harmonogram odevzdávání sad

Sada 1    3. 4 . 2018
Sada 2    1. 5. 2018
Sada 3    8. 5. 2018