Complexidade Computacional

Primeiro semestre de 2002

• Introdução [ps.gz] [pdf]

• Critério de avaliação e bibliografia

• As ementas abaixo estão um pouco desatualizada:
  • Programa de MAC 430
  • Programa de MAC 5722

• Programação das aulas

• Provas

• Listas de exercícios

• Lista de alunos

• Notas

• Recuperação

• Lista de discussão

• Comentários anônimos

Informações gerais

• Calendário da graduação.
• Calendário da pós-graduação.

Outras disciplinas sobre Complexidade Computacional na USP

• MAC-5722 (segundo semestre de 2000)
• MAC-5722 (primeiro semestre de 1998)
• MAC-5828 (segundo semestre de 1998)

Alguns links relacionados com tópicos do curso

• A compendium of NP optimization problems. Um catálogo de problemas de otimização junto com a classe de complexidade a que pertencem (se conhecido).
• Collection of Lecture Notes, Surveys, and Papers.
  This is a collection of some lecture notes, papers, ... that we have found in Internet. By no way this is a complete archieve, its primary aim is to serve the local needs of our research group and our students. So many of items are accessible only from Paderborn.
• Electronic Colloquium on Computational Complexity.
  Research reports, surveys and books in computational complexity
• Special Interest Areas. Contém vários links para sítios de geometria computacional e complexidade computacional.
• Arthur-Merlin site. Se você gosta de estórias em quadrinhos e está interessado em uma explicação simples de IP e PCP de uma olhada neste sítio.
• Theoretical computer science on the web. Contém links para páginas e artigos de interesse geral da comunidade de teoria.
• Demonstrações Transparentes e a Inaproximabilidade de Aproximações (livro do Prof. Yoshi e do Prof. José Augusto)
• The Complexity Theory Companion (livro recente de Hemaspaandra e Ogihara).