UFJF - Universidade Federal de Juiz de Fora

Estrutura de Dados II

Você está em: Ensino > Material > Estrutura de Dados II

Semestre 2016.3

Ementa

  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: InsertionSort, MergeSort, Quicksort e Heapsort.
  3. Filas de prioridade: Intercalação de arquivos: algoritmo básico, 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. Estruturas balanceadas e auto-ajustáveis. Árvore AVL,  Vermelho-Preto, B, B+ e de espalhamento.
  5. Estruturas multidimensionais. Estruturas de dados aplicadas em banco de dados espaciais. Árvore Point-Quad e Polygon-Quad. Árvore R.
  6. Estrutura de dados para web: Tries. Trie R-Way. Trie Ternária. Árvore PATRICIA. Arquivos Invertidos.
  7. 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.

 

Avaliação

A avaliação da disciplina se dará através das notas das provas presenciais e entregas de trabalhos, da seguinte forma:

 

Bibliografia

[1] LEISERSON, C. E.; STEIN, C.; RIVEST, R. L., CORMEN, T.H. Algoritmos: Teoria e Prática. Editora Campus, 2002. Segunda Edição. Número da obra: 111190 / Classificação: 681.3.06

[2] SZWARCFITER, Jaime Luíz. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: Ed. LTC, 1994. Número da obra: 67579 / Classificação: 681.3.06:800.92:518

[3] PREISS, Bruno R. Estruturas de dados e algoritmos. Elsevier, 2001. 566p. Número da obra: 116818 / Classificação: 681.31

[4] DROZDEK, A. Estrutura de Dados e algoritmos em C++. Cengage Learning, 2003. Número da obra: 154546 / Classificação: 004.021

 

Datas importantes

 

Lista de exercícios

Atenção: as listas de exercício 1, 2 e 3 foram montadas exclusivamente com questões de provas anteriores!

 

Observações

Em virtude do calendário desse semestre e com os feriados, os seguintes tópicos não serão ministrados em sala de aula: Hashing linear, Huffman dinâmico e Rabin-Karp.

 

Implementação

GETComp desenvolve uma ferramenta gráfica para auxiliar os alunos de Estrutura de Dados e Estrutura de Dados II. Baixe a DSGraph em http://dsgraph.sourceforge.net e treine a implementação de estruturas como árvores AVL, Vermelho-Preto, Splay, QuadTree, B, B+, Tries e algoritmos de ordenação com vetores ou listas. A prática lhe ajudará nas avaliações!

 Ainda, é possível visualizar o funcionamento de boa parte das estruturas neste site: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

 

Monitoria e Tutoria 

 

Horário de atendimento 

Segunda-feira de 19h às 21h

 

Complexidades (resumão): http://bigocheatsheet.com/

Algoritmos de ordenação (resumão): Sound of Sorting 

 

Material de estudo

Aula 1

Introdução

Ordenação

Nota de aula: Introdução

Nota de aula: InsertionSort

Nota de aula: MergeSort

Tarefa:

  • Ler a seção 1.2 e o capítulo 2 do livro [1]
  • Fazer os exercícios 1.2-2, 2.3-1 e 2.3-5 do livro [1]

Aula 2

Ordenação

Nota de aula: QuickSort

Nota de aula: BubbleSort

Software ProfesSort para auxílio ao aprendizado de algoritmos de ordenação.

Analisando complexidade entre QuickSort e BubbleSort.

Tarefa:

  • Implementar o QuickSort com a escolha randomizada de pivô

Aula 3

Ordenação

 

Nota de aula: HeapSort

Dançando algoritmos de ordenação.

Demonstração de algoritmos de ordenação.

Vídeo-aula sobre heapsort.

Tarefa:

  • Ler as seções 6.1, 6.2 e 6.3 do livro [1]

Aula 4

Hashing

Nota de aula: Introdução às técnicas de hashing

Tarefa:

Aula 5

Hashing

Nota de aula: Funções de hashing

Tarefa:

  • Implementar 2 funções de hashing e testar o número de colisões em uma tabela de tamanho 100.

Aula 6

Hashing

Nota de aula: Tratamento de colisões

University of Auckland, Department of Computer Science. – Mostra o hash de palavras com tratamento de colisões por endereçamento aberto passo a passo.

York University, Algorithmics Animation Workshop – Faz o hash com tratamento de colisão por lista com chave inteira. Permite inserção, retirada e busca.

Animação livro do Richard Lafore – Hash com endereçamento aberto. Permite inserir, procurar e retirar, mostrando passo a passo.

Animação livro do Richard Lafore – Hash com listas encadeadas. Permite inserir, procurar e retirar, mostrando passo a passo.

Tarefa:

Aula 7 e 8

Hashing

Nota de aula: hashing para arquivos extensíveis

Material sobre hashing extensível

Aula 9

Filas de prioridade

Nota de aula: Heaps esquerdistas (correção: na linha 11 do slide 467, o correto é “então esq[x1] <-> dir[x1]”)

Manipulação de arquivos em linguagem C

Tarefa:

  • Ler a seção 11.3 do livro [3].

Aula 10

Filas de prioridade

Nota de aula: Heaps binomiais

Tarefa:

  • Ler a seção 19.2 do livro [1].

Aula 11

Estruturas balanceadas

Nota de aula: Árvore AVL

Implementação da árvore AVL

Tarefa:

  • Ler seção 10.5 (páginas 273 a 284) do livro [3]
  • Assistir vídeo-aulas: VA1 e VA2.

Aula 12

Estruturas balanceadas

Nota de aula: Árvore Vermelho-Preto

Implementação e applet com animação da árvore VP

Tarefa:

Aula 13

Estruturas auto-ajustáveis

Nota de aula: Árvore Splay 

Splay trees no MS Windows

Tarefa:

  • Testar árvore AVL, VP e Splay nesse applet

Aula 14

Estruturas balanceadas

Nota de aula: Árvore B 

Vídeo-aula sobre Árvore B

Tarefa:

Aula 15

Estruturas multidimensionais

Nota de aula: QuadTree

Tarefa:

Aula 16

Estruturas multidimensionais

Nota de aula: Árvore_R

Tarefa:

Aula 17 e 18

Estruturas de dados para a web

Nota de aula: Busca digital utilizando tries

Tarefa:

Aula 19, 20 e 21

Casamento de Padrões

Nota de aula: Algoritmos KMP, BMs, Robin-Karp

Tarefa:

  • Ler seções 32.1, 32.2 e 32.4 do livro [1]

Aula 22 e 23

Compressão

Nota de aula: Algoritmos LZs e Huffman

Tarefa:

  • Ler seções 11.2, 11.4 e 11.5 do livro [4]
  • Ver os videos sobre Huffman: video1 e video2.

Aula extra: curiosidade

Indexação invertida

Nota de aula: Índices invertidos

Como o Google funciona? TextoVídeo

Tarefa