MAC0423  Introdução à Teoria da Computabilidade

Por | Em

OBJETIVOS:  Estudo de funções computáveis, estabelecimento da existência de funções não computáveis.

PROGRAMA:  Formalização da noção de algoritmo. Enumeração de funções computáveis e a existência de funções universais. A existência de problemas indecidíveis. O teorema da recursão. Conjuntos recursivos e recursivamente enumeráveis. Outros modelos para computabilidade.

PRÉ-REQUISITOS:  MAC0121.

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada de provas e exercícios.

BIBLIOGRAFIA BÁSICA: 

  • M. Minsky, Computation: Finite and Infinite Machines, Prentice Hall, 1967.
  • H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981.
  • A.F. Kfoury, R.N. Moll, M.A. Arbib, A Programming Approach to Computability, Springer, 1982.

OBSERVAÇÃO:  Disciplina optativa eletiva no currículo do BCC.

 

[Veja dados da disciplina no JúpiterWeb]