Teoria da Computabilidade e Complexidade
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.
Materiais existentes no momento:
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 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 á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 interpretador bem legal para cálculo Lambda. Entre com as expressões e veja como elas são substituídas e reescritas.
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.
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.
Um áudio da BBC sobre P e NP, também é muito legal.
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.
G1 = (P1 + P2 + T) / 3
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.
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.