Rogério Reis


Err and err and err again, but less and less and less.


Computabilidade e Complexidade (CC3004, CC333)

Stacks Image 6
Programa:
Noção de linguagem/problema (semi-)decidível. Revisão de alguns modelos de computação (DFA's, NFA's, CFG's e PDA's) e do seu poder computacional. Máquinas de registo. Tese de Church-Turing. Hierarquia de Chomsky. Estudo de outros modelos de computação Turing-completos e sua equivalência (máquinas de Turing, funções recursivas). Enumerabilidade efetiva das instâncias de um modelo de computação. Método da diagonalização e indecidibilidade do problema da paragem. Redução entre linguagens. Introdução à teoria de complexidade: classes P e NP; completude NP; teorema de Cook e outros problemas NP-completos.