- Identificação:
- Disciplina: INE5408 – Estruturas de Dados
- Carga horária: 108 horas-aula Teóricas: 54 Práticas: 54
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- INE5404 – Programação Orientada a Objetos II
- Ementa:
- Alocação dinâmica de memória. Variáveis estáticas e dinâmicas. Estruturas lineares. Tabelas de Espalhamento. Árvores. Árvores de Pesquisa. Métodos de ordenação. Métodos de acesso a arquivos. Técnicas de implementações iterativas e recursivas de estruturas de dados. Complexidade dos algoritmos em estruturas de dados.
- Objetivo(s):
- Geral: Capacitar o estudante a compreender, tanto do ponto de vista conceitual e teórico quanto prático (implementação e solução de problemas reais), as estruturas de dados clássicas a partir da perspectiva de diferentes paradigmas de programação.
- Específicos:
- Identificar o papel das estruturas de dados no desenvolvimento de software.
- Compreender a teoria associada a cada modelo, sendo capaz de compreender e aplicar adequadamente aspectos de complexidade de algoritmos associados.
- Capacitar o aluno a criar uma biblioteca de estruturas de dados reutilizáveis.
- Identificar as estruturas de dados pertinentes a um problema dado.
- Transferir seus conhecimentos a problemas práticos do mundo real, sendo capaz de solucionar estes problemas práticos do mundo através da utilização das Estruturas de Dados adequadas, tanto do ponto de vista da eficácia quanto da eficiência.
- Conteúdo Programático:
- Alocação dinâmica de memória [6 horas-aula]
- Variáveis estáticas e dinâmicas
- Ponteiros
- Passagem de parâmetros por referência, valor e nome
- Estruturas lineares [24 horas-aula]
- Complexidade de algoritmos [6 horas-aula]
- Conceitos de Complexidade de Algoritmos
- Métodos práticos para Análise da Complexidade de Estruturas e Algoritmos
- Árvores [24 horas-aula]
- Árvore binária
- Árvores binárias semibalancedas como Árvore AVL e Árvore Red-Black
- Árvore semibalanceadas n-árias como Árvore B e B+
- Árvores multichaves como Árvore k-d
- Tabela de espalhamento (hash) [15 horas-aula]
- Tratamento de colisões
- Funções de espalhamento
- Métodos de ordenação [12 horas-aula]
- Conceitos básicos, implicações e premissas
- Métodos de Complexidade Quadrática
- Método por inserção
- Método por seleção
- Método da bolha
- Métodos Avançados e de Complexidade n log n
- Método Quicksort
- Método Heapsort
- Estruturas de dados em arquivo [21 horas-aula]
- Acesso direto e Acesso sequencial
- Organização de Arquvos por Índices
- Métodos indexados sequenciais, ISAM e VSAM
- Indexação por Árvore
- Multilistas e Lista Invertida
- Bibliografia Básica:
- GOODRICH, M.T., TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 4a. Edição. Ed. Bookman, 2007.
- PREISS, B. R., Data Structure and Algorithms With Object-Oriented Design Patterns. Editora John Wiley, 1999.
- HOROWITZ, E., SAHNI, J., Fundamentos de Estruturas de Dados Ed. Campus, 1984.
- WIRTH, N. Algorithms + Data Structures = Programs. Prentice-Hall, 1976.
- AMERAAL, L. Algorithms and Data Structures in C++. Editora John Wiley, 1996.
- TENNENBAUM, A., LANGSAM, Y. Data Structures using C and C++. (2nd Ed.) Prentice-Hall, 1995.
- THARP, A. File Organization and Processing. Editora John Wiley, 1988.
- CLAYBROOK, B.G., Técnicas de Gerenciamento de Arquivos. Ed. Campus, 1985.
- Bibliografia Complementar:
- VILLAS, M. V., Estruturas de Dados: conceitos e técnicas de implementação. Ed. Campus, 1993.
- STANDISH, Thomas A. Data Structures, algorithms, and software principles, Addison-Wesley, 1994.
- BOOCH, G., RUMBAUGH, J. & JACOBSON, I., UML – Guia do Usuário Ed. Campus, 2000
- SEDGEWICK, R. Algorithms in C++. Addison Wesley, 1996.
