Teoria da Computabilidade e Complexidade

Objetivos

O cumprimento da disciplina busca dar ao aluno, ao final do semestre, condições de:

1. Compreender a noção de funções recursivas e recursivas primitivas;

2. Conhecer os princípios básicos da noção de computabilidade de Turing;

3. Compreender os limites da computação através do estudo de provas de indecidibilidade;

4. Conhecer os fundamentos da hierarquia de classes de complexidade de problemas computacionais e identificar problemas pertencentes às classes P, NP e PSPACE, suas características e importância na computação aplicada;

5. Compreender e aplicar a redutibilidade polinomial de problemas através do estudo de provas de NP- e PSPACE-Completude.

Ementa

Estudo dos conjuntos enumeráveis e provas por diagonalização. Estudo da teoria das funções recursivas. Definições equivalentes de computabilidade. Discussão da Tese de Church-Turing. Estudo dos problemas decidíveis e do problema da parada. Estudo do conceito de redutibilidade e sua aplicação na determinação da indecidibilidade de problemas lógicos e computacionais. Estudo e aplicação das classes de complexidade de tempo: classe P, classe NP e NP-completude. Estudo e aplicação das classes de complexidade de espaço: classe PSPACE e PSPACE-completude.

Programa

1. Conjuntos Enumeráveis e Funções Recursivas

   1. Conjuntos Enumeráveis
   2. Argumento Diagonal de Cantor e Conjuntos Incontáveis
   3. Funções Recursivas Primitivas e Funções Recursivas Parciais

2. Turing-Computabilidade

   1. Máquinas de Turing
   2. Linguagens Reconhecíveis e Decidíveis
   3. Variações de Máquinas de Turing
   4. Conjectura de Church-Turing
   5. Máquinas de Turing Universais

3. Problemas Indecidíveis

   1. Prova da Indecidibilidade do Problema da Parada
   2. Entscheidungsproblem e Introdução à Reducibilidade de Problemas
   3. Decidibilidade de Teorias Lógicas
   4. Teoremas de Gödel

4. Hierarquia de Classes de Complexidade de Problemas Computacionais

   1. Tipos de Problemas Computacionais
   2. Complexidade de Tempo e de Espaço
   3. Hierarquia de Classes de Complexidade de Problemas
   4. Classe P e exemplos de Problemas em P
   5. Classe NP
      1. Definição da classe
      2. Exemplos de problemas importantes em NP e suas aplicações industriais
      3. Teorema de Cook-Levin
      4. Redução polinomial de problemas
   6. Provas de NP-Completude
   7. Classe PSPACE
      1. Definição da Classe
      2. Exemplos de Problemas em PSPACE
      3. Provas de PSPACE-Completude
   8. Intratabilidade

Avaliação

G1 = (P1 + P2 + MT) / 3

Materiais existentes no momento:

• A lista de exercícios para praticar suas habilidades com máquinas de Turing!

• Uma apresentação muito interessante sobre como codificar Máquinas de Turing para serem executadas em uma Máquina de Turing Universal pode ser encontrado aqui e é tão legal que tem backup.

• Os filmes mostrando a máquina de Turing Universal em ação!

• Um vídeo explicando os conjuntos de Cantor, diagonalização e mostrando que existe o mesmo número de inteiros e de racionais, mas que a quantidade de números reais é infinita e ainda maior. Por isso, existem infinitos de vários tamanhos.

• Um interpretador bem legal para cálculo Lambda. Entre com as expressões e veja como elas são substituídas e reescritas.

• Um texto do Michael Sipser sobre a história da computabilidade está aqui.

• Computability and Complexity, um texto de Kleinberg e Papadimitriou que serve como introdução a várias ideias que veremos na disciplina. Leia e não se preocupe se não entender tudo, as peças devem se encaixar à medida que o semestre avançar.

• Um áudio da BBC sobre o Teorema de Gödel, muito legal.

• Uma apresentação feita na Eslovênia e explicando muita teoria da computabilidade (nossa disciplina vai até o capítulo 8, mais ou menos...)

• JFLAP, um software para experimentar com autômatos, máquinas de Turing e outra coisas legais.

• Uma animação sensacional explicando o problema da parada.

• Um áudio da BBC sobre P e NP, também é muito legal.

• Introduction to the theory of complexity, um livro de Bovet e Crescenzi que serve como roteiro (avançado) para o que veremos na disciplina. Treine seus poderes no capítulo 1, ao menos, e depois avance.

• O artigo histórico do Karp sobre reduções entre problemas NP!!

• O artigo sobre games e NP-completude!!

• On the Cruelty of Really Teaching Computer Science, um texto de E. W. Dijkstra, muito interessante. Descubra quem foi Dijkstra, depois leia o texto. São 30 páginas, mas é fácil e simples.

Bibliografia:

Básica:

• Michael Sipser, Introdução à Teoria da Computação, Cengage Learning, tradução da 2a edição norte-americana, 2012.

• Papadimitriou, Ch. H. Computational complexity. Addison-Wesley, 1994.

• Boolos, G., Burgess, J. and Jeffrey, R. Computability and Logic. Cambridge University Press, 5th edition, 2007.

Complementar:

• Lewis, Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.

• M. Garey, D.Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, New York, NY, W. H. Freeman, 1979.

• Peter Smith, An Introduction to Gödel's Theorems, Cambridge University Press, 2007.

• B. Reus. Limits of Computation: From a Programming Perspective, Springer Publishing Internacional, 2016.

• Davis, M., Sigal R., Weyuker, E. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. Morgan Kaufmann; 2 ed, 1994.