Automaty a výpočetní složitost

ZS 2021/2022
NMMB415 - 3/1 Z, Zk

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

Od teď se přednáška opět koná prezenčně.

Čas konání: Po 12:20-14:40, cvič. Po 14:50-15:30.
Místo konání: K7, Karlín. Zoom: https://cesnet.zoom.us/j/4042155019
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

1. Do 25.10.2021, 12:20.
2. Do 15.11.2021, 12:20.
3. Do 29.11.2021, 12:20.
4. Do 4.1.2022, 12:20.

Zkouška