Complexidade de Algoritmos
2008

Professores

Celina M. H. de Figueiredo, Guilherme Dias da Fonseca, Rafael Bernardo Teixeira

Horário e local

Aulas: 2^as e 6^as, das 10:00 às 12:00, na sala H-304 A

Calendário

Semana	Assunto	Professor
15/09	Introdução	Guilherme
22/09	Divisão e Conquista	Guilherme
29/09	Programação Dinâmica	Guilherme
06/10	Método Guloso	Rafael
13/10	Matroides	Rafael
20/10	Backtracking	Rafael
27/10	Outros paradigmas	Guilherme
03/11	Revisão e prova	Rafael
10/11	Computabilidade, P e NP	G. e R.
17/11	Teorema de Cook, NP-Completos	Guilherme
24/11	Reduções entre problemas NP-Completos (figura)	Rafael
01/12	Algoritmos Aproximativos e Revisão	Guilherme
12/12	Prova dia 12/12	Rafael

Provas

1^a Prova 1 - 07/11
2^a Prova - 12/12

Listas de exercícios

Lista 1 Entrega na aula de 24/10.
Lista 2 Entrega na aula de 03/11.
Lista 3 Entrega na aula de 05/12.

Bibliografia

Introduction to Algorithms, T. H. Cormen, C. Stein, R. L. Rivest, C. E. Leiserson, McGraw-Hill, 2001.
Algorithm design, J. Kleinberg, E. Tardos, Addison-Wesley, 2005.
Algorithms, S. Dasgupta, C. H. Papadimitriou, U. Vazirani, McGraw-Hill, 2006.
Computers and Intractability: A Guide to the Theory of NP-Completeness, M. R. Garey, D. S. Johnson, W. H. Freeman, 1979. Veja também NP-Completeness Columns.
Computational Complexity, C. H. Papadimitriou, Addison Wesley, 1994.
Combinatorial Optimization: Algorithms and Complexity, C. H. Papadimitriou, K. Steiglitz, Dover, 1998.
Uma Introdução Sucinta a Algoritmos de Aproximação, Marcelo Henriques de Carvalho, Márcia Rosana Cerioli, Ricardo Dahab, Paulo Feofiloff, Cristina Gomes Fernandes, Carlos Eduardo Ferreira, Katia Silva Guimarães, Flávio Keidi Miyazawa, José Coelho de Pina Jr., José Augusto R. Soares, Yoshiko Wakabayashi
Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag, 2001.