Automaty a výpočetní složitosti

V zimním semestru 2026/2027 vedu kurz o výpočetních modelech, vyčíslitelnosti a výpočetní složitosti pro magisterské studenty matematiky [NMMB415]. Přednáška a cvičení se konají ve středy od 15:40 do 18:50 v posluchárně K12.

Zdroje

• Hand-written lecture notes
• Předchozí běh této přednášky včetně částečných videozáznamů
• Přednáška z roku 2025 (Michal Koucký), včetně poznámek
• Michael 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.
• Martin Mareš: Úvod do automatů
• Karl Bringmann: Fine-Grained Complexity Theory – lecture notes