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 Expressões regulares o O lema de pumping • Linguagens livres de contexto. o Gramáticas livres de contexto. 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: • Classes de complexidade P e NP. • Completude-NP. • Usar redução em tempo polinomial para provar completude-NP