Teoria da Computação 

Disciplina da Secção de Lógica e Computação.

Cursos:
LEIC- Alameda (Licenciatura em Engenharia Informática e de Computadores). Ano: 1. Semestre: 2.
LEIC-Tagus (Licenciatura em Engenharia Informática e de Computadores). Ano: 1. Semestre: 2.
LERCI (Licenciatura em Engenharia de Redes de Comunicação e Informação). Ano: 1. Semestre: 1.

Professor Responsável: Paula Gouveia  (Alameda) //  João Rasga (Tagus).

Semestre corrente: Avisos e outras informações - Alameda // Tagus.

Objectivos gerais 

Desenvolver o raciocínio matemático rigoroso. Dominar os instrumentos matemáticos necessários para compreender os limites da computação e diversos modelos de computação.

Objectivos operacionais

Aprender a trabalhar com modelos computacionais comuns, desde os autómatos finitos às máquinas de registos. Entender e saber utilizar a teoria das linguagens regulares. Entender e saber utilizar os mecanismos da lógica clássica proposicional e de primeira ordem. Compreender o conceito de computabilidade e seus limites. 

Programa

Linguagens regulares: autómatos finitos deterministas, equivalência e minimização de autómatos finitos deterministas, autómatos finitos não deterministas, gramáticas, expressões regulares. Lógica clássica: sintaxe, semântica, cálculo de Smullyan, cálculo de Gentzen, resolução e cálculo de Hilbert. Computabilidade:  máquina URM, funções parciais recursivas, conjuntos recursivos e conjuntos recursivamente enumeráveis, existência de funções não computáveis, problemas clássicos da computabilidade e da decidibilidade (problema da paragem inter alia). Importância da noção de complexidade computacional.

Bibliografia básica

• N. Cutland. Computability: An Introduction to Recursive Function Theory.
  Cambridge University Press, 1980.
• P. Gouveia, C. Caleiro. Introdução à Teoria da Computação.
  DMIST, em preparação. 
• J. Kelly. The Essence of Logic.
  Prentice Hall, 1997.
• M. Sipser. Introduction to the Theory of Computation.
  PWS Publishing Company, 1997.
  

Bibliografia complementar

• J. Hopcroft, R. Motwani e J. Ullman. Introduction to Automata Theory, Languages, and Computation
  Addison Wesley, 2001.
• D. Mandrioli e C. Ghezzi. Theoretical Foundations of Computer Science.
  John Wiley, 1987.
  

Avaliação

Ficha electrónica (10%) e testes (90%).

Carga horária semanal

Aulas teóricas: 3h. Aulas práticas: 2h. Estudo recomendado: 3h.

Última actualização: 23 de Setembro de 2005.