Programação das aulas

Sujeito a mudanças...

Abaixo MR denota o livro de Motwani e Raghavan.

Agosto

Setembro

Outubro

• 4 de outubro (Aula 14):
  • algoritmo BPP resultante da construção da aula passada
  • obtenção de corpos de um certo tamanho
  • delimitações de Chernoff
  Avaliação intermediária: responda e me mande por email ao seguinte questionário respondido até o dia 12/10 (quinta).

• 6 de outubro (Aula 15):
  • delimitações de Chernoff para somas de variáveis 0-1.
  • método de Monte Carlo para estimar valores
  • algoritmo para estimar o valor de pi
  Leitura recomendada: sec 4.1 do MR.

• 11 e 13 de outubro:
  • Não haverá aula (segunda semana de break)

• 18 de outubro (Aula 16):
  • método Monte Carlo para #DNF

• 20 de outubro (Aula 17):
  • roteamento de pacotes no hipercubo

• 25 de outubro (Aula 18):
  • roteamento de pacotes no hipercubo - continuação
  • Lista 4
  Leitura recomendada: sec 4.2 do MR. Veja também as notas que preparei. [ps.gz] [pdf]

• 27 de outubro (Aula 19):
  • método probabilístico
  • método das esperanças condicionais
  MAX2SAT: Dada uma fórmula booleana em CNF em que cada cláusula tem no máximo dois literais, encontre uma atribuição para as variáveis da fórmula que satisfaça o maior número possível de cláusulas da fórmula.
  Exercício: Escreva uma 0.5-aproximação probabilística para o MAX2SAT. Desaleatorize esse algoritmo usando o método das esperanças condicionais.
  Exercício: O que acontece com esses algoritmos quando a fórmula dada tem apenas cláusulas com exatamente dois literais?

Novembro