Programa

Fundamentos da Computação

Mestrado Bolonha em Ciência Cognitiva

Programa

Linguagens e modelos de computação: • Linguagens regulares o Autómatos finitos deterministas (AFD) e não deterministas (AFN). o Definição formal e representação diagramática. o Definição formal de computação. o A linguagem reconhecida por um autómato finito. o Equivalência AFD e AFN. o Expressões regulares. o Operações sobre expressões regulares: união, concatenação e estrela. o Expressões regulares e linguagens regulares. o O lema de pumping. • Linguagens livres de context. o Gramáticas livres de contexto. o derivação; Árvore de parsing; A linguagem da gramática; Ambiguidade. o Autómatos de pilha. • Linguagens computáveis o Máquinas de Turing. o Variantes de máquinas de Turing e equivalência. o Máquina de Turing universal. o A tese de Church-Turing. Decidibilidade: • Linguagens computáveis (decidíveis) e semi-decidíveis. Redução por mapeamento entre linguagens e o seu uso para provar (in)decidibilidade. o Existência de linguagens não-decidíveis. o O problema da paragem (Halting problem). o O teorema de Rice. Complexidade temporal: • Definição. • Classes de complexidade P e NP. • Completude-NP. • Usar redução em tempo polynomial para provar completude-NP