Programa

Teoria da Computação

Licenciatura Bolonha em Matemática

Licenciatura Bolonha em Engenharia Informática

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.