Algoritmos avançados (INF 5016/CMP 588) (2021/1)

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, Zoom.
Consultas: No discord (Convite).
Detalhes: Vê o programa e página da PPGC.

Resultados

Notícias

29 de agosto: Nova versão das Notas de aula publicada.
26 de agosto: Material do Lab 2 é disponível.
26 de agosto: Nova versão das Notas de aula publicada.
11 de agosto: Página atualizada.
9 de agosto: Material da terceira aula é disponível.
5 agosto: nova versão das Notas de aula publicada.

Materiais

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

Aulas

No.	Data	Tópicos	Notas pág.	Exercícios	Soluções	Leitura
1	02/08	📢 Algoritmo de Dijkstra e Heaps binários.	5-15			KT2.5,C6
2	04/08	Laboratório 1 (Dijkstra).
3	09/08	📢 Fast marching method e A*.	42-48
4	11/08	📢 Laboratório 2 (Dijkstra).
5	16/08	Árvores geradoras mínimas e arborescências				KT4
6	18/08	📢 Laboratório 3 (Dijkstra).
7	23/08	Fluxos em redes 1.	49-57			KT7.{1,2}
8	25/08	📢 Laboratório 4 (Arborescências).
9	30/08	Fluxo em redes 2.	57-59			KT7.{2,3}
10	01/09	📢 Laboratório 5 (Arborescências).
11	06/09	Fluxo em redes 3.	60-69			KT7.4
12	08/09	📢 Laboratório 6 (Arborescências).
13	13/09	Emparelhamentos 1.	70-74			KT7.5,K19
14	15/09	📢 Laboratório 7 (Fluxos).
	20/09	Revolução Farroupilha
15	22/09	Emparelhamentos 2.	74-83			K20
16	27/09	📢 Laboratório 8 (Fluxos).
17	29/09	Emparelhamentos 3.	84-87			K20
18	04/10	📢 Laboratório 9 (Fluxos).
19	06/10	Emparelhamentos 4.	84-87			K20
	11/10	Sem aula
20	13/10	📢 Laboratório 10 (Emparelhamentos).
21	18/10	Randomização 1.	129-138			MU1,KT13.2
22	20/10	📢 Laboratório 11 (Emparelhamentos).
23	25/10	Randomização 2.	138-146			C31.8
24	27/10	📢 Laboratório 12 (Emparelhamentos).
25	01/11	Hashing 1.	89-95			KT13.6,C11
26	03/11	📢 Laboratório 13.
27	08/11	Hashing 2.	95-98			KT13.6,C11
28	10/11	📢 Laboratório 14.
	15/11	Proclamação da República
29	17/11	Aproximação.	99-108
30	22/11	Prova		P	SP
		Provas de recuperação (a serem combinadas).

	04/12	Término oficial das aulas.

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

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.