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 Introdução à Lógica de Programação Introdução à Lógica Matemática

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 Introdução Noções preliminares Teoria dos Autômatos Linguagens Autômatos Finitos Expressões regulares Autômatos com Pilha Teoria da Computabilidade Máquina de Turing Tese de Church-Turing Máquina de Turing Universal Problema da Parada e Redutibilidade Teoria da Complexidade Análise assintótica Classe P Classe NP NP-Completude Otimização e busca: NP-Difícil