Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Está em: • inf05016

Barra Lateral

Índice

inf05016:homepage

Tabela de Conteúdos

Algoritmos avançados (INF 5009) (2025/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, 107/43413 (seg), 103/43425 (qua).
Consultas: a combinar.
Detalhes: Vê o programa e página da PPGC.

Resultados

Notícias

  • 10 de março: 1ᵒ dia de aula.

Materiais

Aulas

No. Data Tópicos Notas cap. Exercícios Soluções Leitura
1 10/03 Algoritmo de Dijkstra e Heaps binários. 1.1-1.4 KT2.5,C6
2 12/03 Laboratório 1 (Dijkstra). JEA, AM
3 17/03 Árvores geradoras, Fast marching method e A*. 1.1-1.4
4 19/03 Laboratório 2 (Dijkstra).
5 24/03 Tópicos em caminhos mais curtos. 1.5 KT4
6 26/03 Laboratório 3 (Dijkstra).
7 31/03 Fluxos em redes 1. 1.6 KT7.{1,2}
8 02/04 Laboratório 4 (Fluxos).
9 07/04 Fluxo em redes 2. 1.6 KT7.{2,3}
10 09/04 Laboratório 5 (Fluxos).
11 14/04 Fluxo em redes 3. 1.6 KT7.4
12 16/04 Laboratório 6 (Fluxos).
21/04 Tiradentes
13 23/04 Laboratório 7 (Fluxos).
14 28/04 Emparelhamentos 1. 1.7 KT7.5,K19
15 30/04 Laboratório 8 (Aplicação de fluxos).
16 05/05 Emparelhamentos 2. 1.7 K20
17 07/05 Laboratório 9.
18 12/05 Emparelhamentos 3. 1.7 K20
19 14/05 Laboratório 10.
20 19/05 Randomização 1. 4.1 MU1,KT13.2
21 21/05 Laboratório 11.
22 26/05 Randomização 2. 4.2 C31.8
23 28/05 Laboratório 12.
24 02/06 Randomização 3. 4.3-4.4 C31.8
25 04/06 Laboratório 13.
26 09/06 Problemas de amostragem discreta e contínua.
27 11/06 Laboratório 14.
28 16/06 Problemas de amostragem e contagem.
29 18/06 Tópicos 3. Revisão.
30 23/06 Prova P SP
Provas de recuperação (a serem combinadas).
19/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: 2025/07/01 18:44 (Edição externa)

Ferramentas de Página

Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki