Algoritmos avançados (INF 5016/CMP 588) (2014/2)

Beware of bugs in the above code; I have only proved it correct, not tried it. (Donald Knuth)

Bem-vindo.

Informações gerais

Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 2+2
Súmula: Algoritmos, estruturas de dados e técnicas algoritmicas avançadas: algoritmos randomizados, algoritmos de aproximação, algoritmos parametrizados.
Turma: U.
Horário/Sala: Seg/Qua 13.30-15.10, Sala 102, prédio 43424.
Consultas: Seg/Qua, 15.10-16.00, Sala 201, prédio 43425.
Detalhes: Vê o programa e página da PPGC.

Resultados

Notícias

Prova no dia 24 de novembro
Prazo final para entrega de trabalhos é dia 1 de dezembro

Materiais

Página da disciplina em 2013/2, 2012/2, 2011/2, 2010/2 e 2009/1.
Notas de aula (atualizado 2/9/2014).
Algumas demonstrações de algoritmos.
Dicas para os trabalhos experimentais.

Aulas

No.	Data	Tópicos	Notas cáp.	Exercícios	Soluções	Leitura
1	04/08	Introdução. Heaps binários.	1.1-1.3.1			KT2.5,C6
2	06/08	Laboratório 1
3	11/08	Heaps binomiais.	1.3.2			K8,C19
4	13/08	Laboratório 2
5	18/08	Caminhos mais curtos e A*	1.3,1.3.6
6	20/08	Laboratório 3.
7	25/08	Fluxo em redes 1.	1.4,1.4.1			KT7.{1,2}
8	27/08	Laboratório 4.
9	01/09	Fluxo em redes 2.	1.4.[234]			KT7.{2,3}
10	03/09	Laboratório 5.
11	08/09	Fluxo em redes 3.	1.4.[56]			KT7.4
12	10/09	Laboratório 6.
	15/09	Sem aula
13	17/09	Laboratório 7.
14	22/09	Emparelhamentos 1.	1.5,1.5.2			KT7.5,K19
15	24/09	Laboratório 8.
16	29/09	Emparelhamentos 2.	1.5.2			K20
17	01/10	Laboratório 9.
18	06/10	Emparelhamentos 3.	1.5.[13]			K20
19	08/10	Laboratório 10.
20	13/10	Randomização 1.				MU1,KT13.2
21	15/10	Laboratório 11.	4.1			KT13.6,C11
	20/10	Semana acadêmica
	22/10	Semana acadêmica
22	27/10	Randomização 2.	4.[23]			C31.8
23	29/10	Laboratório 12.
24	03/11	Randomização 3.	4.4			C31.8
25	05/11	Laboratório 13.
26	10/11	Aproximação 1.	3.[1234]
27	12/11	Laboratório 14.
28	17/11	Aproximação 2.	3.[567]
29	19/11	Parametrização.	5			KT10.1
30	24/11	Prova		P	S
	31/11	Prova de recuperação.
	1/12	Prazo final entrega de trabalhos

	20/12	Término oficial das aulas.

Livros: KT=Kleinberg/Tardos. K=Kozen, C=Cormen, et al.,V=Vazirani, MU=Mitzenmacher/Upfal

Bibliografia

Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
Jon Kleinberg and Éva Tardos. Algorithm design. Addison-Wesley, 2005.
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
Rolf Niedermeier. Invitation to fixed-parameter algorithms. Habilitationsschrift, Universität Tübingen, WSI für Informatik, Germany, September 2002.
Dexter Kozen. The design and analysis of algorithms. Springer, 1991.
Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, Dover edition, 1982.