Teoria da Computação

Imagem d@ Carlos Manuel Chôrro Simões Barrico [Ficheiro Local]
Carlos Manuel Chôrro Simões Barrico
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)
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:
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