Teorie složitosti

Přednášející:

Luděk Kučera (gar.), Ondřej Suchý

Cvičící:

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:

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

• Znalostní inženýrství, verze 2016 a 2017 (volitelný předmět)
• Počítačové systémy a sítě, verze 2016 až 2019 (volitelný předmět)
• Návrh a programování vestavných systémů, verze 2016 až 2019 (volitelný předmět)
• Zaměření Informační systémy a management, verze 2016 až 2019 (volitelný předmět)
• Zaměření Softwarové inženýrství, verze 2016 až 2019 (volitelný předmět)
• Zaměření Webové inženýrství, verze 2016 až 2019 (volitelný předmět)
• Společný magisterský plán před přiřazením do oboru, verze 2016 až 2019 (VO)
• Zaměření Systémové programování, verze 2016 až 2019 (volitelný předmět)
• Zaměření Teoretická informatika, verze 2016-2017 (povinný předmět zaměření)
• Znalostní inženýrství, verze 2018 to 2019 (volitelný předmět)