Programa

Teoria da Computação

Licenciatura Bolonha em Engenharia Informática

Licenciatura Bolonha em Tecnologias de Informação

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). Definição formal e representação em forma de diagrama. Definição de computação. 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;