MAC323 - Estruturas de Dados

1o. Semestre de 2013

Sinopse das aulas

[Fevereiro | Março | Abril | Maio | Junho]

Fevereiro
- (Aula 0) 26/2/2013 Discussão inicial sobre a disciplina. Veja informações gerais sobre esta edição de MAC323. A noção de tipo. O esquema cliente/interface/implementação. Exemplo simples: veja este diretório.
- (Aula 1) 28/2/2013 O esquema cliente/interface/implementação (continuação). Um problema geométrico: contagem de pares de pontos que distam no máximo um dado valor; veja este diretório.
Março
- (Aula 2) 5/3/2013 O esquema cliente/interface/implementação (continuação). Mais exemplos: o problema de Josephus, listas ligadas (recaptulação), gerenciamento de memória para listas ligadas; veja este diretório.
- (Aula 3) 7/3/2013 Alocação dinâmica de matrizes. Strings: a biblioteca string.h. Um exemplo de uso da função qsort(). Veja este diretório.
- (Aula 4) 12/3/2013 Leitura de cadeias de caracteres de comprimento arbitrário (a função GetLine() em getline). Discussão do enunciado do EP1. Grafos: introdução. Literatura indicada sobre grafos: sítio do texto Exercícios de teoria dos grafos. Veja este diretório.
- (Aula 5) 14/3/2013 Aula de responsabilidade do monitor Antonio Josefran Oliveira Bastos (modularização, o utilitário make, declarações de variáveis globais em programas compostos de vários módulos, argumentos na linha de comando).
- (Aula 6) 19/3/2013 Grafos: continuação. Exercício: escreva um algoritmo/programa que (a) dados dois vértices u e v de um grafo, encontra os vizinhos comuns a esses dois vértices e (b) dado um vértice u de um grafo, listar todos os vértices v que tem pelo menos um vizinho comum com u. Veja este diretório (inclui exemplo com parsing de argumentos na linha de comando (my_cat.c) e um Makefile genérico para programas em C.) Relações binárias, reflexivas, simétricas, transitivas, relações de equivalência. Como calcular a menor relação de equivalência gerada por uma relação?
- (Aula 7) 21/3/2013 Tipos abstratos de dados. Exemplos: uso do tipo Item; pilhas e filas; relações de equivalência. Tipos abstratos de dados de primeira classe. Exemplos: números complexos; uso de handles. Veja este diretório.
- 26/4/2012 Semana Santa: Recesso escolar
- 28/4/2012 Semana Santa: Recesso escolar
Abril
- (Aula 8) 2/4/2013 Tabelas de símbolos. Discussão inicial. Veja este diretório. Neste diretório encontram-se versões que usam o gerador de números aleatórios do SGB, The Stanford GraphBase, de Knuth (veja SGB). O módulo de geração de números aleatórios do SGB é o gb_flip.
- (Aula 9) 4/4/2013 Tabelas de símbolos. Continuação. Veja este diretório (não deixe de ver também o material da aula de 2/4/2013).
- (Aula 10) 9/4/2013 Árvores binárias (ABs) e árvores binárias de busca (ABBs). Tabelas de símbolos com ABBs. ABs e ABBs típicas; veja este texto (Notes.pdf). Tabelas de símbolos com ABBs. Implementação: veja este diretório.
- (Aula 11) 11/4/2013 Árvores binárias (ABs) e árvores binárias de busca (ABBs). Continuação. EP2. Breve discussão do enunciado. P1. Breve discussão.
- (Aula 12) 16/4/2013 Prova 1 [PDF]
- 18/4/2013 Aula cancelada (professor fora do país)
- (Aula 13) 23/4/2013 Árvores binárias de busca (ABBs). Continuação. Rotações de ABBs Inserção de um elemento na raiz de uma ABB. Seleção em ABBs. Veja este diretório. O campo N. Exercício. Modifique as rotinas de manipulação de árvore, incorporando o campo N. Implementação das rotinas de partição e remoção de uma ABB: veja este diretório. (Supondo que temos o tipo de tabelas de símbolos implementado como um tipo de primeira classe, isto é, que podemos ter várias instâncias delas, e usamos ABBs para implementá-las, a rotina de união de duas tais tabelas pode ser implementada dessa forma: prog12.16.c.)
- (Aula 14) 25/4/2013 Evolução de uma ABB. Resultado da evolução de uma ABB de 650 nós, após 60 milhões de remoções e inserções aleatórias (30 milhões de cada, alternadas): exemplo 1, exemplo 2; observa-se uma degradação da "aleatoriedade" da árvore. Os programas que geraram esses diagramas estão neste diretório. ABBs balanceadas. Balanceamento explícito de uma ABB: prog13.1.c (Exercício: experimente essa função; gere diagramas). ABBs aleatorizadas (ABBAs). Evolução de ABBAs: resultado da evolução de uma ABBA de 650 nós, após 60 milhões de remoções e inserções aleatórias (30 milhões de cada, alternadas): exemplo 1, exemplo 2; não há degradação da "aleatoriedade" da árvore. As rotinas de inserção e remoção aleatorizadas estão incorporadas neste programa (veja este diretório).
- 30/4/2013 Semana de break
- 2/5/2013 Semana de break
Maio
- (Aula 15) 7/5/2013 Árvores 2-3. Veja a Seção 3.3 de Sedgewick e Wayne. Árvores rubro-negras esquerdistas (ARNEs). Algoritmos de busca e inserção.
- (Aula 16) 9/5/2013 Árvores rubro-negras esquerdistas (ARNEs). Algoritmos de busca e inserção.
- (Aula 17) 14/5/2013 ARNEs: algoritmo de inserção. Veja o código de Sedgewick (Java): RedBlackBST.java. Tradução minimal para C: llrb.c.
- (Aula 18) 16/5/2013 Árvores 2-3 e ARNEs. Algoritmos de remoção: remoção do mínimo.
- (Aula 19) 21/5/2013 Árvores 2-3 e ARNEs. Algoritmos de remoção: remoção geral. Evolução de ARNEs. Veja env.pdf, que mostra sequências de ARNEs: (a) uma sequência de remoções dos elementos máximos, (b) uma sequência de remoções dos elementos mínimos, (c) uma sequência de remoções aleatórias e (d) uma sequência de inserçòes e remoções aleatórias. Desempenho e propriedades de ARNEs.
- (Aula 20) 23/5/2013 Tabelas de espalhamento/dispersão (hashing). Discussão geral sobre hashing. Funções de hashing. Breve discussão sobre resolução de colisões por encadeamento. Veja este diretório.
- 28/5/2013 Semana de break
- 30/5/2013 Corpus Christi. Recesso escolar
Junho
- (Aula 21) 4/6/2013 Implementação de tabelas de símbolos com tabelas de espalhamento, com resolução de colisões por encadeamento. Veja este diretório. Breve discussão sobre tabelas dinâmicas.
- (Aula 22) 6/6/2013 Implementação de tabelas de símbolos com tabelas de espalhamento, com resolução de colisões com probing linear/sequencial. Veja este diretório.
- (Aula 23) 11/6/2013 Vetor de sufixos. O problema dos fatores repetidos de comprimento máximo. Veja este diretório.
- (Aula 24) 13/6/2013 Provas de edições anteriores de mac323: provas de 2012 e provas de provas de 2008 (veja este diretório para alguns programas auxiliares sobre ARNE (em particular, veja yk_print.c e yk_print_range.c)).
- (Aula 25) 18/6/2013 Prova 2 [PDF]
- (Aula 26) 20/6/2013 (aula opcional, sem lista de presença) Discussão do EP5. Vetor de sufixos (continuação). Veja este diretório.
- (Aula 27) 25/6/2013 Prova Sub (fechada) [PDF]
- 27/6/2013 Não haverá aula

Calendário


        February 2013              March 2013               April 2013     
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                     1  2                     1  2         1  2  3  4  5  6 
      3  4  5  6  7  8  9      3  4  5  6  7  8  9      7  8  9 10 11 12 13 
     10 11 12 13 14 15 16     10 11 12 13 14 15 16     14 15 16 17 18 19 20 
     17 18 19 20 21 22 23     17 18 19 20 21 22 23     21 22 23 24 25 26 27 
     24 25 26 27 28           24 25 26 27 28 29 30     28 29 30 
                              31

           May 2013                June 2013                July 2013      
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
               1  2  3  4                        1         1  2  3  4  5  6 
      5  6  7  8  9 10 11      2  3  4  5  6  7  8      7  8  9 10 11 12 13 
     12 13 14 15 16 17 18      9 10 11 12 13 14 15     14 15 16 17 18 19 20 
     19 20 21 22 23 24 25     16 17 18 19 20 21 22     21 22 23 24 25 26 27 
     26 27 28 29 30 31        23 24 25 26 27 28 29     28 29 30 31 
                              30

Página principal de MAC323, 1o. semestre de 2013

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Thu Jun 27 20:40:01 BRT 2013