Automaty a výpočetní složitost

ZS 2025/2026
NMMB415 - 3/1 Z, Zk

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

První přednáška bude dne 10. října, 3. října tedy odpadá.

Čas konání: Pá 10:40-13:00, cvič. Pá 13:10-13:55.
Místo konání: K8, Karlín.
Jazyk: česky, unless we agree on English.

Přednáška podávající základní úvod do výpočetní složitosti a vyčíslitelnosti určená především studentům navazujícího magisterského studia MMIB.

Předběžný plán přednášky

• Výpočetní modely: počítač, Turingův stroj, Booleovský obvod
• Nerozhodnutelné problémy, problém zastavení
• Časová složitost, třída P
• Třída NP, NP-úplnost, Cook-Levinova věta, nedeterministické výpočty
• Prostorová složitost, PSPACE, QBF, Polynomiální hierarchie
• L, NL, Savičova věta, NL=coNL
• Věty o hierarchii, zjemnělá složitost
• Konečné automaty, regulární jazyky
• Booleovské obvody a výpočty s nápovedou.

Literatura

• Poznámky k přednášce 2020 (in Czech): 1) počítač, 2) Turingův stroj, 3) nerozhodnutelné problémy, 4) časová složitost, třída P, 5) NP-úplnost a nedeterministické výpočty, 6) prostorová složitost, 7) věty o hierarchii, 8) zjemnělá složitost, 9) konečné automaty 10) Booleovské obvody (2021)
• Michaal Sipser: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
• Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
• Sanjeev Arora, Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press, 2008.
• Christos Papadimitriou: Computational Complexity, Addison-Wesley, 1994.

Domácí úkoly

Zkouška