Programa de Ensino 20082
Aprovado pelo Departamento em: 8-7-2008
- Identificação:
- Disciplina: INE5372 - Teoria da Computação
- Carga horária: 72 horas-aula
Teóricas: 72
Práticas: 0
- Período:
Início da oferta da disciplina até a presente data
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- Ciências da Computação (208)
- INE5317 - Linguagens Formais e Compiladores
- Ementa:
- Noções de computabilidade efetiva. Modelos de computação. Problemas indicidíveis. Classes e relações de complexidade.
- Objetivo(s):
- Geral: Apresentar os principais fundamentos da Teoria da Computação e suas conseqüências à análise de problemas.
- Específicos:
- Introduzir a noção de computação.
- Apresentar a tese de Church-Turing e suas conseqüências ao estudo da computabilidade efetiva.
- Apresentar técnicas de análise de problemas sob a ótica da computabilidade e da decidibilidade.
- Apresentar o conceito de classes de complexidade de algoritmos e suas conseqüências a computabilidade prática.
- Introduzir o conceito de completeza NP.
- Apresentar o conceito de intratabilidade.
- Conteúdo Programático:
- Introdução [02 horas-aula]
- Preliminares (Revisão) [02 horas-aula]
- Conjuntos e relações
- Funções
- Grafos
- Predicados
- Indução matemática
- Aritmética
- Linguagens (Revisão) [04 horas-aula]
- Operações
- Fechamento de Kleene
- Linguagens regulares
- Gramáticas
- Modelos de Computação [12 horas-aula]
- Autômatos
- Máquinas de Turing
- Outros modelos
- Computabilidade [14 horas-aula]
- Máquinas de Turing universais
- Problemas computáveis e não computáveis
- A tese de Church-Turing
- Funções recursivas parciais
- Decidibilidade [14 horas-aula]
- O método da diagonal de Cantor
- O problema da parada
- O problema da correspondência de Post
- Problemas indecidíveis
- Noções de reducibilidade
- Complexidade [24 horas-aula]
- Ordens assintóticas
- Complexidade no tempo
- A classe P
- A classe NP
- Completeza NP
- O teorema Cook-Levin
- Problemas NP-completos
- Complexidade no espaço
- O teorema de Savitch
- A classe PSPACE
- As classes L e NL
- Noções de intratabilidade
- Bibliografia Básica:
- Hopcroft, J.E., Ullman, J., Introduction to Automata Theory, Languages and Computation, 2a. Edição, Addison-Wesley, 2001.
- Sipser, M., Introduction to the Theory of Computation, 2a. Edição, PWS Publishing, 2006. (Versão em português “Introdução à Teoria da Computação - 2a ed.”, editora Thomson Pioneira.)
- Lewis, H.R., Papadimitriou, C.H., Elementos de Teoria da Computação, 2a. edição, Bookman, 2000.
- Sudkamp, T.A., Languages and Machines, Addison-Wesley, 1988.
- Bibliografia Complementar:
- Wood, D., Theory of Computation, John Wiley & Sons, 1987.
- Artigos selecionados.