Automaty a výpočetní složitost
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
ZS 2020/2021
NMMB415 - 3/1 Z, Zk
Čas konání: St. 10:40-13:00, cvič. St. 13:10-14:00.
Místo konání: Skrze Zoom https://cesnet.zoom.us/j/4042155019, Malá Strana.
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 (Sipser - kap. 3), Booleovský obvod
- Nerozhodnutelné problémy, problém zastavení (Sipser - kap. 4 a 5)
- Časová složitost, třída P (Sipser - kap. 7.1-7.2)
- Třída NP, NP-úplnost, Cook-Levinova věta (Sipser - kap. 7.3-7.4), nedeterministické výpočty (Sipser - kap. 10.3)
- Prostorová složitost, PSPACE, QBF (Sipser kap. 8), Polynomiální hierarchie
- L, NL, Savičova věta, NL=coNL
- Věty o hierarchii (Sipser - kap. 9.1), zjemnělá složitost
- Konečné automaty, regulární jazyky
Literatura
- Aktualizované poznámky k přednášce
- 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ů.
- Do 21.10.2020, 10:30.
- Do 4.11.2020, 10:30.
- Do 25.11.2020, 10:30.
- Do 16.12.2020, 10:30.
- Do 13.1.2021, 10:30.
Zkouška
Zkouší se z probrané látky. Termíny zkoušek jsou v SISu a další lze domluvit emailem.
Předpokládá se osobní účast na zkoušce. Pokud se nemůžete dostavit osobně, vzdálené zkoušky budou ve stejné dny, ale už od 9:00 hodin přes Zoom. Pro vzdálené zkoušky je nutná kamera, doklad totožnosti a informovat zkoušejícího alespoň den předem. Příklad zkušebních otázek.