Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

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
NI-CPX Z,ZK 5 3P+1C česky
Garant předmětu:
Ondřej Suchý
Přednášející:
Dušan Knop, Ondřej Suchý
Cvičící:
Michal Opler, 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:

Předpokládají se znalosti grafů a grafových algoritmů v rozsahu BI-AG1, jazyků, Turingových strojů, tříd P a NP a nedeterminismu v rozsahu BI-AAG. Značnou výhodou jsou také znalosti z BI-AG2, napřiklad co se týče Hamiltonovských kružnic, TSP a aproximačních algoritmů a dalších.

Osnova přednášek:

1. Výpočetní problémy a modely výpočtu.

2. Nerozhodnutelnost, nedeterminismus, třída NP, existence NP-úplného problému

3. Další NP-úplné problémy, silná a slabá NP-těžkost, pseudopolynomiální algoritmy

4. třídy coNP a NP průnik coNP, polynomiální hierarchie

5. Problém P=NP, relativizace

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

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

8. Logspace

9. Obvodová složitost, P/poly, obvody omezené hloubky, paralelizace výpočtu

10. P-úplnost

11. Pravděpodobnostní algoritmy

12. Vztahy tříd pravděpodobnostních algoritmů a k ostatním třídám

13. Optimalizační problémy, Aproximační algoritmy

14. Pravděpodobnostně ověřitelné důkazy, gap problem, PCP věta,

15. Komunikační složitost

16. Složitost počítání, #P

17. (silná) Domněnka exponenciálního času, důsledky

18. Pseudonáhodné generátory, derandomizace.

Osnova cvičení:

1. Složitost algoritmů, vzájemné simulace výpočetních modelů.

2. Problémy mimo NP, Různé NP-úplné problémy a jejich převody, problémy patřící do coNP

3. Problémy patřící do PSPACE a různých tříd polynomiální hierarchie, příklady obvodů pro různé jednoduché problémy

4. Různé aproximační algoritmy a důkazy neaproximovatelnosti

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

pravděpodobnostních algoritmů.

6. Komunikační schémata, dolní meze komunikační složitosti

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:

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

Christos H. Papadimitriou, “Computational Complexity”. Pearson, 1993. ISBN 978-0201530827

D. P. Williamson, D. B. Shmoys: “The Design of Approximation Algorithms”, Cambridge university press, 2011. ISBN 9780521195270

V. V. Vazirani: Approximation Algorithms, Springer, 2001. ISBN 3540653678

R. Motwani, P. Raghavan, ''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/NI-CPX/
Rozvrh na zimní semestr 2023/2024:
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
St
místnost T9:346
Opler M.
12:45–13:30
(přednášková par. 1
paralelka 101)

Dejvice
NBFIT učebna
místnost T9:346
Suchý O.
13:30–16:00
(přednášková par. 1)
Dejvice
NBFIT učebna
Čt

Rozvrh na letní semestr 2023/2024:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 15. 4. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6290606.html