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/

Rozvrh na zimní semestr 2019/2020:

	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	místnost T9:343 Kučera L. 12:45–16:00 LICHÝ TÝDEN (přednášková par. 1) Dejvice NBFIT učebna místnost T9:343 Kučera L. 12:45–14:15 SUDÝ TÝDEN (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:343 Suchý O. 14:30–16:00 SUDÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna
St
Čt
Pá

Rozvrh na letní semestr 2019/2020:

Rozvrh není připraven

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

• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2015 (volitelný předmět)
• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v letech 2015 (VO, volitelný předmět)
• 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)