Aulas

1. 8/agosto
   • 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. 10/agosto
   • 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. 15/agosto
   • Cap. 2 Algoritmos Clássicos
     • Empacotamento Unidimensional - não admite razão (absoluta) menor que 3/2, a menos que P= NP.
     • 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.
4. 17/agosto
   • Cap. 2 Algoritmos Clássicos
     • [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).
     • [EXTRA] Problema do Corte Multiseparador (multiway cut) Mínimo (notas de aula).
5. 22/agosto
   • Cap. 2 Algoritmos Clássicos
     • 2.3. Caixeiro Viajante
     • Lista 2.
     • [EXTRA] Caminhos Disjuntos nas Arestas [algoritmo guloso] (notas de aula).
6. 24/agosto
   • Cap. 2 Algoritmos Clássicos
     • Problema da Mochila - FPTAS
     • Problema da 2-Partição - PTAS (notas de aula)

7. 29/agosto
   • Cap. 3 Método Primal
     • Estudar em casa: Apêndice C do livro
     • Técnica do arredondamento; técnica métrica

   Semana da Pátria 4 a 10/set -- semana sem aulas na USP

8. 12/set
   • Cap. 4 Método Dual
9. 14/set
   • Cap. 5 Método Primal-Dual
     • Caso clássico
10. 19/set
    • Cap. 5 Método Primal-Dual
      • Caso aproximado
11. 21/set
    • Cap. 5 Método Primal-Dual
      • Transversal Mínima
      • [EXTRA] Cobertura
      • (Entregar Lista 4)
12. 26/set
    • Cap. 5 Método Primal-Dual
      • [EXTRA] Feedback vertex set
      • Floresta de Steiner
13. 28/set
    • Cap. 5 Método Primal-Dual
      • Floresta de Steiner
      • (Entregar Lista 5)
14. 3/out
    • Cap. 6 Algoritmos Probabilísticos
      • MaxSat
15. 5/out
    • Primeira Prova
    Semana do break -- 10 a 14 de outubro

16. 17/outubro
    • Cap. 6 Algoritmos Probabilísticos
      • MaxSat - PL e arredondamento probabilístico
      • Algoritmo combinado
17. 19/outubro
    • Cap. 6 Algoritmos Probabilísticos
      • [EXTRA] Jogando moedas tendenciosas (MaxSat)
      • [EXTRA] Jogando moedas tendenciosas (MinCV com pesos)
18. 21/outubro
    • Cap. 6 Algoritmos Probabilísticos
      • Desaleatorização
19. 26/outubro
    • Cap. 7 Programação Semidefinida
      • MaxCut - Goemans-Williamson
20. 28/outubro
    • Cap. 7 Programação Semidefinida (cont.)
      • [EXTRA] Max2Sat