Teoria da Computação

Ementa

Bem vindo ao curso Teoria da Computação

Objetivo
Fornecer ao aluno uma visão que o leve a analisar, avaliar e entender problemas reais sob o ponto de vista da computabilidade e complexidade dos mesmos.

Nível do curso
Superior.

Pré-requisito

Programa
Teoria dos autômatos: linguagens; hierarquia de Chomsky; reconhecedores e geradores; autômatos finitos; autômatos com pilha; lema do bombeamento. Teoria da computabilidade: máquinas de Turing; variações de máquinas de Turing; tese de Church; decidibilidade; problema da parada; redutibilidade. Teoria da complexidade: complexidade de tempo; classes de problemas; NP-completude; teorema de Cook-Levin; NP-difícil.

Bibliografia

SIPSER, M. Introdução à Teoria da Computação, 2ª Edição, Editora: Cengage Learning, 2011.
DIVERIO, T. A.; MENEZES, P. B.Teoria da Computação - Máquinas Universais e Computabilidade, 3ª Edição, Volume. 5, Editora: Artmed, 2011.
HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J. D. Introdução À Teoria de Autômatos, Linguagens e Computação, 1ª Edição, Editora: Campus, 2002.
VIEIRA, N. J. Introdução aos Fundamentos da Computação - Linguagens e Máquinas, 1ª Edição, Editora: Thomson Pioneira, 2006.
COELHO, F.; PEDRO NETO, J. Teoria da Computação - Computabilidade e Complexidade, 1ª Edição, Editora: Escolar Editora / Zamboni, 2010.

Índice de aulas