1. Home
  2. NOVA School of Science and Technology
  3. Computer Science and Engineering
  4. Theory of Computation

Theory of Computation

Objectives

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.

General characterization

Code

2468

Credits

6.0

Responsible teacher

António Maria Lobo César Alarcão Ravara

Hours

Weekly - 5

Total - 65

Teaching language

Português

Prerequisites

Available soon

Bibliography

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.

Teaching method

The course is organized in lectures and laboratory classes. There are written lecture notes, which closely follow the presentation in the lectures.

In the laboratory classes students discuss and solve problems proposed by the instructor from a predefined list. In the lectures the instructor presents and motivates concepts and applications are discussed and exemplified, generally prompted by challenges arising in various areas of computer science. Tipically, “knowledge application” learning outcomes are also exercised in the recitation, so to promote a close connection between the theoretical concepts and their application.

Evaluation method

The course has an optional evaluation element, consituted by four quizzes, each one count 1 point to the final grade.

The continuous evaluation has a mandatory component consisting of two tests, each contributing with 8 points to the final grade. To be approved in the course the final grade in this component should be greater or equal 7,45 points.

The exam has two parts, each corresponding to a test. It is possible to improve the mark obtained in each test, even to achieve approval in the course. There will not be possible to improve the grades of the quizzes, but it is possible to count the exam to 20 points or each part to 10, abdicating of the grade of the quizzes.

Subject matter

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).