Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Está em: • 2021-1

Barra Lateral

Índice

inf05016:2021-1

Tabela de Conteúdos

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

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.

Locations of visitors to this page

inf05016/2021-1.txt · Esta página foi modificada pela última vez em: 2022/11/16 08:42 (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