Computabilidade | Anderson Almeida Ferreira

Universidade Federal de Ouro Preto – UFOP

Instituto de Ciências Exatas e Biológicas – ICEB

Departamento de Computação – DECOM

Disciplina: Computabilidade – BCC243 – 2/2011

Turma: 11

Prof. Anderson Almeida Ferreira

Objetivo:

Ao final do curso espera-se que os alunos possuam os seguintes conhecimentos e habilidades: compreensão dos conceitos de computabilidade e decidibilidade de problemas e compreensão sobre a distinção entre algoritmos das classes P e NP.

Ementa:

Tese de Church. Problemas Indecidíveis. Teorema da Incompletude de Godel. Classes de Problemas P, NP, NPCompleto e NP-Difícil. Métodos de Redução de Problemas.

Conteúdo Programático:

Tese de Church-Turing
Decidibilidade
Redutibilidade
Complexidade de Tempo

Processo Avaliativo:

03 avaliações teóricas:

Avaliação 1 – 03/10/2011 - Valor: 25,0 pontos
Avaliação 2 – 07/11/2011 - Valor: 25,0 pontos
Avaliação 3 – 12/12/2011 - Valor: 25,0 pontos

Listas de exercícios - 25,0 pontos
Notas

Material Didático:

Transparências de aula:

Apresentação da disciplina

Tese de Church: Máquinas de Turing, Variantes de Máquinas de Turing, Modelos Universais
Decidibilidade: Problemas Algoritmicos, Linguagens não Decidíveis, Redutibilidade
Complexidade de tempo: Complexidade de tempo, NP, NP-Completo

Exercícios

Ferramentas

JFlap

Leitura

Bibliografia:

M. SIPSER, Introduction to the Theory of Computation, PWS Publishing Company, 1996.
N. J. VIEIRA, Introdução aos Fundamentos da Computação, Pioneira Thomson Learning, 2006.
T. A. SUDKAMP, Languages and machines: an introduction to the theory of computer science, Pearson Education, 2006.
J. E. HOPCROFT, R. MOTWANI, J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, 3/e, Pearson Education, 2006.
Daniel I. A. Cohen, Introduction to Computer theory, Willey, 1997.

Última Atualização: 05/12/11