UFJF - Universidade Federal de Juiz de Fora

Plano de ensino

Disciplina: DCC012 - ESTRUTURA DE DADOS II

Créditos: 4

Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE

Ementa Introdução;
Ordenação;
Filas de prioridade;
Estruturas de Dicionário: Acesso Direto; Estruturas balanceadas e Estruturas auto-organizáveis;
Estruturas multidimensionais e espaciais;
Estruturas de dados para a web;
Processamento de Cadeias de Caracteres
Conteúdo 1. Introdução: Análise de complexidade assintótica, análise e adaptação de estrutura de dados, apresentação da problemática que será discutida na disciplina.
2. Ordenação: MergeSort, Quicksort e Heapsort.
3. Filas de prioridade: Intercalação de arquivos: algoritmo básico, busca direta, árvore binária de vencedores e perdedores. União de filas de prioridades. Heaps esquerdistas e heaps binomiais.
4. Estruturas de Dicionário - Acesso Direto: Transformação de chave: funções "hash". Colisões e Transbordamento. Hashing para Arquivos Extensíveis.
5. Estruturas de dicionário - estruturas balanceadas e auto ajustáveis: Arquivos Sequenciais Indexados. Árvores Balanceadas: Árvore AVL, Árvore Vermelho-Preto, Árvores B, Árvores B+. Árvores de splay: Árvore de espalhamento.
6. Estruturas multidimensionais e espaciais: Estruturas de dados aplicadas em banco de dados espaciais. Árvore Point-Quad. Árvore R.
7. Estruturas de dados para web: Tries. Trie R-Way. Trie Ternária. Árvore PATRICIA. Arquivos Invertidos.
8. Processamento de cadeias de caracteres: Casamento Exato de Cadeias: algoritmo KMP, BMH, BMHS e Robin-Karp. Compressão: Compressão de Textos em Linguagem Natural, Codificação RLE, Codificação de Huffman Usando Bytes, Huffman Adaptativo, Codificação de Lempel-Ziv. Criptografia.

Bibliografia DROZDEK. Adam. Estrutura de Dados e Algoritmos em C++. Cengage Learning.2002.
LEISERSON, C. E.; STEIN, C.; RIVEST, R. L., CORMEN, T.H. Algoritmos:Teoria e Prática. Tradução da 2a. edição americana. Editora Campus, 2002.
PREISS, Bruno. Estrutura de Dados e Algoritmos. Elsevier. 2001.
Bibliografia (continuação)
Bibliografia complementar DINESH P. Mehta e SARTAJ Sahni. Handbook of Data Structures and Application. Chapman & Hall/CRC. 2005.
GUIMARÃES, A. P. Algoritmos e estruturas de dados. LTC, 1994.
SZWARCFITER, J. L. Estrutura de Dados e Seus Algoritmos. Segunda Edição. LTC, 1994.
VELOSO, P.; SANTOS, C.; AZEREDO, P.; FURTADO, A. Estruturas de Dados. Campus, Rio de Janeiro, 1983.
ZIVIANI, NIVIO. Projeto de Algoritmos com Implementação em Java e C++. Cengage Learning. 2007.
Voltar