| Code |
14813
|
| Year |
3
|
| Semester |
S1
|
| ECTS Credits |
6
|
| Workload |
PL(30H)/T(30H)
|
| Scientific area |
Informatics
|
|
Entry requirements |
NA
|
|
Mode of delivery |
face-to-face
|
|
Work placements |
Not applicable.
|
|
Learning outcomes |
Understand the computing capacity of classical machines, as well as their theoretical limits.
Understand how classical computers handle problems.
Understand the fundamental concepts that support the languages of a classical computer.
|
|
Syllabus |
A. Introduction and Basic Concepts
B. Finite Automata
C. Regular Expressions and Languages
D. Pushdown automata
E. Turing machines
F. Incomputability and undecidability
G. Alternative Computing Models
H. Introduction to Computational Complexity
I. Programming in Models of Computation (practical-laboratory classes)
|
|
Main Bibliography |
Michael Sipser. Introducton to the Theory of Computation (3rd Edition). Cengage Learning, 2012.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison Wesley, 2006.
|
|
Teaching Methodologies and Assessment Criteria |
In order for the student to acquire the required competences, the course includes:
- 2h/week of lectures (TE) for oral presentation of theoretical concepts, methods and algorithms, also using writing on the board, discussing ideas with the students and showing slides;
- 2h/week of practical-laboratory classes (PL), in which the student will apply and test the concepts, methods and algorithms presented in the lectures, by solving exercises on worksheets;
|
|
Language |
Portuguese. Tutorial support is available in English.
|