Disciplina: DCC012 - ESTRUTURA DE DADOS II
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
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)
Não informado
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.
