Programação das aulas de MAC5711

Primeiro semestre de 1999

Mês de Abril

Meses de Maio e Junho

• 12 de maio (aula 16):
  • Programação dinâmica [cap 16, sec 16.2 do CLR]
  • Multiplicação de matrizes em cadeia [sec 16.1 do CLR]
• 14 de maio (aula 17):
  • Subseqüência comum de comprimento máximo [sec 16.3 do CLR]
• 19 de maio (aula 18):
  • Estrutura de dados para grafos [sec 23.1 do CLR]
  • Busca em largura [sec 23.2 do CLR]
• 21 de maio (aula 19)
  • Busca em profundidade [sec 23.3 do CLR]
  • Árvore geradora mínima [cap 24]
  • Algoritmo de Kruskal
  • Lista 6 [ps | tex | pdf]
• 26 de maio (aula 21)
  • Algoritmo de Prim
  • Algoritmos gulosos [sec 17.2 do CLR]
• 28 de maio (aula 22)
  • Busca de padrão [sec 34.1 do CLR]
  • Algoritmo de Knuth, Morris e Pratt (KMP) [sec 34.4 do CLR]
• 2 de junho (aula 23)
  • Teoria de Complexidade [sec 36.1 e 36.2 do CLR]
• 4 de junho (feriado)
  • Teoria de Complexidade [sec 36.3 do CLR]
• 9 de junho (aula 24)
  • Teoria de Complexidade [sec 36.4 do CLR]
• 11 de junho (aula 25)
  • Teoria de Complexidade [sec 36.5 do CLR]
• 16 de junho (aula 26)
  • Ajuste de cronograma
• 18 de junho
  • Prova 3 [ps | pdf]
  Matéria da prova: método de Strassen, programação dinâmica, algoritmos de busca em grafos (DFS e BFS), árvores geradoras mínimas (Kruskal e Prim), busca de padrão (KMP) e teoria de complexidade (P, NP, reduções, NP-completude).