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

Teorie složitosti

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-CPX Z,ZK 5 3P+1C česky
Garant předmětu:
Přednášející:
Cvičící:
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. Modely výpočtu.\r

2. Algoritmická nerozhodnutelnost.\r

3. Nedeterminismus, třída NP, existence NP-úplného problému.\r

4. Další NP-úplné problémy.\r

5. Problém P=NP, relativizace, třídy coNP a NP průnik coNP.\r

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

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

8. Obvodová a algebraická složitost.\r

9. Pravděpodobnostní algoritmy, třídy složitosti pravděpodobnostních algoritmů (třídy BPP, ZP, RP).\r

10. Jednosměrné funkce, pseudonáhodné posloupnosti, diskrétní logaritmus, kryptografie.\r

11. Interaktivní důkazy, pravděpodobnostně ověřitelné důkazy, expandery, gap problem, PCP věta, neaproximovatelnost 3SAT.\r

Osnova cvičení:

1. Vzájemné simulace výpočetních modelů.

2. [2] Různé NP-úplné problémy a jejich převody.

3. Problémy patřící do coNP a průniku NP a coNP.

4. [2] Úplné problémy pro PSPACE a různé třídy hierarchie v PSPACE.

5. [2] Příklady obvodů pro různé jednoduché problémy, omezenost počtu vstupů hradel.

6. [3] Příklady různých Monte-Carlo a Las Vegas algoritmů.

7. Příklady pseudonáhodných posloupností a jednoduché poznatky o jejich (ne)predikovatelnosti.

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

9. Expandery a náhodné procházky, Markovovy řetězce a jejich míchání.

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:

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

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

Motwani, R., Raghavan, P. ''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/
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 14. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet1433906.html