5. Atividades para avaliação do aprendizado do aluno

• Listas de exercícios (entrega obrigatória)
• Provas (início ou meados de abril e meados de junho) <=============
• Possivelmente um seminário a ser dado pelo aluno -- vai depender do tamanho da turma e outros fatores

6. Listas de exercícios

• Lista 0. Antes de fazer as listas de exercícios regulares, ler pelo menos as 10 primeiras páginas do livro Mathematical Writing. Para ter acesso à versão disponível em pdf, veja o item acima sobre ¨Outros textos recomendados (para melhorar a formação)¨. De tempos em tempos, ler e reler este e outros textos recomendados, principalmente se você vai escrever sua dissertação ou um artigo.
• Lista 1. Entregue na aula do dia 05/março. [Resolver até 9/março.]
• Lista 2. Entregue na aula do dia 09/março. [Resolver até 16/março.]
• Lista 3. Entregue na aula do dia 16/março. [Resolver até 23/março.]
• Lista 4. Entregue na aula do dia 02/abril. [Resolver até 13/abril.]
• Lista 5. Entregue na aula do dia 27/abril. [Resolver até 7/maio.]
• Lista 6. Entregue na aula do dia 11/maio.
• Lista Extra. Enviada por e-mail no dia 05/junho.

7. Aulas

1. 02/março - Introdução
   • Uma visão geral dos tópicos que serão cobertos nesta disciplina (requisitos, textos, material disponível).
   • Cap.1 Introdução (definições básicas e notação).
2. 05/março
   • Cap.2 Algoritmos Clássicos
     • 2.1. Escalonamento. Algoritmo de Graham. Complexidade computacional no caso de 2 máquinas.
     • [EXTRA] II-Extra.1. Empacotamento Unidimensional (bin packing ). [First-Fit, Next-Fit]
3. 09/março
   • Cap.2 Algoritmos Clássicos
     • [EXTRA] II-Extra.2. 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 produzidas por Bruno Takahashi)
     • 2.2. Cobertura por Conjuntos (set cover) - relação com os problemas em grafos sobre cobertura de arestas por vértices e cobertura de vértices por arestas, hipergrafos.
4. 12/março
   • Cap.2 Algoritmos Clássicos
     • 2.2. Cobertura por Conjuntos (cont.)
     • [EXTRA] II-Extra.3. Corte Multiseparador Mínimo (multiway cut) [algoritmo guloso] (notas de aula)
       
     • [EXTRA] II-Extra.4. Caminhos Disjuntos nas Arestas [algoritmo guloso] (notas de aula)
5. 16/março
   • Cap.2 Algoritmos Clássicos
     • Comentários e esclarecimento de dúvidas sobre o Problema dos Caminhos Disjuntos nas Arestas (aula de 12/03).
     • TSP - O Problema do Caixeiro Viajante.
     • Entrega da Lista 3 (de exercícios). <==== (Veja o item 6 acima)
6. 19/março
   • Cap.2 Algoritmos Clássicos
     • TSP - O Problema do Caixeiro Viajante Métrico: dois algoritmos de aproximação com razão constante.
     • Esquema de aproximação polinomial (PTAS) e esquema de aproximação plenamente polinomial (FPTAS)
       • O Problema da Mochila -- algoritmo exato (pseudo-polinomial) e um FPTAS que faz uso desse algoritmo exato
7. 23/março
   • Cap.2 (cont. extra) Esquema de aproximação polinomial (PTAS).
     • [EXTRA] II-Extra.5. Problema da 2-Partição Mínima (balanceada) (notas de aula produzidas por Rafael da Ponte Barbosa)
       
     • [EXTRA] II-Extra.6. Problema do Conjunto Independente Máximo em grafos planares. (Conceito de grafo exoplanar, k-exoplanar, existência de algoritmo polinomial exato para grafos k-exoplanares.) [Notas de aula sob responsabilidade de Joel S. Uchoa] OBS: No algoritmo dado em aula, considerar k = chão de (1/epsilon).
8. 26/março
   • Cap.3 Método Primal
     • Técnica do arredondamento
       • Problema da Cobertura de Vértices (MinCV)
       • Problema da Cobertura por Conjuntos (MinCC); MinCV visto como MinCC, e generalização para o MinCC do algoritmo e da análise feita para o MinCV.
9. 30/março
   • Cap.3 Método Primal (cont.)
     • Técnica métrica
       • Problema do Multicorte Mínimo (MinMCut); PL de tamanho exponencial; o problema da separação; interpretação da solução como comprimento das arestas, e função objetivo como volume do sistema de tubulação definido pelas arestas do grafo.
10. 02/abril
    • Cap.4 Método Dual
      • Método Dual simples e Dual Maximal.
      • [EXTRA] Dual Fitting (notas de aula produzidas por César Gamboa) <======
      • Entrega da Lista 4 (de exercícios)

    SEMANA DO BREAK --- 6 a 10/abril --- semana sem aulas

11. 13/abril
    • Cap.5 Método Primal-Dual
      • O Método Primal-Dual Clássico (para achar solução exata)
12. 16/abril
    • 1a. PROVA
13. 23/abril
    • Cap.5 Método Primal-Dual
      • Método de Aproximação Primal-Dual
      • Problema da Transversal Mínima
14. 27/abril
    • Cap.5 Método Primal-Dual
      • Problema da Transversal Mínima (continuação)
      • Problema da Floresta de Steiner
      • Entrega da Lista 5 (de exercícios) <==== (Veja o item 6 acima)
15. 30/abril
    • Cap.5 Método Primal-Dual
      • Problema da Floresta de Steiner (continuação)
16. 04/maio
    • Cap.5 Método Primal-Dual
      • Problema da Localização de recursos ( Facility Location Problem)
17. 07/maio
    • Cap.6 Algoritmos Probabilísticos
      • Algoritmos para o Max-3SAT
18. 11/maio
    • Cap. 6 Algoritmos Probabilísticos
19. 14/maio
    • Cap.6 Algoritmos Probabilísticos
      • Desaleatorização - método das esperanças condicionadas

    SEMANA DO BREAK -- 18 a 22/maio

20. 25/maio
    • Cap.7 Programação Semidefinida
      • O problema do corte máximo (algoritmo probabilístico de Goemans-Williamson)
21. 27/maio
    • Cap.7 Programação Semidefinida
      • [EXTRA] O problema do Max2SAT (algoritmo probabilístico)
22. 01/junho
    • Cap.8 Inaproximabilidade
      • Classes de problemas de otimização NPO
      • NP-completude e inaproximabilidade
23. 04/junho
    • Cap.8 Inaproximabilidade
      • Completude para problemas de otimização
      • AP-redução (Max3SAT para MaxClique)
24. 08/junho
    • Cap.8 Inaproximabilidade
      • Limiares de aproximação
      • [EXTRA] A técnica do gap para prova de limiar de aproximação
      • [EXTRA] PCP (Probabilistically Checkable Proofs); nova caracterização da classe NP; Teorema: NP = PCP (log n, 1); consequëncias desse teorema sobre inaproximabilidade: MaxSAT não admite um PTAS.

    RECESSO ESCOLAR -- 11/junho (Corpus Christi), 12 e 13 de junho.

25. 15/junho -- Mais sobre inaproximabilidade

26. 18/junho 2a. prova (início: 8 horas) <=============