MAC338 Análise de Algoritmos

BCC - 1o. Semestre de 2000

Aulas

  1. 22/2/2000 Discussão inicial. Ementa da disciplina, objetivos, conteúdo, critério de avaliação.
  2. 25/2/2000 Introdução a grafos, discussão inicial. Representação de grafos: listas de adjacência e matrizes de adjacência. Busca em largura. Discussão informal da correção do algoritmo de busca em largura para o cálculo das distâncias dos vértices de um vértice dado. Notação O (noções).
  3. 29/2/2000 Busca em largura (continuação). Busca em profundidade. Os timestamps d[u] e f[u]. Complexidade da busca em profundidade.
  4. 3/3/2000 Busca em largura (continuação). A floresta de busca em profundidade e suas propriedades. Classificação das arestas/arcos do grafo de acordo com o resultado da busca.
  5. 7/3/2000 Carnaval! Recesso Escolar
  6. 10/3/2000 Classificação das arestas/arcos do grafo de acordo com o resultado da busca (continuação). Busca em profundidade e ordenação topológica de um grafo orientado acíclico.
  7. 14/3/2000 Um truque de baralho (aula apresentada pelo prof. José Coelho de Pina Jr). Alguns problemas relacionados com este truque aparecem em um desafio.
  8. 17/3/2000 Ordenação topológica (continuação).
  9. 21/3/2000 Componentes fortemente conexas. O algoritmo de Kosaraju e Sharir (introdução).
  10. 24/3/2000 Componentes fortemente conexas. O algoritmo de Kosaraju e Sharir (continuação).
  11. 28/3/2000 Árvores geradoras mínimas. O algoritmo genérico.
  12. 31/3/2000 Árvores geradoras mínimas. Um critério para arestas permissíveis, o algoritmo de Kruskal.
  13. 4/4/2000 Algoritmo de Kruskal. Estruturas de dados para Union-Find (representação de partições "decrescentes" de conjuntos). Veja http://www.linux.ime.usp.br/~yoshi/mac338/code/Union_Find para os programas de Sedgewick e um gerador de grafos aleatórios.
  14. 7/4/2000 Mais estruturas de dados para Union-Find (o uso de árvores). A heurística dos pesos.
  15. 11/4/2000 Latin 2000, aula de exercícios (Orlando Lee)
  16. 14/4/2000 Latin 2000, aula de exercícios (Orlando Lee)
  17. 18/4/2000 Semana Santa, recesso escolar
  18. 21/4/2000 Semana Santa, recesso escolar
  19. 25/4/2000 Prova 1
  20. 28/4/2000 Union-Find, parte final (análise do algoritmo de Kruskal; compressão de caminhos). Algoritmo de Prim, introdução a filas de prioridade.
  21. 2/5/2000 Filas de prioridade. Implementações (vetores não-ordenados e heaps): Item.h, prog9.1.c, prog9.2.c, prog9.3.c, prog9.4.c, prog9.5.c. Construção de um heap em tempo linear: prog9.7.c
  22. 5/5/2000 Construção de heaps em tempo linear (continuação). A soma das alturas dos nós de uma árvore binária completa.
  23. 9/5/2000 Reunião sobre o BCC; não houve aula.
  24. 12/5/2000 O algoritmo de Dijkstra. Implementação com filas de prioridade, complexidade, e correção. Os invariantes do laço principal do algoritmo de Dijkstra para a demonstração da correção do algoritmo.
  25. 16/5/2000 Correção do algoritmo de Dijkstra (continuação). O caso de grafos com arcos de comprimento negativo.
  26. 19/5/2000 Quicksort. Veja nos diretórios quicksort1 e quicksort2 duas versões do quicksort. A diferença está no algoritmo de partição. Exemplo de uso dos programas em quicksort1 (o uso dos programas no outro diretório é o mesmo). Número esperado de comparações no caso de uma entrada aleatória uniforme.
  27. 23/5/2000 Quicksort (continuação). Número esperado de comparações no caso de uma entrada aleatória uniforme e discussão sobre a variância. Aplicação da desigualdade de Chebyshev. Remoção da recursividade, tamanho máximo da pilha. Uso de insertion sort. Median-of-three. Uma versão incrementada do quicksort pode ser vista no diretório quicksort3.
  28. 26/5/2000 Mergesort. Propriedades básicas. Intercalação (merge) de dois vetores ordenados: prog8.1.c. Algoritmo in-place abstrato: prog8.2.c. O diretório mergesort1 contém uma implementação básica do mergesort (versão top-bottom). Veja o uso destes programas neste arquivo. Análise de correção e complexidade do mergesort (início).
  29. 30/5/2000 Complexidade do mergesort (continuação). Mergesort com melhoramentos: mergesort2. Mergesort para listas: mergesort3. (Outras versões de quicksort: quicksort4 e quicksort3b)
  30. 2/6/2000 (mergesort2b) Radix sort. Versões do radix sort LSD (least significant digit): radixsort1, radixsort2 (o sort_drive gera numeros em um dado intervalo; o programa de ordenacao é o mesmo). Estes programas podem ser usados para experimentar com o quicksort aplicado a strings: quick_string (neste diretório você encontra o texto de Hamlet, para usar como entrada do sort_drive). No diretório radix_string, você encontra um programa de ordenação que usa quicksortX() do livro do Sedgewick (programa 10.3 da Seção 10.4).
  31. 6/6/2000 Busca. A noção de tabelas de símbolos. A interface e uma implementação básica (com listas ligadas) pode ser vista no diretório STs. Tabelas de símbolos com árvores de busca binária (ABBs); veja STs_BST. Árvores binárias de busca aleatórias.
  32. 9/6/2000 Árvores binárias de busca aleatórias: profundidade média dos nós internos e nós externos. Análise da altura esperada. Análise do problema de determinação do máximo de uma seqüência aleatória.
  33. 13/6/2000 Árvores binárias de busca aleatórias, análise da altura, continuação. (ABBs)
  34. 16/6/2000 Aula de exercícios
  35. 20/6/2000 Prova 2
  36. 23/6/2000 Recesso escolar
  37. 27/6/2000 Não houve aula
  38. 30/6/2000 Não houve aula
  39. 4/7/2000 Prova 3 - Cobre todo o material do semestre
  40. 7/7/2000 Não houve aula
  41. 11/7/2000 Aula de despedida. Aula extra sobre programação dinâmica. Fibonacci prog5.11.c. O problema da mochila prog5.12.c, prog5.13.c. O problema da subseqüência comum mais longa [lcs.dvi.gz | lcs.ps.gz | lcs.pdf.gz | lcs.w.gz].

Calendário

       Fev             Mar             Abr             Mai             Jun
  S  T  Q  Q  S   S  T  Q  Q  S   S  T  Q  Q  S   S  T  Q  Q  S   S  T  Q  Q  S
               
                        1  2  3   3  4  5  6  7   -  ?  ?  ?  ?            1  2
                  -  -  -  9 10  10 11 12 13 14   8  9 10 11 12   5  6  7  8  9
                 13 14 15 16 17  -- -- -- -- --  15 16 17 18 19  12 13 14 15 16
 21 22 23 24 25  20 21 22 23 24  24 25 26 27 28  22 23 24 25 26  19 20 21  -  -
 28 29           27 28 29 30 31                  29 30 31        26 27 28 29 30

 ? = Semana do S. ?
Página principal de MAC338 (BCC - 1o. Semestre de 2000)
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Tue Jul 11 20:29:07 BRT 2000