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 e NP-Completo, Teorema de Cook-Levin.