Conteúdo / Main content
Menu Rodapé
  1. Início
  2. Cursos
  3. Engenharia Informática
  4. Teoria da Computação

Teoria da Computação

Código 11562
Ano 2
Semestre S2
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 e usar a capacidade de computação das máquinas, assim como os seus limites teóricos.
O aluno deverá ser capaz de perceber e usar a capacidade de computação das máquinas, assim como os seus limites teóricos.
Conteúdos programáticos Apresentação Contextual e Histórica da Teoria da computação
Modelos da computação: dos autómatos (de estados finitos, com pilha) às máquinas de Turing.
Modelos de computação alternativos: Funções recursivas de Kleene e calculo lambda.
Programação em modelos da computação.
Tese de Church-Turing. Provas de equivalência de modelos.
A não computabilidade e a indecidibilidade: Problemas indecidíveis, técnica da diagonalização, técnica da redução.
Metodologias de Ensino e Critérios de Avaliação Alteração dos critérios de avaliação para acomodar o período de confinamento e de emergência sanitária:

Substituição da prova escrita da avaliação contínua (a frequência) por uma componente prática suplementar: a resolução de dois exercícios de programação suplementares, elevando para 5 o número de exercícios para avaliação.
A cotação individual (máxima) de cada exercício é a seguinte:
A: 2.5
B: 5
C: 4.5
D: 4
E: 4

(continua em baixo))
Bibliografia principal * J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification. Springer-Verlag,2011.
* A. Arnold and I. Guessarian. Mathematics for Computer Science. Prentice-Hall, 1996.
* Chris Hankin. Lambda Calculi: A Guide for Computer Scientists, volume 3 of Graduate Texts in Computer Science. Clarendon Press, Oxford, 1994.
* J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata theory, languages, and computation. 3rd ed. Pearson education, 2006.
* Harry R. Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1997.
* P. Linz. An introduction to formal languages and automata. Jones and Bartlett Publisher, 2006.
* Dexter Kozen. Automata and Computability. Springer-Verlag, New York, 1997.
* Dexter Kozen. . Theory of Computation. Springer, New York, 2006.
Língua Português

Regente

Imagem d@ Simão Patricio Melo de Sousa [Ficheiro Local]
 Simão Patricio Melo de Sousa

Curso

Engenharia Informática
Data da última atualização: 2021-07-26
As cookies utilizadas neste sítio web não recolhem informação pessoal que permitam a sua identificação. Ao continuar está a aceitar a política de cookies.