Carga Horária Teórica: 60 Horas.
Carga Horária Prática: 0 Horas.

Número de Créditos: 4.

Ementa: A noção de algoritmo. Funções parcialmente recursivas. Computabilidade das funções parcialmente recursivas. Máquinas de Turing. Tese de Church. Função e máquina universal. Conjuntos recursivamente enumeráveis.

Bibliografia Básica:

- Garey, M.R. & Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. W.H. Freeman and Company, 1979.
- Aho, A.E.; Hopcroft, J.E. & Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974.
- Hopcroft, J.E. & Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
- Algorithms in C, Robert Sedgewick, Addison-Wesley, 1997.
- Estruturas de Dados usando C, Tenenbaum et al., Makron Books, 1995.