This course introduces students to the mathematical foundations of theoretical computer science, including computational models, formal languages, and automata theory. Students will learn how to formalize computations and understand the limits of computability and complexity.
Course Program
Introduction to Computation Theory
- History and objectives of the course;
- Basic concepts and definitions.
Formal Languages and Grammars
- Alphabets, words, languages;
- Regular languages and regular expressions;
- Context-free grammars.
Finite Automata
- Deterministic and non-deterministic finite automata;
- Equivalence of automata and minimization;
- Applications of automata.
Store automata and context-free languages
- Definition and properties;
- Connection with grammars.
Turing machines
- Turing model;
- Computability and non-computability;
- Examples of computable functions.
Computational complexity
- Complexity classes P, NP, NP-complete problems;
- Connection with computation models.
The halting theorem and its consequences
- Formulation and proof;
- Impact on computability.
Applications of computation theory
- Compilers;
- Program verification;
- Cryptography.
Course duration
12 weeks (2–3 classes per week, 1.5–2 hours each).