Portal InstitucionalUFPEL

Objetivo Geral:

Apresentar aos estudantes os principais conceitos básicos de estruturas de dados e seus algoritmos, buscando complementar a formação básica da área de Computação.

1. Estruturas lineares
1.1. Tipos de listas lineares: listas com e sem descritor; listas ordenadas; listas disciplinadas (pilhas, filas, deques) e não disciplinadas; listas duplamente encadeadas e listas circulares.
1.2. Operações básicas.
1.3. Alocação sequencial (array) e alocação encadeada (ponteiros).
1.4. Pesquisa calculada (""hashing""):
1.4.1. tratamento de colisões (endereçamento aberto, encadeamento, Re-hashing);
1.4.2. cálculo de endereço (compressão de chaves alfanuméricas, métodos da divisão/multiplicação/quadrado/dobradura/ conversão de base).

2. Estruturas não-lineares
2.1. Árvores: conceitos, representação simbólica e aplicações.
2.2. Árvores binárias: percurso; representação (alocação sequencial e encadeada).
2.3. Árvores de busca binária.
2.4. Árvores balanceadas e AVL
2.5. Árvores Rubro-negras
2.6. Árvores B

3. Grafos
3.1. Representação, Pesquisa, Ordenação Topológica
3.2. Caminhos mais curtos
3.3. Problemas de Fluxo em Rede

4. Métodos de Classificação de Dados
4.1. Ordenação por inserção (Insertion Sort)
4.2. por Intercalação (Merge Sort)
4.3. por troca (Bubble Sort)
4.4. por seleção (Selection Sort, Heap Sort)
4.5. por troca e partição (Quicksort)
4.6. por distribuição (Ordenação por Caixas, Ordenação por Contagem, Ordenação por Raiz).

5. Compressão de Dados
5.1. Técnicas de compressão com e sem perda
5.2. Codificação de Huffman e Shannon-Fano
5.3. Codificação Comprimento de Carreira (Run-Length)
5.4. Codificação LZW
5.5. Codificação Huffman Adaptativo

Bibliografia Básica:

• Aho, A. V.; Hopcroft, J. E.; Ullman, J. D. Data Structures And Algorithms. Reading: Addison Wesley, 1982.
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. Algoritmos: Teoria E Prática. Rio De Janeiro: Campus, 2002.
• Drozdek, Adam. Estrutura De Dados E Algoritmos Em C++. Tradução: Luiz Sérgio De Castro Paiva. São Paulo: Pioneira Thomson Learning, 2002. 579 P.
• Ziviani, N. Projeto De Algoritmos: Com Implementações Em Java E C++. São Paulo: Thomson, 2007