ELC1068 Pesquisa e Ordenação de Dados "A"
Universidade Federal de Santa Maria

Departamento: Linguagens e Sistemas de Computação
Carga Horária: 60 horas/semestre
Créditos: 3 créditos
Horário: Tercas-feiras e Quintas-feiras 14h30-16h10. Sala 364 - CT.

Programa da disciplina

Cronograma de aulas (2013/2)

Aula 01: (10/09) Apresentação do programa da disciplina. Bibliografia. Página da disciplina. Especificação do método de avaliação.
Introdução à ordenação de dados. Formas de apresentação do resultado: contigüidade física, vetor indireto de ordenação (VIO), encadeamento.
Bibliografia: Cap. 10 do livro do Veloso (1988).

Aula 02: (12/09) Introduction to data compression (long)
Data compression (book) Codificação de texto em linguagem natural: Huffman usando caracteres e Huffman usando palavras.
Bibliografia: 8.2 Compressão. cap. 8 do livro do Ziviani (2011). pp. 365- 380.

Aula 03: (17/09) Compressão de dados (Família LZ*: LZ77, LZ78, LZW)
O material com o conteúdo da aula pode ser encontrado aqui: Data Compression Technology.
Leitura recomendada: Data Compression. Debra A. Lelewer, Daniel S. Hirschberg. ACM Computing, 1987.

Aula 04: (19/09) Compressão de bits: RLE. Huffman Adaptativo
Bibliografia: 5.4.2 Bitmap compactados. H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 5. Ed. Campus, 2001. pp. 243-246.

Aula 05: (24/09) Famílias de métodos de ordenação de dados: análise do desempenho.
Ordenação interna: bolha, ordenação por seleção, ordenação por inserção, shellsort.
Bibliografia: cap. 4 do livro do Ziviani (2011). pp. 101-109.

Aula 06: (26/09) Ordenação interna: heapsort. Método da partição e troca (quicksort). Comparação entre os métodos de ordenação interna.
Bibliografia: cap. 4 do livro do Ziviani (2011). pp.109-124.

Aula 07: (01/10) Lista de exercicios: cap 10. Veloso 1988. Aula nao presencial.

Aula 08: (03/10) Lista de exercicios: cap. 4 do livro do Ziviani (2011). Aula nao presencial.

Aula 09: (08/10) Ordenação interna: countingsort, radixsort, mergesort.
Bibliografia: cap. 4 do livro do Ziviani (2011).

Aula 10: (10/10) Ordenação parcial. Bibliografia: cap. 4 do livro do Ziviani (2011).

Aula 11: (15/10) JAI - Jornada de Integração

Aula 12: (17/10) JAI - Jornada de Integração

Aula 13: (22/10) Ordenação em memória secundária (external sorting).
Intercalação balanceada de vários caminhos. Intercalação polifásica.
Bibliografia: cap. 4 do livro do Ziviani (2011).

Aula 14: (24/10) Pesquisa seqüencial e pesquisa binária.
Árvores binárias de pesquisa com balanceamento (SBB).
Bibliografia: cap. 5 do livro do Ziviani (2011).

Aula 15: (29/10) Pesquisa digital: TRIE e PATRICIA.
Patricia - Practical Algorithm to Retrieve Information Coded in Alphanumeric
trie

Aula 16: (31/10) Transformação de chave (hashing para memória primária).
Bibliografia: cap. 5 do livro do Ziviani (2011).

Aula 17: (05/11) Modelo de computação para a memória secundária.
Arquivo sequencial indexado: implementaçã para disco óptico e disco magnético

Aula 18: (07/11) Árvores de Pesquisa: Árvores-B. Applet com a árvore-B.
Árvores de Pesquisa: Árvores-B*.
Bibliografia: cap. 6 do livro do Ziviani (2011).

Aula 19: (12/11) Índices sobre arquivos seqüenciais (denso e esparso). Índices secundários.
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 4. Ed. Campus, 2001.

Aula 20: (14/11) Árvore B+ para memória secundária. Tabelas hash para a memória secundária (hash extensível e hash linear).
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 4. Ed. Campus, 2001.
Exercicios.

Aula 21: (19/11) SAINFO 2013.

Aula 22: (21/11) Entrega do trabalho 1 de Pesquisa e Ordenação de Dados (especificação)
Primeira Avaliação Parcial.
Conteúdo: capítulos 4, 5 do livro do Ziviani (2011) + capítulo 10 Veloso (apresentação de resultados pós-ordenacao) + compressao de dados.
Importante: não chegue atrasado (a) no dia da prova. Estude para a prova antecipadamente através de livros, usando preferencialmente a bibliografia indicada pela professora.
Slides são material de apoio do professor e não devem ser usados como ferramenta de estudo para uma avaliação.

Aula 23: (26/11) Apresentação do trabalho 1.

Aula 24: (28/11) Índices multidimensionais. Consultas multidimensionais. Arquivos de grade.
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 5. Ed. Campus, 2001. pp. 201-219.

Aula 25: (03/12) Índices multidimensionais. Funções de hash particionado (hash para a memória secundária).
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 5. Ed. Campus, 2001. pp. 219-224.
J. Nievergelt, H. Hinterberger, K.C. Sevcik. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71 (1984)

Aula 26: (05/12) Estruturas semelhantes a árvores para dados multidimensionais: índice de várias chaves, árvore kd, árvore quadrante.
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 5. Ed. Campus, 2001. pp.225-234.
R-Tree: A Dynamic Index Structure for Spatial Searching

Aula 27: (10/12) Estruturas semelhantes a árvores para dados multidimensionais: árvore R. Mapa de bits (bitmap).
Bibliografia: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Cap. 5. Ed. Campus, 2001. pp.235-253.

Aula 28: (12/12) Revisao final - exercicios

Aula 29: (07/01) Entrega do trabalho 2. Segunda Avaliação Parcial.
Conteúdo: H. Garcia-Molina, J. Widom, J. D. Ullman. Implementação de Sistemas de Bancos de Dados. Caps. 4 e 5. Ed. Campus, 2001. + Cap. 6 Ziviani.

Aula 30: (09/01) Apresentação do trabalho 2 Especificação Entrega do trabalho ate 07/01, em formato PDF, via email.

Exame: (21/01) Avaliação final. Prova escrita realizada durante o horário de aula. Conteúdo: toda a matéria da disciplina.