| Code |
14343
|
| 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 skills, the student is provided for:
- 2h/week of theoretical classes (ET) for oral exposure of theoretical concepts, methods and algorithms, also using writing on the board, discussing ideas with students, and projection of slides;
- 2h/week of practical-laboratory classes (PL), in which the student will apply and test the concepts, methods and algorithms presented in the theoretical classes, through the resolution of exercises that are included in forms created for this purpose;
|
|
Language |
Portuguese. Tutorial support is available in English.
|