Disciplina Curricular

Teoria da Computação TComput

Licenciatura Bolonha em Engenharia Informática - 3_Plano 2015/16

Contextos

Grupo: 3_Plano 2015/16 > 1º Ciclo > 3º Ano

Período:

Peso

6.0 (para cálculo da média)

Objectivos

Pretende-se que o aluno: 1. seja capaz de representar problemas reais utilizando modelos computacionais abstratos (autómatos finitos deterministas e não deterministas, gramáticas livres de contexto, máquinas de Turing); 2. seja capaz de identificar as capacidades e limitações dos vários modelos computacionais; 3. compreenda processos simples de análise sintática; 4. seja capaz de classificar um problema como “Turing-reconhecível” ou “Turing-decidível”; 5. compreenda e seja capaz de avaliar a complexidade de um problema e a diferença entre problemas tratáveis e intratáveis.

Programa

Linguagens regulares: Autómatos finitos deterministas (DFA) e não-deterministas (NFA). Def. formal e representação diagramática. Def. de computação. Linguagem reconhecida por um autómato finito. Equivalência entre DFAs e NFAs. Expressões regulares. Operações regulares. Lema do Bombeamento. Linguagens livres de contexto: Gramáticas livres de contexto. Derivação. Árvore sintática. Linguagem gerada. Ambiguidade. Formas normais. Autómatos de pilha. Análise sintática. Lema do Bombeamento. Teoria da Computabilidade: Máquinas de Turing. Variantes de Máquinas de Turing e equivalência ao modelo padrão. A tese de Church-Turing. Linguagens computáveis (decidíveis). O problema da paragem. Noção de redução entre linguagens e seu uso em (in)decidibilidade. Teorema de Rice. Teorema da Recursão. Teoria da Complexidade: Definição formal. Classes de complexidade. As classes P e NP. NP-completude. Uso da redução em tempo polinomial para provas de NP-completude.