Ferramentas de Utilizador

Ferramentas de Site


inf05016:homepage

Algoritmos avançados (INF 5009/CMP 588) (2024/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, 109/43413.
Consultas: a combinar.
Detalhes: Vê o programa e página da PPGC.

Resultados

Notícias

  • 18 de março: 1o dia de aula.

Materiais

Aulas

No. Data Tópicos Notas cap. Exercícios Soluções Leitura
1 18/03 Algoritmo de Dijkstra e Heaps binários. 1.1-1.4 KT2.5,C6
2 20/03 Laboratório 1 (101, Dijkstra). JEA, AM
3 25/03 Árvores geradoras, Fast marching method e A*. 1.1-1.4
4 27/03 Laboratório 2 (101, Dijkstra).
5 01/04 Tópicos em caminhos mais curtos. 1.5 KT4
6 03/04 Laboratório 3 (101).
7 08/04 Fluxos em redes 1. 1.6 KT7.{1,2}
8 10/04 Laboratório 4 (101).
9 15/04 Fluxo em redes 2 (113/43425). 1.6 KT7.{2,3}
10 17/04 Laboratório 5 (102).
11 22/04 Fluxo em redes 3. 1.6 KT7.4
12 24/04 Laboratório 6 (101).
13 29/04 Emparelhamentos 1. 1.7 KT7.5,K19
01/05 Dia do Trabalho
14 06/05 Emparelhamentos 2. 1.7 K20
15 08/05 Laboratório 7 (102).
16 13/05 Emparelhamentos 3. 1.7 K20
17 15/05 Laboratório 8 (101).
18 20/05 Emparelhamentos 4. 1.7 K20
19 22/05 Laboratório 9 (101).
20 27/05 Randomização 1. 4.1 MU1,KT13.2
21 29/05 Laboratório 10 (101).
22 03/06 Randomização 2. 4.2 C31.8
23 05/06 Laboratório 11 (102).
24 10/06 Randomização 3. 4.3-4.4 C31.8
25 12/06 Laboratório 12 (102).
26 17/06 Aproximação. 3
27 19/06 Laboratório 13 (101).
28 24/06 Hashing. 2.3-2.4 KT13.6,C11
29 26/06 Laboratório 14 (101).
30 01/07 Prova
Provas de recuperação (a serem combinadas).
20/07 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.

Locations of visitors to this page

inf05016/homepage.txt · Esta página foi modificada pela última vez em: 2024/03/20 13:01 (Edição externa)