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
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, an exercise solving one in the laboratories (P), one base based in quests (TP), and a theoretical one (T). All these elements are evaluated in the 0 to 20 scale.
The P component contributes with 1 value to the final grade. To obtain it a student should attend laboratory classes and present an original resolution of some of the exercices. The presence log is done in the beginning of the class.
The TP component consists of four quizzes, where the use of any kind of auxiliary material or electronic devise is not allowed, each contributing with 1 value to the final grade.
The T component consists of two written on-campus tests, each contributing with 7,5 values to the final grade. Both can be substituted by part of the final exam. Students are allowed to use an A4 hanwritten sheet as help for each test. These sheets, identified, should be delivered with the answer book. To aprove the course the grade obtained in the T component (either in the exam or in the average of the tests grades) é 9,5.
The final grade is calculated by the following grade, rounded to units, being the grades of the quizzes, tests, and several components, rounded to centesimals.
NF = P + TP + 0,75xT
Only component T may be improved. To improve a grade, students may do the final exam and substitute one or the two tests. Students may also not use the grades of the quizzes to define the final grade, being in that case used the formula
NFM = P + 0,95T
In written assigments it is not allowed the use of any kind of auxiliary material or electronic devise, apart from the sheets referred above.
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).