|
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (13.12.2018)
|
|
||
Last update: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (13.12.2018)
Papadimitriou, Christos H.: Computational Complexity, Addison-Wesley 1994.
Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich: Discrete Algebraic Methods, Walter de Gruyther 2016.
Sakarovitch, Jacques: Elements of automata theory, Cambridge University Press 2009.
Sipser, Michael: Introduction to the Theory of Computation, PWS Publishing Company 1997
Shallit, Jeffrey: A second Course in Formal Languages and Automata Theory, Cambridge University Press 2009.
|
|
||
Last update: prof. Mgr. Michal Koucký, Ph.D. (28.09.2020)
Sylabus
1. Výpočetní modely: počítač, Turingův stroj, Booleovský obvod 2. Nerozhodnutelné problémy, problém zastavení 3. Časová složitost, třída P 4. Třída NP, NP-úplnost, Cook-Levinova věta, nedeterministické výpočty 5. Prostorová složitost, PSPACE, QBF, Polynomiální hierarchie 6. L, NL, Savičova věta, NL=coNL 7. Věty o hierarchii, zjemnělá složitost 8. Konečné automaty, regulární jazyky
Webová stránka přednášky: https://iuuk.mff.cuni.cz/~koucky/vyuka/AVS-ZS2020/index.html |