CI709 - Teoria da Computação
optativa: CI339 - Complexidade Computacional
1º semestre de 2009

Ementa:

1. Algoritmos.
2. Computabilidade.
3. A classe de complexidade P.
4. A classe NP e NP-completude.
5. A classe de complexidade P-espaço.

Objetivos: A compreensão das limitações do modelo computacional e da dificuldade inerente de se resolver poblemas computacionais algoritmicamente.

Carga horária: 60 Créditos: 4

Bibliografia:

1. Michael Sipser, Introdução à Teoria da Computação, Editora Thompson, Tradução 2a. ed., 2007.
2. M.R. Garey e D.S. Johnson, Computers and intractability :a guide to the theory of NP-completeness, San Francisco, W.H. Freeman, 1979.

Bibliografia complementar


3. C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
4. J.E. Hopcroft e J.D. Ullman, R. Motwani, Introdução à Teoria de Automatos, Linguagens e Computação, Ed. Campus.

Material na web


5. P, NP and Mathematics - a computational complexity perspective. A. Wigderson. Proceedings of the ICM 06 (Madrid), vol. 1, EMS Publishing House, Zurich, pp. 665-712, 2007.
6. Draft of Computational Complexity: A Modern Approach Textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.
7. Great Ideas in Theoretical Computer Science, Scott Aaronson, MIT.
8. Complexity Theory - Material. Oded Goldreich.
9. Leonid A. Levin. Fundamentals of Computing.
10. Computation Complexity Lecture Notes by Laszlo Lovasz and Peter Gacs.

Sistema de avaliação

O aluno será avaliado com base nos exercícios/trabalhos em sala de aula, apresentação de seminário, preparação de listas de exercícios, prova e projeto final da disciplina. A média final será obtida da seguinte forma:

• Exercicios / trabalhos: 33%
• Apresentação de seminario: 33%
• Provas: 33%

Calendário:

• 02/03 - Início das aulas.
• 09/04 - Prazo final para protocolar cancelamento de disciplinas semestrais da graduação.
• 13/04 - Prazo final para protocolar cancelamento de disciplinas semestrais da pós-graduação.
• 23/06 - Prova.
• 26/06 - Último dia letivo.

Listas:

• 1a. Lista de exercícios - Computabilidade
• 2a. Lista de exercícios - Complexidade

Links:

• Electronic Colloquium on Computational Complexity.
• Computational Complexity of Games and Puzzles
• Computational complexity theory and Computability From Wikipedia, the free encyclopedia.
• P versus NP Clay Mathematics Institute
• The Complexity Zoo
• A compendium of NP optimization problems
• Turin machine simulator
• The LEGO Turing Machine:
  

Tópicos das aulas

Aula 01 - Apresentação.
Aula 02 - Revisão: Conjuntos, Funções, Notação assintótica.
Aula 03 - Revisão: Problemas x Algoritmos. Codificação.
Aula 04 - 
Aula 05 - Máquinas de Turing.
Aula 06 - Enumerabilidade.
Aula 07 - Codificação de Máquinas de Turing. 
Aula 08 - Máquina de Turing universal.
Aula 09 - Funções/Linguagens recursuivas e recursivamente enumeraveis.
Aula 10 - O problema da parada e outros exemplos de linguagens indecidíveis.
Aula 11 - 
Aula 12 - Redutibilidade.
Aula 13 - 
Aula 14 - Classes de complexidade P e NP.
Aula 15 - Redutibilidade com restrição de tempo.
Aula 16 - 3sat <=p clique, clique <=p vertex-cover.
Aula 17 - NP-completude
Aula 18 - Circuitos booleanos
Aula 19 - P esta em P/poly
Aula 20 - semana academica
Aula 21 - CIRCUIT-SAT é NP-completo
Aula 22 - coP e coNP
Aula 23	- P-espaco
Aula 24 - 
Aula 25 e 26 - 02 e 05/06 - seminário
Aula 27 e 28 - 16 e 19/06 - seminário 
Aula 29 e 30 - 23 e 25/05 - seminario 
      

Temas para os seminários

1. máquinas RAM e equivalencia com maquinas de Turing.
2. circuitos booleanos e modelos de computação não-uniforme.
3. Teorema da recursão e aplicações.