Models of Computation

Lecture: Tuesday 14:15 - 15:45, room 2.502
Practice class: Tuesday 16:00 - 17:30, room 0.817

Content:

Classical models of computing: finite automata, pushdown automata, Turing machines(TM), variants of TMs, partial recursive functions, undecidability, time and space complexity, random access machines (RAM), circuits, cellular automata. Models of parallel and distributed computing. Unconventional models of computing (natural computing).

Requirements, evaluation:

1. Active partitipation and work in pactice classes: solving and discussing excercises
2. passing >=50% of the 10 min. tests at the beginning of the practice classes
3. Successful exams (grade is computed as average of 2 exams)

Important dates:

- midterm test/exam (written): 2023-10-17
- final test/exam (written): 2023-11-28
- repeat exam (second trial exam in case of unsuccessful exam): 2023-12-05

Slides:

-	foliák
1. Introduction	PDF
2. Grammars	PDF
3. Programmed grammars, Matrix grammars, Random context grammars, L-systems	PDF
4. Regular expressions, finite automata	PDF
5. Finite automata, DFA, NFA, minimal DFA, regular pumping lemma	PDF
6. Probabilistic automata, Pushdown automata, Context-free languages	PDF
7. Turing machines, Variants, Church-Turing thesis, Recursively enumerable languages	PDF
8: Decision problems, Undecidability, Diagonalization	PDF

Exercise sheets: 1

Literature:

J. E. Savage, Models of Computation: Exploring the Power of Computing, Brown University, 1998. https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf
M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.