Portal do Ementário

Apresentar os fundamentos da teoria da computação, permitindo ao aluno dominar os instrumentos matemáticos necessários para compreender e analisar os diversos modelos de computação.

Funções Computáveis. Funções Recursivas. Tese de Church. Máquinas de Turing. Decidibilidade. Computabilidade. Classes de Problemas.

DIVERIO, Tiarajú A.; MENEZES, Paulo B. "Teoria da Computação - Máquinas Universais e Computabilidade". 3a ed. Sagra-Luzzatto , 2011. SIPSER, Michael. “Introdução à Teoria da Computação”. 2a ed. Thompson Learning, 2007. LEWIS, Harry R.; PAPADIMITRIOU, Christos H. “Elementos de Teoria da Computação”. 2a ed. Bookman, 2000.

HOPCROFT, John E.; MOTWANI, Rajeev.; ULLMAN, Jeffrey D. “Introdução à Teoria de Autômatos, Linguagens e Computação”. Campus, 2003. GAREY, Michael R.; JOHNSON, David S. “Computers and Intractability: A Guide to the Theory of NP-Completeness”. W. H. Freeman, 1979.