Detail předmětu
Složitost
Garant předmětu
Jazyk výuky
česky
Zakončení
zkouška
Rozsah
- 26 hod. přednášky
- 26 hod. projekty
Zajišťuje ústav
Ústav inteligentních systémů (UITS)
Literatura studijní
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
- Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
- Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7
Literatura referenční
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
Osnova přednášek
- Úvod, Turingovy stroje, složitost časová a prostorová.
- Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
- Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
- Souvislosti prostoru a času z pohledu složitosti, uzavřenost tříd složitosti vůči doplňku, ostrost inkluzí mezi třídami složitosti.
- Blumův teorém. Gap theorem.
- Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
- Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
- Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
- NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
- Aproximační algoritmy, neaproximovatelnost.
- Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
- Složitost a kryptografie.
- PSPACE-úplné problémy. Složitost a formální verifikace.
Zařazení předmětu ve studijních plánech