Výpočetní modely
Výuka probíhá na
katedře logiky FF UK.
Sylabus
- Turingův stroj
- měření času a prostoru pro Turingův stroj
- příklady jazyků, jejichž rozpoznání vyžaduje logaritmický prostor
- algoritmicky nerozhodnutelné úlohy, problém zastavení
- Postův korespondenční problém, problém slov v pologrupách
- random access machine (RAM)
- ekvivalence polynomiálního času pro Turingův stroj a RAM
Učební texty
Sekce 4.1 až 4.4 z textu fja2016AutGr1.pdf
Sekce 1 z textu fja2016AN.pdf
Sekce The word problem in universal algebra v článku na Wikipedii
Word problem (mathematics)
Sekce 2.2.2 a 2.4 z textu
vypsl2016zs1.pdf
Literatura
- John E. Savage.
Models of Computation, Exploring the Power of Computing.
- Michael Sipser. Introduction to the Theory of Computation.
Thomson Course Technology, 2006.
- Sanjeev Arora and Boaz Barak. Computational Complexity, A Modern Approach.
Cambridge University Press, 2009.