Programação das aulas de MAC6711

Março

Abril

Maio

Junho

• 2 de junho (Aula 18):
  • Análise amortizada: union-find
  Leitura recomendada: Secs 21.3 e 21.4 do CLRS e notas de aula [pdf].
  Entrevista curtinha com o Tarjan, que fez a análise justa do union-find.
  Slides [pdf].

• 6 de junho:
  • Segunda prova
  Matéria da prova: método guloso e análise amortizada (listas 4, 5, 6).

• 13 de junho (Aula 19):
  • Busca de padrão
  • Algoritmo de Boyer-Moore
  • Lista 7
  Leitura recomendada: Cap 13 do livro Algoritmos, do Prof. Paulo. (Veja as notas de aulas correspondentes na página dele.)
  Slides [pdf].

• 16 de junho (Aula 20):
  • Algoritmos para casamento estável
  • Lista 8
  Leitura recomendada: Sec 1.1 do KT. Por curiosidade, leia também essa página da wiki.
  Slides [pdf].

• 20 de junho (aula 21):
  • Algoritmos de aproximação
  • Problema dos k-centros: 2-aproximação
  • Problema do caixeiro viajante
  Leitura recomendada: Sec 11.1 e 11.2 do KT e Sec 2.4 deste livro de algoritmos de aproximação.
  Slides [pdf].

• 23 de junho (aula 22):
  • Busca local
  • Algoritmo Metropolis e simulated annealing
  • Redes neurais de Hopfield
  • Corte máximo num grafo
  • Lista 9
  Leitura recomendada: Secs 12.1 até 12.4 do KT.
  Se tiver curiosidade, veja também o artigo que propôs o resultado visto em aula. [pdf]
  Slides [pdf]

• 27 de junho (aula 23):
  • Algoritmos que executam para sempre...
  Leitura recomendada: Epílogo do KT.
  Slides [pdf]

• 30 de junho
  • Terceira prova
  Matéria da prova: