Theory of Computation
Objectives
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. Recognise (semi-)decidable languages.
Distinguish countable from non-countable sets. Model systems using finite automata, deterministic (DFA) and non-deterministic (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. Recognise expressiveness limits of languages and (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 - 70
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).
Lecture notes for Theory of Computation (João Ribeiro, 2024).
Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.
Michael Sipser: "Introduction to the Theory of Computation", Cengage Learning, 2012, 3rd edition.
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 two evaluation components: A practical component (P) and a theoretical/practical component (T).
* The P component, which is not mandatory, 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 a detailed solution of an exercise proposed by the lecturer. Possible exercises are those used in evaluation tests in previous years. This assessment is solicited by the students and occurs during the teaching period. During the presentation the use of any auxiliary material or device is not allowed.
The final grade of this component is given by P = P1 + P2.
* The T component consists of 3 individual in-person tests (T1 to T3), or an in-person exam (Ex). Students are allowed to use one side of an A4 handwritten sheet as help for each test - three in the exam (one for each part corresponding to a test). These sheets, identified with the student number, should be delivered with the answer book. All written evaluations in the T component will be graded in a 0-20 scale.
The grade for this component is the average of the tests grades converted to 0-18, i-e-, given by T = 0.9*(T1 + T2 + T3)/3 or T = 0.9*Ex. In order to obtain approval in the course, the T component must be at least 8.5.
Pre-registration is required for the tests. When the distribution of students across rooms is published, a room will be identified where students who did not register for the test might be able to take it, according to the following rule: if, 15 minutes after the actual start of the test, the number of unregistered students wishing to take the test can be accommodated in the indicated room, and if there are enough test papers available, these students may take the test, but they will not be given extra time; otherwise, if there is no space or test paper for all these students, none of them will take the test.
* Final grade: The final grade (NF) is given by the following formula, where the P and T components are rounded to the nearest hundredth: NF = P + T. To aprove the course the minimum grade of NF is 9.5.
* Improving grades: Only the T component may be improved. The grade obtained in the exam substitutes the grade obtained in this component.
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 extra auxiliary material (besides the one referred above) nor electronic devices of any kind are permitted in written evaluations.
During an assessment, students may not have any electronic devices capable of accessing the internet or with Bluetooth connectivity (e.g., smartphones, smartwatches, smartglasses, tablets, laptops) with them, even if they are turned off.
Violation of this rule results in immediate failure of the curricular unit by exclusion and will be reported to the Scientific Committee of the respective program.
Subject matter
1. Set Theory
Set cardinality, countable and uncontable sets, Cantor’s diagonalisation argument. Difference between function and algorithm. Decision problems and languages.
2. Machines, Automata and Specifications
What is a model of computation? Finite automata and regular expressions. Determinism and non-determinism in computation. Context Free languages and Stack machines. Parsing algorithms (LL and LR). Turing machines.
3. Computability
Turing universality. Church-Turing thesis. Undecidability of problems(e.g., termination) and (semi-)decidability of languages.