Aulas

1. 6/agosto (2af)
   • Uma visão geral dos tópicos que serão cobertos nesta disciplina (requisitos, textos, material disponível).
   • Cap. 1 Introdução: Conceitos básicos e notação.
2. 7/agosto (3af)
   • Cap. 2 Algoritmos Clássicos
     • 2.1. Escalonamento. Algoritmo de Graham. Complexidade computacional no caso de 2 máquinas (redução via Problema da Partição).
     • Cobertura de Vértices: uma 2-aproximação.
     • [EXTRA] Empacotamento Unidimensional (bin packing ). [First-Fit, Next-Fit]
     • Lista 1.
3. 13/agosto (2af)
   • Cap. 2 Algoritmos Clássicos
     • Empacotamento Unidimensional - não admite razão (absoluta) menor que 3/2, a menos que P= NP.
     • [EXTRA] Corte Máximo -- Dois algoritmos bem simples (com razão de aproximação 1/2): Algoritmo baseado em Busca Local e Algoritmo Guloso (notas de aula).
4. 14/agosto (3af)
   • Cap. 2 Algoritmos Clássicos
     • [EXTRA] Problema do Corte Multiseparador (multiway cut) Mínimo (notas de aula).
     • [EXTRA] Cobertura de vértices
5. 20/agosto
   • Cap. 2 Algoritmos Clássicos
     • 2.2. Cobertura por Conjuntos (set cover) - Introdução: relação com os problemas em grafos sobre cobertura de arestas (por vértices) e cobertura de vértices (por arestas), hipergrafos.
     • [EXTRA] Caminhos Disjuntos nas Arestas [algoritmo guloso] (notas de aula).
6. 21/agosto
   • Cap. 2 Algoritmos Clássicos
     • 2.3. Caixeiro Viajante
7. 27/agosto
   • Cap. 2 Algoritmos Clássicos
     • Problema da Mochila - FPTAS
     • Problema da 2-Partição - PTAS (notas de aula)

8. 28/agosto
   • Cap. 3 Método Primal
     • Estudar em casa: Apêndice C do livro
     • Técnica do arredondamento (MinCV, MinCC)

   Semana da Pátria 3 a 8/set -- semana sem aulas na USP

9. 10/set
   • Cap.3 Técnica métrica (MinMCut)

   11/set - Não houve aula

10. 17/set
    • Cap. 4 Método Dual (MinCV)
11. 18/set
    • Cap. 5 Método Primal-Dual
      • Caso Clássico x Caso aproximado
12. 24/set
    • Cap. 5 Método Primal-Dual
13. 25/setg
    • Cap. 5 Método Primal-Dual (cont.) - Cobertura Mínima por conjuntos (MinCC)
14. 1/out
    • Cap. 5 Método Primal-Dual (cont). - Transversal Mínima
15. 2/out
    • Cap. 5 Método Primal-Dual (cont.) - Floresta de Steiner
    • Cap. 6 Algoritmos Probabilísticos
      • Digressão
      • MaxSat