Teoria da Computação (2017/2018) - Departamento de Informática
Descrição

Usar a lógica e a teoria de conjuntos para modelar dados e sistemas. Conhecer os fundamentos teóricos da computação, o conceito formal de algoritmo e a existência de problemas indecidíveis. Conhecer as classes de linguagens formais, os modelos computacionais associadas e a sua relação mútua. Compreender o conceito de universalidade Turing.

Modelar o espaço de estados de sistemas com conjuntos e lógica de 1º ordem. Distinguir conjuntos contáveis de não contáveis. Modelar sistemas com autómatos finitos (DFA e NFA). Construir um autómato dada uma expressão regular e o inverso. Construir um DFA equivalente a um NFA. Definir linguagens independentes de contexto com gramáticas. Construir analisadores LL e LR. Reconhecer a (in)decidibilidade de problemas computacionais.

Programa

1. Modelação com Conjuntos e Lógica

Conjuntos, Funções, Relações (revisão). Finito e Infinito, argumento diagonal de Cantor. Diferença entre função e algoritmo. Definições indutivas. Modelos de sistemas simples e tipos abstractos de dados.

2. Máquinas, Autómatos e Especificações

O que é um modelo computacional? Automátos finitos deterministas e expressões regulares. Determinismo e não determinismo. Linguagens independentes de contexto e máquinas de pilha. Análise sintática (LL e LR).

3. Computabilidade

Complexidade básica (P,NP). Expressividade computacional. Equivalência entre programação funcional e imperativa. Máquinas abstractas e níveis de interpretação. Universalidade Turing. Tese de Church-Turing. Indecidibilidade (da terminação).


Bibliografia Principal

Notas da UC ITC (Luís Caires, 2011).

Christos Papadimitriou and Harry Lewis: “Elements of the theory of computation”, Prentice-Hall, 1982, second edition 1997.

Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Total de Horas 0
ECTS 6.0