Teorie složitosti
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.
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/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 Č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)