Automaty a výpočetní složitost

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

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

Dne 4.11. se přednáška nekoná.

Čas konání: Po 9:00-11:20, cvič. Po 11:30-12:10.
Místo konání: K10C, 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

Úkoly odevzdávejte v Moodle. Na zápočet je třeba získat alespoň 70% bodů ze všech úkolů. Každá úloha je za 10 bodů, pokud není rozdělená na podúlohy. Každá podúloha je za 5 bodů.

Zkouška

Zkouší se z probrané látky. Příklad zkušebních otázek. Zkouška je ústní. Po zadání otázek budete mít čas na přípravu. Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny. Společenský oblek není nutný, ale přiměřené oblečení je doporučeno. Termíny zkoušek budou v SISu.