Programação das aulas

Sujeito a mudanças...

Abaixo MR denota o livro de Motwani e Raghavan.

Agosto

• 9 de agosto (Aula 1):
  • Informações gerais [ps.gz] [pdf]
  • Aquecimento: busca aleatória [ps.gz] [pdf]

• 11 de agosto (Aula 2):
  • Algoritmo para corte mínimo de Karger
  • Lista 1 (veja abaixo o que é para entregar!)
  Leitura recomendada: sec 1.1 do MR.

• 16 de agosto (Aula 3):
  • Algoritmos para k-caminhos
  Leitura recomendada: parte das notas de aula [ps.gz] [pdf] do curso Probabilistic Algorithms de Anupan Gupta.
  Exercícios da lista 1 que você deve entregar até a aula de quarta da semana que vem (dia 23): 1(b), 5 e 6.

• 18 de agosto (Aula 4):
  • Classes de complexidade probabilísticas: RP, coRP, ZPP, BPP.

• 23 de agosto (Aula 5):
  • Mais sobre complexidade: PP, relação entre as classes P, NP e as probabilísticas
  • Princípio das decisões postergadas (PDP)
  • Dois exemplos: clock solitaire e casamentos estáveis
  • Lista 2
  Leitura recomendada: sec 1.5 (complexidade) e 3.5 (PDP e exemplos) do MR.
  Veja também o zoo de complexidade.

• 25 de agosto (Aula 6):
  • Verificação de produto de matrizes
  • Verificação de igualdade de polinômios
  Leitura recomendada: cap 7, secs 7.1 e 7.2.

• 30 de agosto:
  • Não houve aula.

Setembro

Outubro

Novembro