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

A disciplina tem três temas: (0) Modelação de sistemas usando conjuntos, (1) Linguagens Formais e Autómatos, centrado na definição de linguagens por gramáticas e seu reconhecimento por autómatos, com relevância para o processamento de linguagens. (2) Teoria da Computabilidade, que formaliza a noção de algoritmo (tese de Church-Turing) e estuda as suas limitações, com relevância para o estabelecimento da insolubilidade de certos problemas.

Objectivos

Objectivos

Saber
Fazer
Soft-Skills
Programa

1. Modelação usando Teoria de Conjuntos e Lógica Matemática

Conjuntos, Aplicações, Relações

Finito e Infinitos, diagonalização.

Definições Indutivas

Modelação de Sistemas e Tipos de Dados Abstractos

2. Sintaxe e Semântica

Sintaxe Abstracta

Sintaxe Concreta (BNF)

Modelos e Interpretaçõoes

Refinamento de Tipos Abstractos de Dados

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

Modelos de Computação (Panorâmica)

Autómatos Finitos e Expressões Regulares; Determinismo e não Determinismo.

Linguagens independentes de Contexto e Autómatos de Pilha

Algoritmos de Análise Sintática (LL(1), LR)

4. Computabilidade

Complexidade Básica

Equivalencia de programação imperativa e funcional.

Universalidade Turing (usando uma linguagem imperativa).

Tese de Church-Turing.

Incompletude Turing (indecidabilidade do problema da terminação, indecidabilidade doproblema de decisão da lógica de primeira ordem)


Bibliografia Principal

Material didático

Bibliografia recomendada

Os seguintes livros são recomendados:

Requisitos Prévios

Os alunos deverão ter realizado previamente as unidades curriculares de Introdução à Programação e de Matemática Discreta.

Esforço do Aluno
  Horas por crédito 28
  Horas p/ semana Semanas Horas
Aulas teóricas 2 14 28.0
Aulas teórico-práticas 3 14 42.0
Avaliação   6.0
Estudo   92.0
Total de Horas 168
ECTS 6.0