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

Teorie složitosti

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-CPX Z,ZK 5 3+1 česky
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/

Rozsah=prednasky+proseminare+cviceni3p+1c

Další informace:
https://courses.fit.cvut.cz/MI-CPX/
Rozvrh na zimní semestr 2018/2019:
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:301
Kučera L.
12:45–16:00
SUDÝ TÝDEN

(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:301
Kučera L.
12:45–14:15
LICHÝ TÝDEN

(přednášková par. 1)
Dejvice
NBFIT učebna
místnost T9:301
Suchý O.
14:30–16:00
LICHÝ TÝDEN

(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
St
Čt

Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 22. 3. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1433906.html