| 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 |
Due to the pandemic situation, the assessment criteria are two-fold.
with the possibility of an in-person written exam: Assessment = (practical assessment * 0.8 + written assessment * 1.2) / 2
without the possibility of an in-person written exam: Assessment = reinforced practical assessment
practical assessment = 3 exercises to be submitted electronically
reinforced practical assessment = 4 exercises to be submitted electronically
written assessment = "frequência" or exam
|
|
Language |
Portuguese. Tutorial support is available in English.
|