| Code |
14813
|
| Year |
3
|
| Semester |
S1
|
| ECTS Credits |
6
|
| Workload |
PL(30H)/T(30H)
|
| Scientific area |
Informatics
|
|
Entry requirements |
--
|
|
Mode of delivery |
face-to-face
|
|
Work placements |
Not applicable.
|
|
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 thus 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.
|
|
Syllabus |
A. Introduction and Basic Concepts
B. Finite-state Automata
C. Theory of Formal Languages
D. Pushdown Automata
E. Turing Machines
F. Non-computability and Undecidability
G. Others Models of Computation
H. Computational Complexity
I. Programming in Computer Models (practical-laboratory classes)
|
|
Main Bibliography |
"An Introduction to Formal Languages and Automata", 4th Ed, 2006
Peter Linz
Jones and Bartelett Computer Science
"Teoria da Computação - Computabilidade e Complexidade", 2010
Francisco Coelho e João Pedro Neto
Escolar Editora
"Elements for the Theory of Computation", 2nd Ed, 1998
Harry Lewis and Christos Papadimitriou
Prentice Hall, 1998.
"Models of Computation and Formal Languages", 1998
R. Gregory Taylor
Oxford University Press
"Introduction to Automata Theory, Languages and Computation", 2nd Ed, 2001
John Hopcroft, Rajeev Motwani, Jeffrey Ullman
Addison Wesley
|
|
Teaching Methodologies and Assessment Criteria |
In order to guarantee that students achieve the main goals expected for this course, classes will be divided into the following types:
- 2h/week theoretical classes (T) for showing the main theoretical concepts, methods and algorithms, using the board, oral discussion and data projection as main tools;
- 2h/week practical classes (PL), which will serve for applying and testing concepts learned during the theoretical classes, by problem solving and exercise sheets containing proofs to construct; There will also be a practical programming component.
Evaluation:
- 2 Written Tests (WT) - 16 points (80%) divided by 2 times (8 point each).
- 1 Evaluation of Knowledge on Practical Classes (PC) - 4 points (20%).
WT 1: 16/11/2021; WT 2: 11/01/2022; PC: 06/12/2021 or 07/12/2021
|
|
Language |
Portuguese. Tutorial support is available in English.
|