Výpočetní modely

Výuka probíhá na katedře logiky FF UK.

Sylabus

  1. Turingův stroj
  2. měření času a prostoru pro Turingův stroj
  3. příklady jazyků, jejichž rozpoznání vyžaduje logaritmický prostor
  4. algoritmicky nerozhodnutelné úlohy, problém zastavení
  5. Postův korespondenční problém, problém slov v pologrupách
  6. random access machine (RAM)
  7. 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

  1. John E. Savage. Models of Computation, Exploring the Power of Computing.
  2. Michael Sipser. Introduction to the Theory of Computation.
    Thomson Course Technology, 2006.
  3. Sanjeev Arora and Boaz Barak. Computational Complexity, A Modern Approach.
    Cambridge University Press, 2009.