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

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
Garant předmětu:
Ondřej Suchý
Přednášející:
Dušan Knop, Ondřej Suchý
Cvičící:
Michal Opler, Ondřej Suchý
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:

Předpokládají se znalosti grafů a grafových algoritmů v rozsahu BI-AG1, jazyků, Turingových strojů, tříd P a NP a nedeterminismu v rozsahu BI-AAG. Značnou výhodou jsou také znalosti z BI-AG2, napřiklad co se týče Hamiltonovských kružnic, TSP a aproximačních algoritmů a dalších.

Osnova přednášek:

1. Výpočetní problémy a modely výpočtu, Turingův stroj, nerozhodnutelnost.

2. Časová hierarchie, nedeterministický Turingův stroj.

3. Třída NP, existence NP-úplného problému, Cookova věta.

4. Silná a slabá NP-těžkost, pseudopolynomiální algoritmy. Třída coNP, Ladnerova věta.

5. Turingův stroj s orákulem, relativizace, Bakerova-Gillova-Solovayova věta.

6. Polynomiální hierarchie, problémy úplné pro třídy hierarchie.

7. Paměťová složitost, PSPACE, Savitchova věta, Logspace.

8. Booleovské obvody, Obvodová složitost, P/poly, obvody omezené hloubky, paralelizace výpočtu, P-úplnost.

9. Pravděpodobnostní Turingův stroj, Třídy randomizovaných výpočtů, redukce chyby, vztah k P/poly a k Polynomiální hierarchii.

10. Optimalizační problémy, aproximační algoritmy, třídy aproximovatelnosti.

11. Pravděpodobnostně ověřitelné důkazy, PCP věta, neaproximovatelnost Vrcholového Pokrytí a Nezávislé Množiny.

12. (silná) Domněnka exponenciálního času, jejich vztahy a důsledky.

13. Kvantové výpočty a vztahy ke klasickým třídám.

Osnova cvičení:

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

2. Nedeterminismus, redukce, třída NP

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

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

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

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

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.

Goldreich, O. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 052188473X.

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

M. Mitzenmacher, E. Upfal, '' Probability and Computing: Randomized Algorithms and Probabilistic Analysis''. Cambridge University Press, 2005, ISBN9780521835404.

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

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/NI-CPX/
Rozvrh na zimní semestr 2023/2024:
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
St
místnost T9:346
Opler M.
12:45–13:30
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
místnost T9:346
Suchý O.
13:30–16:00
(přednášková par. 1)
Dejvice
NBFIT učebna
Čt

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