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 compreenda: como se podem representar problemas reais utilizando modelos computacionais abstratos; as capacidades e limitações relativas dos vários modelos; as relações entre linguagens e modelos; o conceito de uma linguagem "ser reconhecível" num determinado modelo de computação; que há linguagens que são indecidíveis, em especial no modelos das Máquina de Turing; o conceito de complexidade de um problema, conseguindo determinar a complexidade de alguns problemas; e, finalmente, a diferença entre tratável e intratável.
Programa
1. Modelos de computação para: 1.1 Linguagens regulares: 1.1.1 Autómatos finitos: Autómatos finitos deterministas (DFA) e não-deterministas (NDFA). Linguagem reconhecida por um autómato finito. Equivalência DFA e NDFA. 1.1.2 Expressões regulares: operações de união, concatenação e fecho de Kleene para expressões regulares. Expressões regulares e linguagens regulares. Equivalência com os autómatos. 1.1.3 Lema de Bombeamento: Prova e aplicação do Lema de Bombeamento. Como demonstrar que há linguagens não regulares. 1.2 Linguagens livres de contexto. 1.2.1 Gramáticas livres de contexto: Definição formal; noção de derivação; Árvore sintática. Linguagem gerada. Ambiguidade. Formas normais. 1.2.2 Autómatos de pilha: Noção de PDA; computação num PDA; Derivação; Equivalência às CFG. 1.3 Linguagens computáveis: 1.3.1 Máquinas de Turing: Definição e variantes de Máquinas de Turing (e.g.: deterministas e não deterministas). Equivalência ao modelo padrão. Criação de máquinas de Turing. Computação numa MT. Máquinas enumeradoras. Descrição de alto nível. 1.3.2 A tese de Church-Turing. 2 Decidibilidade: 2.1 Noção de decidibilidade (ou computável ou recursiva) e semi-decidibilidade (ou reconhecível ou recursivamente enumerável). Diferenças entre decidibilidade e semi-decidibilidade; 2.2 Linguagens decidíveis e reconhecíveis. 2.3 Indecidibilidade e o problema da paragem e suas variações. 2.4 Noção de redução entre problemas e e seu uso em indecidibilidade. 2.5 O Teorema de Rice. 3. Complexidade 3.1 Noções de complexidade: temporal e espacial; 3.2 Avaliar a complexidade; 3.3 Classes de complexidade temporal: a classe $P$ dos problemas com resolução eficiente; a classe $NP$ dos problemas com uma solução verificável; a classe dos Problemas $NP$ difíceis e $NP$ completos; a questão $P$ vs $NP$ e implicações; reduções polinomiais;
Métodos de ensino e avaliação
Aulas teóricas de exposição da matéria e aulas teórico-práticas de resolução de exercícios. Avaliação contínua (3 valores); exame escrito final (17 valores).