Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Teorie složitosti

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-CPX Z,ZK 5 3P+1C česky
Přednášející:
Ondřej Suchý (gar.), Dušan Knop
Cvičící:
Ondřej Suchý (gar.), Dušan Knop
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Studenti se dozvědí o základních třídách teorie výpočetní složitosti a různých modelech algoritmů a o implikacích této teorie týkajících se praktické algoritmické (ne)řešitelnosti složitých úloh.

Požadavky:
Osnova přednášek:

1. Výpočetní problémy a modely výpočtu.

2. Nerozhodnutelnost, nedeterminismus, třída NP, existence NP-úplného problému

3. Další NP-úplné problémy, silná a slabá NP-těžkost, pseudopolynomiální algoritmy

4. třídy coNP a NP průnik coNP, polynomiální hierarchie

5. Problém P=NP, relativizace

6. Třída PSPACE, Savitchova věta

7. PSPACE-úplné problémy (kvantifikované formule a hry), problémy úplné pro třídy hierarchie

8. Logspace

9. Obvodová složitost, P/poly, obvody omezené hloubky, paralelizace výpočtu

10. P-úplnost

11. Pravděpodobnostní algoritmy

12. Vztahy tříd pravděpodobnostních algoritmů a k ostatním třídám

13. Optimalizační problémy, Aproximační algoritmy

14. Pravděpodobnostně ověřitelné důkazy, gap problem, PCP věta,

15. Komunikační složitost

16. Složitost počítání, #P

17. (silná) Domněnka exponenciálního času, důsledky

18. Pseudonáhodné generátory, derandomizace.

Osnova cvičení:

1. Složitost algoritmů, vzájemné simulace výpočetních modelů.

2. Problémy mimo NP, Různé NP-úplné problémy a jejich převody, problémy patřící do coNP

3. Problémy patřící do PSPACE a různých tříd polynomiální hierarchie, příklady obvodů pro různé jednoduché problémy

4. Různé aproximační algoritmy a důkazy neaproximovatelnosti

5. Amplifikace pravděpodobnosti úspěchu pravděpodobnostních algoritmů, příklady

pravděpodobnostních algoritmů.

6. Komunikační schémata, dolní meze komunikační složitosti

Cíle studia:

Poskytnout teoretický základ pro rozhodování, zda daný problém lze, dle našich současných znalostí, úspěšně řešit a popřípadě, jaký typ výpočetních postupů zvolit.

Studijní materiály:

S. Arora, B. Barak, ''Computational Complexity: A Modern Approach''. Cambridge University Press, 2009. ISBN 0521424267.

Christos H. Papadimitriou, “Computational Complexity”. Pearson, 1993. ISBN 978-0201530827

D. P. Williamson, D. B. Shmoys: “The Design of Approximation Algorithms”, Cambridge university press, 2011. ISBN 9780521195270

V. V. Vazirani: Approximation Algorithms, Springer, 2001. ISBN 3540653678

R. Motwani, P. Raghavan, ''Randomized Algorithms''. Cambridge University Press, 1995. ISBN 0521474655.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-CPX/

Další informace:
https://courses.fit.cvut.cz/MI-CPX/
Rozvrh na zimní semestr 2020/2021:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
místnost TH:A-942
Knop D.
Suchý O.

12:45–16:00
LICHÝ TÝDEN

(přednášková par. 1)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Knop D.
Suchý O.

12:45–14:15
SUDÝ TÝDEN

(přednášková par. 1)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Knop D.
Suchý O.

14:30–16:00
SUDÝ TÝDEN

(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
St
Čt

Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 1. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet6290606.html