Programação das aulas

Sujeito a mudanças...

Abaixo MR denota o livro de Motwani e Raghavan.

Agosto

Setembro

Outubro

Novembro

• 1 de novembro (Aula 20):
  • método probabilístico: prova da existência de um algoritmo de roteamento que consome número linear em n de bits aleatórios e tem tempo esperado linear em n.
  Leitura recomendada: sec 5.4 do MR.
  Exercícios para entregar: 1, 5, 7, 8 e 10 da L4, para dia 10/11. Se não der para entregar todos na sexta, você pode entregar alguns na semana seguinte sem problemas, mas entregue pelo menos uns dois ou três na sexta...

• 3 de novembro:
  • Não houve aula (finados)

• 8 de novembro (Aula 21):
  • Algoritmo de Miller-Rabin
  Leitura recomendada: sec 31.8 do CLRS.

• 10 de novembro (Aula 22 - previsão):
  • Algoritmo de Miller-Rabin (continuação da análise)
  • Algoritmo de Solovay-Strassen
  Leitura recomendada: sec 14.6 do MR. Veja também as notas de aulas. [ps.gz] [pdf]

• 15 e 17 de novembro:
  • Não haverá aula (terceira semana de break)

• 22 de novembro (Aula 23):
  • Análise do algoritmo de Solovay-Strassen
  • Cadeias de Markov e passeios aleatórios
• 24 de novembro (Aula 24):
  • Algoritmo para 2-SAT
  • Algoritmo para 3-SAT
  Leitura recomendada: sec 7.1 do MU. Veja também as notas de aulas [ps.gz] [pdf]

• 29 de novembro:
  • Não houve aula

• 1 de dezembro:
  • Não houve aula
• 6 de junho (Aula 25):
  • Seminário do Domingos
• 8 de junho:
  • Não houve aula