| Código |
14813
|
| 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, assim como os seus limites teóricos. Para tal, é necessário definir formalmente o que é e o que não é um programa, um algoritmo.
Perceber os fundamentos das linguagens de programação. Para tal, é necessário estudar as construções que determinam a capacidade de computação das linguagens, assim como o comportamento dos programas.
|
|
Conteúdos programáticos |
A. Introdução e Conceitos Básicos
B. Autómatos de Estados Finitos
C. Teoria das Linguagens Formais
D. Autómatos com Pilha
E. Máquinas de Turing
F. A Não Computabilidade e a Indecidibilidade
G. Modelos de Computação Alternativos
H. Complexidade Computacional
I. Programação em Modelos da Computação (aulas pratico-laboratoriais)
|
|
Metodologias de Ensino e Critérios de Avaliação |
Para que o estudante possa adquirir as competências exigidas, estão previstas:
- 2h/semana de aulas teóricas (TE) para exposição oral dos conceitos teóricos, métodos e algoritmos, utilizando-se ainda a escrita no quadro, a discussão de ideias com os alunos, e a projeção de diapositivos;
- 2h/semana de aulas prático-laboratoriais (PL), nas quais o estudante aplicará e testará os conceitos, os métodos e os algoritmos apresentados nas aulas teóricas, através da resolução de exercícios que constam em fichas criadas para o efeito;
Avaliação:
- 2 testes escritos, cada teste vale 8.0 valores;
- 1 trabalho prático, valendo 4 valores.
Teste escrito 1: 16/11/2021; Teste escrito 2: 11/01/2022; Trabalho prático: 06/12/2021 ou 07/12/2021
|
|
Bibliografia principal |
"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
|
| Língua |
Português
|