| Code |
13954
|
| Year |
3
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
PL(30H)/T(30H)
|
| Scientific area |
Informatics
|
|
Entry requirements |
NA
|
|
Learning outcomes |
There are limits to the ability of problem solving by a computer.
In order to explore these limits in this unit the student shall formally define the concept of computing power of the machines and study their theoretical limit and thus be able to define formally what is and what isn't a program, an algorithm.
To understand the concepts underlying programming languages in this unit we shall study formally the constructs that determine the expression (or computing power) of programming languages, as well as the behavior of the programs.
At the end of this Unit the student should be able to understand and use the computing power of the machines, as well as understand their theoretical limits, be able to formalize properly and assess whether certain problems have computational solution or not and be able to understand and know how to use models, techniques and symbolic computation techniques to solve everyday computer science and engineering problems.
|
|
Syllabus |
1. Context and History of the theory of Computation.
2. Regular Languages and Expressions, Finite Automata’s, Properties, algorithms, transformations and limits.
3. Context free languages, formal grammar’s, pushdown automata.
4. Theory of formal languages: decidable problems and their respective algorithms, processing of formal languages, parsing, grammar transformations.
5. Computing Models: Turing Machines, Kleene Recursive Theory, Lambda Calculus-
6. The Church-Turing Thesis. Equivalence proofs and models.
7. Computability and Decidability. Undecidable problems, the diagonal technique, reduction techniques, dealing with undecidable problems, semi-decision.
8. Computational Complexity. Definition of complexity classes (NP,P, NP-Hard, NPC, PSpace etc.).
9. NP Completeness. Cooks theorem, polynomial reductions, NP-Complete problems, dealing with NO completeness
|
|
Main Bibliography |
[1] Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
[2] P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
[3] M. Sipser. Introduction to the Theory of Computation. PWS Publishing, 2012.
[4] Pierre Wolper. Introduction à la Calculabilité. Dunod, Paris, France, 3 edition, 2006.
[5] Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
[6] M. Fernández. Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer, 2009.
[7] J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification, volume 103 of Undergraduate Topics in Computer Science. Springer-Verlag, first edition, 307 p. 52 illus. edition, 2011.
|
|
Language |
Portuguese. Tutorial support is available in English.
|