Teoria da Computabilidade e Complexidade


Ementa

Estudo dos conjuntos enumeráveis e provas por diagonalização. Estudo da teoria das funções recursivas. Definições equivalentes de computabilidade. Discussão da Tese de Church- Turing. Estudo dos problemas decidíveis e do problema da parada. Estudo do conceito de redutibilidade e sua aplicação na determinação da indecidibilidade de problemas lógicos e computacionais. Estudo e aplicação das classes de complexidade de tempo: classe P, classe NP e NP-completude. Estudo e aplicação das classes de complexidade de espaço: classe PSPACE e PSPACE-completude.

Materiais existentes no momento:

Avaliação

G1 = (P1 + P2 + T) / 3

Bibliografia:

Básica:

Complementar: