Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20082

Aprovado pelo Departamento em: 8-7-2008

  1. Identificação: Visualizar em PDF
    • 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
  2. Curso(s):
    • Ciências da Computação (208)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5317 - Linguagens Formais e Compiladores
  4. Ementa:
    • Noções de computabilidade efetiva. Modelos de computação. Problemas indicidíveis. Classes e relações de complexidade.
  5. Objetivo(s):
    • Geral: Apresentar os principais fundamentos da Teoria da Computação e suas conseqüências à análise de problemas.
    • Específicos:
      1. Introduzir a noção de computação.
      2. Apresentar a tese de Church-Turing e suas conseqüências ao estudo da computabilidade efetiva.
      3. Apresentar técnicas de análise de problemas sob a ótica da computabilidade e da decidibilidade.
      4. Apresentar o conceito de classes de complexidade de algoritmos e suas conseqüências a computabilidade prática.
      5. Introduzir o conceito de completeza NP.
      6. Apresentar o conceito de intratabilidade.
  6. 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
  7. 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.
  8. Bibliografia Complementar:
    • Wood, D., Theory of Computation, John Wiley & Sons, 1987.
    • Artigos selecionados.