| Código |
14343
|
| Ano |
3
|
| Semestre |
S1
|
| Créditos ECTS |
6
|
| Carga Horária |
PL(30H)/T(30H)
|
| Área Científica |
Informática
|
|
Tipo de ensino |
Presencial
|
|
Estágios |
Não aplicável.
|
|
Objectivos de Aprendizagem |
Perceber a capacidade de computação das máquinas clássicas, bem como os seus limites teóricos.
Perceber a tratabilidade de problemas por computadores clássicos.
Perceber os conceitos fundamentais que sustentam as linguagens de um computador clássico.
|
|
Conteúdos programáticos |
A. Introdução e Conceitos Básicos
B. Autómatos Finitos
C. Expressões Regulares e Linguagens
D. Autómatos com Pilha
E. Máquinas de Turing
F. Incomputabilidade e indecidibilidade
G. Modelos de Computação Alternativos
H. Introdução à Complexidade Computacional
I. Programação em Modelos da Computação (aulas prático-laboratoriais)
|
|
Bibliografia principal |
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.
|
| Língua |
Português
|