MAC323 - Estruturas de Dados

BCC - 1o. Semestre de 2001

Aulas

Março
  1. 2/3/2001 Discussão inicial. Ementa da disciplina, objetivos, conteúdo, critério de avaliação.
  2. 6/3/2001 Estruturas de dados compostas. Matrizes como vetor de vetores, alocação dinâmica [prog3.6.c, prog3.16.c]. Vetor de strings, ordenação de strings, uso de qsort() e bsearch() [prog3.17.c].
  3. 9/3/2001 Leitura de linhas de comprimento arbitrário [getline.h, getline.c]. Grafos, matriz de adjacência [prog3.18.c] e representação com listas ligadas [prog3.19.c]. Discussão de um problema geométrico. Suponha que são dados um inteiro N e um real d com 0<d<1. Suponha que geramos N pontos uniformemente ao acaso no quadrado de lado unitário e que queremos determinar quantos pares destes pontos distam a menos de d entre si. Esta é a solução imediata para este problema: Programa 3.8 do livro de Sedgewick (Arquivos auxiliares: Point.h e Point.c). Esta solução tem tempo de execução proporcional a N^2. O mensagem central desta aula foi que o uso de estruturas de dados conveniente podem contribuir de forma essencial no projeto de algoritmos mais eficientes. Esta é a solução deste problema com tempo de execução proporcional a d^2N^2 (que é muito bom pelo fato de ser menor para valores menores de d): Programa 3.20 de Sedgewick. (Note que este programa também ilustra alocação dinâmica de memória para matrizes.) Uma observação: o Programa 3.20 acima gasta quantidade de memória proporcional a 1/d^2+N^2. Assim, existe um preço a pagar; para tirar proveito de valores pequenos de d, gastamos mais memória.
  4. 13/3/2001 Tipos abstratos de dados. Exemplo de manipulação de números complexos. Veja os seguintes dois diretórios para duas implementações distintas: versão 1, versão 2 (estude estes exemplos com cuidado).
  5. 16/3/2001 Tabelas de símbolos. Este tipo abstrato de dados será muito importante durante o semestre. Veja este diretório para um exemplo completo (esta implementação mantém os objetos da tabela em uma lista ligada ordenada). Outras implementações de tabelas de símbolos. Como vetores característicos: prog12.3.c; como vetores mantendo os objetos ordenados: prog12.4.c. Discussão do primeiro EP e do primeiro desafio.
  6. 20/3/2001 Não haverá aula [Yoshi no Fortaleza Summer School on Algorithms and Combinatorics, Fortaleza, Ceará, 12 a 24 de março, 2001].
  7. 23/3/2001 Não haverá aula [Yoshi no Fortaleza Summer School on Algorithms and Combinatorics, Fortaleza, Ceará, 12 a 24 de março, 2001].
  8. 27/3/2001 Elementos básicos sobre árvores.
  9. 30/3/2001 Programas de pesquisa de nós de árvores: prog5.14.c, prog5.15.c, e prog5.16.c. Alguns outros programas de manipulação de árvores: prog5.17.c, e prog5.18.c. Tabelas de símbolos implementadas com árvores de busca binária: veja este diretório.
Abril
  1. 3/4/2001 Tabelas de símbolos implementadas com árvores de busca binária, continuação. Inserção sem recursão: prog12.7b.c. Relação entre as propriedades matemáticas das ABs e o desempenho de tabelas de símbolos implementadas com ABBs. Anúncio do segundo EP e do segundo desafio.
  2. 6/4/2001 Índices de textos: veja este diretório. Veja o 3o. Desafio na página dos desafios. Algoritmos de rotação de ABs: prog12.11.c. Inserção na raiz em uma AB: prog12.12.c (desafio: escreva uma versão não-recursiva deste algoritmo de inserção). Balanceamento explícito de uma AB: prog12.14.c e prog13.1.c.
  3. 10/4/2001 Semana Santa
  4. 13/4/2001 Semana Santa
  5. 17/4/2001 Discussão detalhada do EP2. Balanceamento explícito de uma AB (recapitulação). ABBs aleatórias. Inserção aleatória: prog13.2.c. ABBs construídas com inserções aleatórias dos itens, em ordem arbitrária, e ABBs construídas com a inserção dos itens em ordem aleatória; comprimento interno esperado e um resultado sobre grandes desvios. Remoção (determinística) de um item de uma ABB: prog12.15.c.
  6. 20/4/2001 Um pouco mais de operações probabilísticas sobre ABBs.
  7. 24/4/2001 Prova 1!
  8. 27/4/2001 Alguns comentários sobre a prova. Splay trees (self-adjusting BSTs). Veja os diretórios splay_BST, splay_BSTb, e splay_BSTb_noN.
Maio
  1. 1/5/2001 Feriado
  2. 4/5/2001 Árvores AVL e rubro-negras. A biblioteca libavl (veja a documentação e também um texto mais extenso disponível na página da biblioteca, em vários formatos). Várias implementações de tabelas de símbolos com uma pequeno teste comparativo de desempenho: veja este diretório.
  3. 8/5/2001 Hashing. Introdução. Veja este diretório para uma implementação inicial.
  4. 11/5/2001 Resolução de colisões: resolução por encadeamento e resolução por linear probing.
  5. 15/5/2001 Aula de discussão do EP3.
  6. 18/5/2001 [Nao teve aula: Semana de Estudos]
  7. 22/5/2001 Discussão final sobre hashing, com análise de desempenho. Várias implementações de hashing: veja este diretório.
  8. 25/5/2001 Árvores de busca digital. Tries e patricia tries. Veja este diretório para patricia tries.
  9. 29/5/2001 Continuação.
Junho
  1. 1/6/2001 Tries R-ários. Tries de busca ternários.
  2. 5/6/2001 Continuação.
  3. 8/6/2001 B-árvores, hashing extensível. Entrega do EP3 adiada para esta data (até as 18:00, na secretaria do MAC)
  4. 12/6/2001 Não haverá aula [Semana de Estudos]
  5. 15/6/2001 Não haverá aula [Semana de Estudos]
  6. 19/6/2001 Aula de exercícios.
  7. 22/6/2001 Prova 2!
  8. 26/6/2001 Prova 3!
  9. 29/6/2001 Não haverá aula.

Calendário

         Mar                       Apr        
 S  M Tu  W Th  F  S       S  M Tu  W Th  F  S
             1  2  3       1  2  3  4  5  6  7
 4  5  6  7  8  9 10       8  9 10 11 12 13 14
11 12 13 14 15 16 17      15 16 17 18 19 20 21
18 19 20 21 22 23 24      22 23 24 25 26 27 28
25 26 27 28 29 30 31      29 30               
		       			   
         May                       Jun	   
 S  M Tu  W Th  F  S       S  M Tu  W Th  F  S
       1  2  3  4  5                      1  2
 6  7  8  9 10 11 12       3  4  5  6  7  8  9
13 14 15 16 17 18 19      10 11 12 13 14 15 16
20 21 22 23 24 25 26      17 18 19 20 21 22 23
27 28 29 30 31            24 25 26 27 28 29 30
Página principal de MAC323 (BCC - 1o. Semestre de 2001)
Netscape-HTML Checked!
Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Sat Jun 30 14:03:48 BRST 2001