Teorie složitosti

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ů:

• Mgr. obor Znalostní inženýrství, 2016-2017 (volitelný předmět)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (volitelný předmět)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (VO)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (povinný předmět zaměření)
• Mgr. obor Znalostní inženýrství, 2018-2019 (volitelný předmět)