Programação das aulas de MAC5711

Primeiro semestre de 1999

• 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)
  • Cobertura por Conjuntos
  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

• 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