Use logic and set theory to model data and systems. Know the theoretical foundations of computation, the formal concept of algorithm, and the existence of undecidable problems. Know the classes of formal languages, associated computational models, and the relationship between them. Understand the concept of Turing universality.
Model the state space of systems or abstract data types with set theory and first order logic. Distinguish countable from non-countable sets. Model systems using finite automata (DFA and NFA). Construct a finite automata from a regular expression and conversely. Construct a DFA equivalent to a NFA. Define context free languages using grammars. Construct LL and LR parsers. Recognize (un)decidable computational problems.
1. Modeling with Sets and Logic
Sets, Functions, Relations (review). Finite and Infinite, Cantor’s diagonalization argument. Difference between function and algorithm. Inductive definitions. Models of simple systems and abstract data types.
2. Machines, Automata and Specifications
What is a model of computation? Deterministic finite automata and regular expressions. Determinism and non-determinism in computation. Context Free languages and Stack machines. Parsing algorithms (LL and LR).
3. Computability
Basic complexity (P,NP). Expressiveness of computation models. Equivalence between pure functional and imperative programming. Abstract machines and layers of interpretation. Turing universality. Church-Turing thesis. Undecidability (of termination).
Lecture notes for the UC ITC (Luís Caires, 2011).
Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.
Hours per credit | 28 | ||
Hours per week | Weeks | Hours | |
Total hours | 0 | ||
ECTS | 6.0 |