Automata and Computational Complexity
In the winter semester 2026/2027, I teach a course on automata and computational complexity for students of mathematics at master's level [NMMB415]. The lecture and practicals happen on Tuesdays between 15:40 and 18:50 in room K3.
If you want to consult anything, please write an e-mail to mares@kam.mff.cuni.cz and we will discuss possibilities.
We have video recordings (links below), but some parts of the recordings are missing due to equipment failures.
| date | topics | material |
|---|---|---|
| 30. 9. | Architecture of modern computers. Representation of data in memory. CPU and its instructions (see an example). High-level languages, compilers and interpreters. Operating systems and virtual memory. Tricks for faster execution: caching, pipelining, executing more instructions simultanously, branch prediction. video1 video2 | notes |
| 7. 10. |
Towards a formal model of computation. Alphabets and strings. Turing
machines, their syntax and semantics. Computable and partially computable
functions and sets. Example: recognizing 0n1n.
Variants of Turing machines: one-way-infinite tape, multiple tapes,
randomized, with oracle, interactive.
Exercises: recognize binary strings with even number of 1s, reverse a binary string, add and multiply binary numbers. | video notes |
| 14. 10. |
Plan:
Random access machines and their equivalence with Turing machines.
Computable and partially computable sets, classes R and RE.
Enumerable sets are equal to partially computable sets.
Universal language and diagonal language.
Exercises: Monotonically enumerable sets are equal to computable sets. Both R and RE are closed under union and intersection. | notes |
Grading
To complete the course, you need to pass an exam and obtain class credit (in any order).
The exam covers theory presented at the lecture: definitions, theorems, and their proofs. You are allowed to use a cheat sheet on a single A4 page, which you wrote (or typed) yourself.
To obtain credit, you need to solve homework exercises worth at least 100 points. There will be several exercise sets during the semester, worth at least 150 points in total. To submit solutions, please use the Postal Owl (use this link to enroll).
Sources
- Hand-written lecture notes
- Previous run of this course (Michal Koucký), including notes in Czech
- My 2023 version of the course in Czech, including partial recordings.
- My 2022 version of the course in English, including partial recordings.
- Michael 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.
- Martin Mareš: Úvod do automatů (automata theory, in Czech)
- Karl Bringmann: Fine-Grained Complexity Theory – lecture notes