UNIVERSIDADE DO ESTADO DE SANTA CATARINA - UDESC

TEORIA DA COMPUTAÇÃO (TEC0003)

Ementa:

Histórico e contextualização da Computação. Máquinas de Turing. Relações entre modelos de computabilidade e suas equivalências. Problema da Parada. A Tese de Church-Turing. Indecidibilidade. Redutibilidade de linguagens e de problemas. Complexidade de Tempo: análise de algoritmos, as classes de problemas P, NP, NP-Completo e coNP, Teorema de Cook-Levin.