Theory of Computation
2
2016-2017
01000142
Computer Science
Portuguese
Face-to-face
SEMESTRIAL
6.0
Compulsory
1st Cycle Studies
Recommended Prerequisites
Logic, discerte structures, algebra, mathematical analysis, computer programmimg; English.
Teaching Methods
Theoretical classes (2h weekly) for presentation and discussion of the materials of the successive chapters, with computational demonstrations when appropriate. Examples are also solved in the blackboard.
Theoretical-practical classes (1h weekly) for problem solving from a sheet of problems delivered to the students each week.
Practical Laboratorial classes (2h weekly) for additional support in problem solving and for the resolution of thematic challenges.
Learning Outcomes
To study the several models of automata (finite, stack, Turing Machine) and formal grammars (regular, context free and context sensitive, and recursive) and the relations among them, showing its relations with the programming languages and compilers. These are structuring knowledge of the informatics as a scientific discipline that develop the mental capability to follow the present and future evolution of informatics and computation. Also the several computation models, developed in the past, are addressed and compared. The notion of complexity associated with the Turing-computability is introduced, to show the present limits of computation.
Competencies in analysis and synthesis, written communication, informatics knowledge relative to the study focus, problem solving, critical thinking, autonomous learning, practical application of theoretical knowledge, creativity.
Work Placement(s)
NoSyllabus
Chap.1. Introduction and basic definitions; languages, grammars, automata.
Chap.2. Finite automata, deterministic, nondeterministic and their relations.
Chap.3. Regular languages, regular grammars, regular expressions, finite automata, and their relations.
Chap.4. Properties of regular languages, the pumping lemma.
Chap.5. Context-free languages, parsing.
Chap.6 Simplification of grammars, normal forms.
Chap.7. Stack automata, non-deterministic and deterministic..
Chap.8. Properties of context-free languages, pumping lemmas.
Chap.9. Turing Machine, Turing hypothesis.
Chap.10.Other Turing Machine models, linearly bounded automata..
Chap.11 Hierarchies of formal languages and automata..
Chap.12. The limits of algorithmic computation.
Chap.13. Other models of computation (recursive functions, Post, rewriting, lambda-Calculus)
Chap.14. An introduction to the theory of complexity, problems P e NP.
Head Lecturer(s)
António Dourado Pereira Correia
Assessment Methods
Assessment
2 Tests: 40.0%
Exam: 60.0%
Bibliography
An Introduction to Formal Languages and Automata, Peter Linz, 3rd Ed., Jones and Bartelett Computer Science, 2001.
Models of Computation and Formal Languages, R. Gregory Taylor, Oxford University Press, 1998.
Introduction to Automata Theory, Languages and Computation, 2nd Ed., John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2001.
Elements for the Theory of Computation, Harry Lewis and Christos Papadimitriou, 2nd Ed., Prentice Hall, 1998.
Introduction the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.