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, João Miguel Lourenço Ribeiro
Hours
Weekly - 5
Total - 65
Teaching language
Português
Prerequisites
Formally, approval in any other Curricular Unit is not required, but the knowledge and competences transmitted by Discrete Mathematics and Computational Logic are essencial.
Bibliography
Lecture notes for Theory of Computation (Luís Caires, 2015).
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
This course has three evaluation components: A practical component (P), a theoretical/practical component (TP), and a theoretical component (T).
* The P component is divided in two sub-components, P1 and P2:
- The P1 component evaluates active participation in lab lectures (1 point out of 20, in direct proportion to the number of lectures in which the student actively participated). Students should present original solutions to some of the proposed exercises to the lecturer.
- The P2 component consists in the presentation to the head lecturer (in an oral discussion) of certain topics from the theory of computation at large. A list of possible topics will be published during the semester. Students may also propose their own topics, subject to approval.
The final grade of this component is given by P = P1 + P2.
* The TP component consists of 2 online multiple-choice quizzes (MT1 and MT2). No auxiliary material nor electronic devices are allowed. The final grade of this component is given by TP = 0.5*MT1 + 0.5*MT2.
* The T component consists of 2 in-person tests (T1 and T2), or an in-person exam (Ex). No auxiliary material nor electronic devices are allowed. Students are allowed to solve only the part of the exam corresponding to a specific test. The grade for the remaining unsolved exam sections will be the grade from the corresponding test. The grade for this component is given by T = 0.5*T1 + 0.5*T2 or T = Ex. In order to obtain approval in the course, the T component must be at least 9.5.
All written evaluations in the TP and T components will be graded in a 0-20 scale.
* Final grade: The final grade (NF) is the maximum between the following quantities (the P, TP, and T components are rounded to the nearest hundredth):
T,
0.95*T + 0.05*TP,
0.9*T + 0.05*TP + P.
If NF > 20, the student will finish the course with a grade of 20.
* Improving grades: Only the T component may be improved. This would either be the grade of the exam or the grade of a part of the exam plus one of the tests. Students who obtained approval in the course this year may improve the grade obtained in one of the tests.
Students who have obtained approval in the course in previous years must take the exam in full, and will keep the grades from the P and TP components from the previous year in which they obtained approval. In this case, the final grade is computed using the rules from last year.
* No auxiliary material nor electronic devices of any kind are permitted in written evaluations.
In the P1 component there are no restrictions on the material that the students may consult nor on the usage of AI tools such as ChatGPT.
In the P2 component there are no restrictions on the material that the students may consult nor on the usage of AI tools such as ChatGPT while preparing for the oral discussion. During the oral discussion no auxiliary material nor electronic devices of any kind are permitted.
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).