Programação das aulas

Agosto

Setembro

• 10 de setembro:
  • Primeira prova
  • Lista 3
  Matéria da prova: material coberto dos capítulos 1, 2 e 3 do WS.

• 12 de setembro (Aula 9):
  • Bin packing
  Transparências [pdf] [ps.gz]
  Leitura recomendada: sec 3.3 do WS.

• 17 de setembro (Aula 10):
  • Escalonamento em uma máquina, minimizando a soma dos tempos de conclusão
  • Escalonamentos com interrupção e a regra SRPT
  • PLs com número exponencial de restrições
  Transparências [pdf] [ps.gz].
  Leitura recomendada: secs 4.1, 4.2, 4.3 do WS. Ficou interessado em saber um pouco mais sobre o Método dos Elipsóides? Dê uma olhada nas seguintes notas de aulas: lecture 8 e lecture 9.

• 19 de setembro (Aula 11):
  • Problema de Steiner com coleta de prêmios
  Leitura recomendada: sec 4.4 e começo da 4.5 do WS.
  Transparências: [pdf] [ps.gz]

• 24 de setembro (Aula 12):
  • Localização de facilidades
  • Lista 4
  Leitura recomendada: sec 4.5 do WS.
  Transparências: [pdf | ps.gz]

• 26 de setembro (Aula 13):
  • Algoritmos probabilísticos
  • MAX SAT e MAX CUT
  • Desaleatorização
  Leitura recomendada: secs 5.1 a 5.3 do WS. Leia também o cap 6 do livro de aproximação do CBM.
  Transparências: [pdf | ps.gz]