Teorie složitosti

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ččebnamístnost T9:346 Suchý O. 13:30–16:00 (přednášková par. 1) Dejvice NBFIT uččebna
Čt
Pá

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (PS, volitelný předmět)