Programação das aulas de MAC5711
Primeiro semestre de 1999
Mês de Março
- 15 de março (aula 1):
- Introdução [ps |
pdf]
- Cobertura de Vértices: método guloso e método de
arredondamento
- Lista 1 [ps |
tex |
pdf]
Leitura recomendada:
- Para uma revisão de complexidade, veja aqui
[ps |
pdf].
- Para uma revisão de programação linear, veja o Cap 10 do
Vazirani ou Cap 5 do Chvátal.
- 17 de março (aula 2):
- Programação linear - uma revisão rápida
- Método dual para Cobertura de Vértices
- 22 de março (aula 3)
Leitura recomendada: Parte do Cap 11 e do Cap 2 do Vazirani
ou Sec 3.2 e 3.3 da Hochbaum ou ainda Lec 2 do Williamson.
- 24 de março (aula 4)
- Método Primal-Dual - uma descrição geral
- Método Primal-Dual para Cobertura por Conjuntos
- Lista 2 [ps |
tex |
pdf]
Leitura recomendada: Cap 13 do Vazirani
- 29 de março (aula 5)
- Método Primal-Dual para Multicortes em Árvores
Leitura recomendada: Cap 14 do Vazirani
- 31 de março (aula 6)
- Exemplos: diferença entre o método dual e o primal-dual
- Métodos Primal-Dual para Steiner Trees
Leitura recomendada: Cap 15 do Vazirani
Mês de Abril
- 5 de abril (aula 7)
- Métodos Primal-Dual para Steiner Trees
- Métodos Métricos: Multicortes
- Lista 3 [ps |
tex |
pdf]
Leitura recomendada: Seção 5.2 da Hochbaum ou Cap 17 do Vazirani
- 7 de abril (aula 8)
- Métodos Métricos: Multicortes
- 12 de abril (aula 9)
- Métodos Métricos: Cortes Balanceados
Leitura recomendada: Seção 5.1 da Hochbaum
- 14 de abril (aula 10)
- Divisão e Conquista: Arranjo Linear
Leitura recomendada: Seção 5.5 da Hochbaum
Matéria da prova: notação assintótica, recorrências, ordenação
(capítulos 1, 2.1, 4.1, 4.2, 7, 8, 9.1 do CLR).
-->
Segunda parte do cronograma
Last modified: Wed Apr 26 19:34:44 BRT 2000