Marcus Ritt

Ferramentas de Utilizador

Ferramentas de Site

Está em: • 2014-2

Barra Lateral

Índice

inf05016:2014-2

Tabela de Conteúdos

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

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.

Locations of visitors to this page

inf05016/2014-2.txt · Esta página foi modificada pela última vez em: 2015/07/16 10:24 por marcus

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