Programação das aulas de MAC6711
Primeiro semestre de 2018
Março
Abril
Maio
Junho
- 5 de junho (aula 19):
- Algoritmos de aproximação
- Escalonamento: algoritmo de Graham
- Problema dos k-centros: 2-aproximação
Leitura recomendada: Sec 11.1 e 11.2 do KT.
Slides [pdf].
- 8 de junho (aula 20):
- Algoritmos de aproximação
- Problema do caixeiro viajante
- Problema da cobertura por conjuntos
Leitura recomendada: Sec 11.3 e 11.6 do KT.
Slides [pdf].
- 12 de junho (aula 21):
- Busca local
- Algoritmo Metropolis e simulated annealing
Leitura recomendada: Sec 12.1 a 12.4 do KT.
Slides [pdf]
- 15 de junho (aula 22):
- Algoritmos que executam para sempre...
Leitura recomendada: Epílogo do KT.
Se tiver curiosidade, veja também o artigo que propôs o resultado visto em aula.
[pdf]
- 19 de junho:
Matéria da prova: clustering,
union-find, análise amortizada, tabelas dinâmicas, busca de
padrão, e temas finais.