Nome da Atividade
ALGORITMOS E ESTRUTURA DE DADOS
CÓDIGO
1118013
Carga Horária
68 horas
Tipo de Atividade
DISCIPLINA
Periodicidade
Semestral
Unidade responsável
CRÉDITOS
4
CARGA HORÁRIA TEÓRICA
4
CARGA HORÁRIA OBRIGATÓRIA
4
FREQUÊNCIA APROVAÇÃO
75%
Ementa
Estruturas de dados lineares e não-Lineares. Hash estático e dinâmico. Representação, pesquisa, ordenação topológica e problemas de caminhamento e fluxo em grafos. Compressão e classificação de dados.
Objectives
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.Conteúdo Programático
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
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
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