MAC323 - Estruturas de Dados
1o. Semestre de 2012
Sinopse das aulas
[Fevereiro |
Março |
Abril |
Maio |
Junho |
Julho]
- Fevereiro
- (Aula 0) 28/2/2012 Discussão inicial sobre a
disciplina. Veja informações gerais
sobre esta edição de MAC323. Divulgação do EP1. Exercício preliminar sobre
o EP1 (esboço do algoritmo/estruturas de dados para o EP1).
- Março
- (Aula 1) 1/3/2012 A organização
interface/implementação/cliente. Exemplos: média e desvio
padrão de uma seqüência de números [prog3.2.c | prog3.2a.c | Num.h | Num.c]; distância entre pares de
pontos aleatórios no quadrado unitário [prog3.8.c | Point.h | Point.c] (RS 3.0, 3.1, e 3.2; isto
é Seções 3.0 a 3.2 do livro de Sedgewick). Diretório dos
programas: exx; o Makefile que uso.
- (Aula 2) 6/3/2012 Listas ligadas (recaptulação). Exemplo:
ordenação por inserção de uma lista ligada: prog3.11.c; ordenação por
intercalação (mergesort): prog8.6.c. Uma biblioteca de listas
ligadas: list.h, list.c. Um cliente; o problema de
Josephus: prog3.13.c (RS 3.4,
3.5, 8.7).
- (Aula 3) 8/3/2012 Pares de pontos próximos (bis): prog3.20_alt.c. Um
exercício: suponha agora que queremos saber
quantos componentes conexos temos em uma
configuração de pontos no plano, com `limiar de distância'
d; como podemos fazer? Para responder a perguntas mais
`estruturais', podemos usar a noção de grafos. Representação
de grafos com matrizes de adjacência: prog3.18.c. Representação
de grafos com listas de adjacência: prog3.19.c (RS 3.7). Veja o Desafio 1.
- (Aula 4) 13/3/2012 Tipos e tipos abstratos de dados (ADTs).
Pilhas e filas. Interfaces e implementações: STACK.h, prog4.4.c (pilha com vetores), prog4.5.c (pilha com listas ligadas); QUEUE.h, prog4.10.c (pilha com listas ligadas),
prog4.11.c (pilha com vetores). Veja
RS 4.0 a 4.6. Continuação da discussão sobre grafos: buscas em
grafos, usando pilhas e filas: busca em profundidade e busca em
largura. Para esta parte, veja CLRS 22.2 e 22.3 (partes iniciais)
[CLRS: Cormen, Leiserson, Rivest and Stein]. Exercício
(para pensar): dados dois vértices, como encontrar a `distância
entre eles no grafo'?
- (Aula 5) 15/3/2012 O problema da cobertura, o algoritmo X,
e dancing links. Estudamos parte do artigo de Knuth. Programas
de Knuth:
DANCE, QUEENS e SUDOKU (fontes na página
de programas de Knuth).
- (Aula 6) 20/3/2012 O problema da cobertura, o algoritmo X,
e dancing links (continuação). Os ponteiros dançantes no
DLX, o algoritmo X com ponteiros dançantes (para uma implementação
em CWEB,
veja o programa DANCE, de
Knuth).
- (Aula 7) 22/3/2012 Divulgação e discussão do enunciado do EP2 Satisfaça-me. O problema
k-SAT e codificações como problemas de cobertura
generalizados. Tabelas de símbolos. Interface (ST.h). Implementações elementares: vetor
indexado pelas chaves (prog12.3.c),
vetor ordenado (prog12.4.c [busca
seqüencial]), lista ligada não-ordenada (prog12.5.c). Implementações com vetores
não-ordenados ou listas ordenadas: ficam como exercícios
(rotineiros). Busca binária (prog12.6.c) [veja RS 12.0 a 12.4].
- (Aula 8) 27/3/2012 Skip lists: definições e
propriedades básicas. O algoritmo de busca em skip lists. Veja a
implementação de tabelas de símbolos com skip lists em ST_skip_lists (veja, em particular,
prog13.7-10.c).
[Veja também RS 13.5].
- (Aula 9) 29/3/2012 Skip Lists: continuação.
- Abril
- 3/4/2012 Semana Santa: Recesso escolar
- 5/4/2012 Semana Santa: Recesso escolar
- (Aula 10) 10/4/2012 Á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: prog12.7.c. Ordenação
com uma ABB: prog12.8.c. Inserção em
uma ABB sem recursão: prog12.9.c
(veja RS 12.5 e 12.6).
- (Aula 11) 12/4/2012 Rotações de ABBs: prog12.11.c. Inserção de um elemento
na raiz de uma ABB: prog12.12.c.
Seleção em ABBs: prog12.13.c.
- 17/4/2012 Não houve aula (professor no LATIN 2012, Latin American
Symposium on Theoretical Informatics).
- (Aula 12) 19/4/2012 Exercícios sobre o problema (generalizado)
da cobertura (aula de Paulo Victor T. Eufrásio)
- (Aula 13) 24/4/2012 Aula de exercícios (preparação para a P1)
- (Aula 14) 26/4/2012 Prova 1
- Maio
- 1/5/2012 Dia do Trabalho: Recesso escolar
- (Aula 15) 3/5/2012 Partição de uma ABB: prog12.14.c. Remoção de uma ABB: prog12.15.c. União de duas ABBs: prog12.16.c (veja RS 12.8).
Evolução de uma ABB. Vejam o resultado da evolução de uma
ABB de 650 nós, após 80 milhões de remoções e inserções
aleatórias (40 milhões de cada, alternadas): exemplo 1, exemplo 2; observa-se uma degradação
da aleatoriedade da árvore. ABBs balanceadas.
Balanceamento explícito de uma ABB: prog13.1.c (veja RS 13.0).
- 8/5/2012 Semana de break (postergada para esta semana;
professor no Brazil--Cornell
Workshop on Computer Science, Cornell)
- 10/5/2012 Semana de break (postergada para esta semana;
professor no Brazil--Cornell
Workshop on Computer Science, Cornell)
- (Aula 16) 15/5/2012 Árvores binárias de busca
aleatorizadas (ABBAs). Inserção em uma ABBA: prog13.2.c. Remoção de uma ABBA: prog13.4.c. Note que o campo
N precisa ser atualizado nessas rotinas (exercício!).
A primeira das duas árvores em 650.rABB.pdf foi gerada a partir de uma
árvore vazia, com a inserção de 650 itens, em ordem crescente,
usando o algoritmo de inserção aleatória acima. A segunda árvore em
650.rABB.pdf foi obtida executando-se
uma seqüência alternada de remoções e inserções (itens gerados
aleatoriamente), usando-se os algoritmos de inserção e remoção
acima; foram feitas 10 milhões de inserções e remoções (20 milhões
de operações no total). Fato crucial: as ABBAs obedecem a
distribuição de ABBs típicas, isto é, de B_N, como
descrito neste texto
(Notes.pdf). (Veja RS 13.1.)
- (Aula 17) 17/5/2012 Veja o artigo que introduz ABBAs. Um
excelente exercício (parcialmente discutido em sala) é
verificar/reproduzir as Figuras 1 e 2 deste artigo. Árvores
2-3. Veja a Seção 3.3 de
Sedgewick e
Wayne.
- (Aula 18) 22/5/2012 Árvores rubro-negras esquerdistas (ARNEs).
Algoritmos de busca e inserção.
- (Aula 19) 24/5/2012 ARNEs: Algoritmos de inserção (cont.) e remoção
do máximo.
- (Aula 20) 29/5/2012 ARNEs: Algoritmos de remoção do máximo (cont.),
remoção do mínimo. Remoção geral. Veja o código de Sedgewick (Java):
RedBlackBST.java. Tradução
minimal para C: llrb.c. O programa yk_draws-d.c pode ser usado para
gerar seqüências de ARNEs como estas: env.pdf (veja este exemplo de execução; o diretório é este).
- (Aula 21) 31/5/2012 ARNEs: continuação. Um resumo estendido de
Sedgewick: Left-leaning red-black
trees.
- Junho
- 5/6/2012 Semana de break
- 7/6/2012 Corpus Christi (recesso escolar)
- (Aula 22) 12/6/2012 Busca em memória secundária. Veja
Capítulo 16 de RS. B-árvores: descrição e exemplo. Um
artigo interessante, enfatizando o impacto no desempenho de
algoritmos do esquema de memória virtual (e a conseqüência de nem
todos os dados que um programa manipula estarem necessariamente
presentes em memória principal) foi publicado recentemente no ACM
Queue: You're
Doing It Wrong. Este artigo ignora desenvolvimentos teóricos
dos últimos 15 anos (veja, por exemplo, cache-oblivious
algorithms na Wikipedia e as referências citadas nesse artigo),
mas é um artigo interessante mesmo assim.
- (Aula 23) 14/6/2012 B-árvores. Os algoritmos básicos
de manipulação de B-árvores podem ser encontrados em ST.c. Dois clientes que podem ser
usados para experimentar com as rotinas em ST.c são driver.c e driver_random.c. Veja
este diretório; em particular, veja
este exemplo. O
Capítulo 6 de Algorithms, 4th
Edition contém uma discussão de B-árvores; a implementação de
B-árvores dada nesse livro pode ser encontrada na página de códigos do
livro.
- (Aula 24) 19/6/2012 Aula de preparação para a Prova 2
- (Aula 25) 21/6/2012 Prova 2
- (Aula 26) 26/6/2012 Um desafio. Desenvolva um
algoritmo eficiente para encontrar um fator comum mais longo de duas
seqüências dadas. Buscas digitais. Tries binárias. Tries
R-árias.
- (Aula 27) 28/6/2012 ABTs: árvores de busca ternárias (ternary
search trees, TSTs). Veja a página sobre TSTs dos autores da idéia:
Ternary Search
Trees, de Bentley e Sedgewick. Essa página contém um artigo que
descreve TSTs (apresentado no SODA 1997) e códigos detalhados. Para
as aulas 26 e 27, veja o Capítulo 15 de RS; uma referência mais nova
(com código possivelmente melhor) é a Seção 5.2 (Tries)
de Sedgewick e
Wayne.
- Julho
Calendário
February 2012 March 2012 April 2012
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 2 3 1 2 3 4 5 6 7
5 6 7 8 9 10 11 4 5 6 7 8 9 10 8 9 10 11 12 13 14
12 13 14 15 16 17 18 11 12 13 14 15 16 17 15 16 17 18 19 20 21
19 20 21 22 23 24 25 18 19 20 21 22 23 24 22 23 24 25 26 27 28
26 27 28 29 25 26 27 28 29 30 31 29 30
May 2012 June 2012 July 2012
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 5 1 2 1 2 3 4 5 6 7
6 7 8 9 10 11 12 3 4 5 6 7 8 9 8 9 10 11 12 13 14
13 14 15 16 17 18 19 10 11 12 13 14 15 16 15 16 17 18 19 20 21
20 21 22 23 24 25 26 17 18 19 20 21 22 23 22 23 24 25 26 27 28
27 28 29 30 31 24 25 26 27 28 29 30 29 30 31
Página principal de MAC323, 1o. semestre de
2012
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Tue Jul 3 14:45:14 BRT 2012