Você está em: Ensino > Material > Estrutura de Dados II
Semestre 2016.3
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.
Ordenação: InsertionSort, MergeSort, Quicksort e Heapsort.
Filas de prioridade: Intercalação de arquivos: algoritmo básico, União de filas de prioridades. Heaps esquerdistas e heaps binomiais.
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.
Estruturas multidimensionais. Estruturas de dados aplicadas em banco de dados espaciais. Árvore Point-Quad e Polygon-Quad. Árvore R.
Estrutura de dados para web: Tries. Trie R-Way. Trie Ternária. Árvore PATRICIA. Arquivos Invertidos.
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.
A avaliação da disciplina se dará através das notas das provas presenciais e entregas de trabalhos, da seguinte forma:
Três provas presenciais: 80 pontos no total.
Trabalhos prático: 20 pontos no total.
[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
Prova 1 (25 pontos): 21/09/2016
Prova 2 (30 pontos): 16/11/2016
Prova 3 (25 pontos): 14/12/2016
Segunda chamada: 19/12/2016. Matéria toda e somente para quem não fez alguma prova. Serve como substitutiva para quem fez as três provas e o trabalho prático.
Trabalho (20 pontos): 27/10/2016
Enunciado do trabalho (nova versão: 10/10/2016) + base de avaliação
Se o trabalho for entregue até dia 21/10/2016, o aluno poderá ganhar 10 extras.
Atenção: as listas de exercício 1, 2 e 3 foram montadas exclusivamente com questões de provas anteriores!
Lista 0 + Gabarito (lista com exercícios de ponteiros para quem possui dúvidas de Estrutura de Dados)
Lista 2 + Lista extra
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.
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
Monitor: Emanual Parreiras
Não haverá atendimento do monitor, somente as aulas abaixo.
Aula práticas com o monitor nas sextas de 10h às 12h no LABDCC03, nos dias abaixo:
26/08: Relembrando como manipular ponteiros
02/09: Criando estruturas encadeadas elementares (listas)
09/09: Criando funções de hash
16/09: Tratando colisões em tabelas hash
30/09: Criando heaps esquerdistas
07/09: Criando heaps binomiais
14/09: Rotacionando na árvore AVL
28/10: Equilibrando árvores vermelho-preta
04/11: Criando árvores B
11/11: Entendendo árvores R
25/11: Criando tries multiway
02/12: Criando tries ternárias
09/12: Manipulando árvores PATRICIA
16/12: Criando huffman estático com lista encadeada
Segunda-feira de 19h às 21h
Complexidades (resumão): http://bigocheatsheet.com/
Algoritmos de ordenação (resumão): Sound of Sorting
Nota de aula: Introdução
Nota de aula: InsertionSort
Nota de aula: MergeSort
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]
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.
Implementar o QuickSort com a escolha randomizada de pivô
Nota de aula: HeapSort
Dançando algoritmos de ordenação.
Demonstração de algoritmos de ordenação.
Vídeo-aula sobre heapsort.
Ler as seções 6.1, 6.2 e 6.3 do livro [1]
Nota de aula: Introdução às técnicas de hashing
Assistir a vídeo-aula sobre funções de hashing
Nota de aula: Funções de hashing
Implementar 2 funções de hashing e testar o número de colisões em uma tabela de tamanho 100.
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.
Ler as seções 11.1 e 11.2 do livro [1]
Assistir a vídeo-aula sobre encadeamento exterior
Nota de aula: hashing para arquivos extensíveis
Material sobre hashing extensível
Nota de aula: Heaps esquerdistas (correção: na linha 11 do slide 467, o correto é "então esq[x1] <-> dir[x1]")