UFJF - Universidade Federal de Juiz de Fora

Algoritmos e estrutura de dados

Você está em: Ensino > Material > Algoritmos e estrutura de dados

Ementa

  1. Introdução: Métodos de prova matemática. 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.
  2. Estruturas básicas: listas, pilhas, filas. skip lists.
  3. Filas de prioridade. 
  4. Estruturas de dicionário: Acesso Direto. Transformação de chave: funções hash. Colisões e Transbordamento. Árvores binárias. Estruturas balanceadas.
  5. Estrutura de dados para web: Tries. Trie R-Way. Trie Ternária. Árvore PATRICIA. Suffix trees. Suffix arrays. Grafos. Representação e percursos em grafos.

 

Avaliação

TVC1 (25 pontos): 08/04/19

TVC2 (40 pontos): 06/05/19

TVC3 (35 pontos): 30/05/19 

 

Bibliografia básica

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

[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] KOFFMAN & WOLFGANG. Objetos, abstração, estruturas de dados e projeto usando [C++ ou Java]. Editora LTC.

 

Listas de exercícios

 

Material de ajuda

O comportamento da maioria das estruturas pode ser visualizado neste site: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

 

Material de estudo

Aula 1

Métodos de prova matemática

Freitas, R., Viana, P. Minicurso de Métodos de Prova. II Colóquio de Matemática da Região Sul. 2012.

Leitura complementar: Capítulos 5, 7 e 8 da referência acima

Aula 2

Introdução e Complexidade assintótica. Pior e melhor caso.

Leitura complementar (Curiosidade): http://bigocheatsheet.com/ 

Aula 3

Complexidade assintótica. Cálculo do caso médio. Ordenações.

Leitura complementar: Demonstração de algoritmos de ordenação e Aula do Prof Siang

Aula 4

Listas contíguas e encadeadas

Aula 5

Pilhas e filas

Aula 6

Skiplists

Leitura complementar: Pugh, W. (1990). “Skip lists: A probabilistic alternative to balanced trees“. Communications of the ACM 33 (6): 668. doi:10.1145/78973.78977.

Aulas 7, 8 e 9

Hashing

Leitura complementar: Introdução às técnicas de hashingFunções de hashing e Tratamento de colisões.

Aula 10, 11 e 12

Árvores. Árvores binárias de busca.

Leitura complementar: Entender a análise do caso médio nesta aula do Prof Siang.

Aula 13

Árvore AVL

Leitura complementar: Nota de aula

Aula 14

Árvore Vermelho-Preto (retirado desse período)

Leitura complementar: Pfaff, Ben (June 2004). “Performance Analysis of BSTs in System Software“. Stanford University.

Aula 15

Heaps binários

Aula 16

Heaps binomiais

Aula 17 e 18

Busca digital

Leitura complementar: Busca digital utilizando tries

Aula 19 e 20

Algoritmos em grafos