PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5408 - Estruturas de Dados
Nível:Graduação
Carga Horária:108 horas-aula (Teórica: 54; Prática: 54)
Vigência:De 2020-1 até a presente data

2. 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.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo 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.

4.2 Objetivos Específicos:

  1. Identificar o papel das estruturas de dados no desenvolvimento de software.
  2. Compreender a teoria associada a cada modelo, sendo capaz de compreender e aplicar adequadamente aspectos de complexidade de algoritmos associados.
  3. Capacitar o aluno a criar uma biblioteca de estruturas de dados reutilizáveis.
  4. Identificar as estruturas de dados pertinentes a um problema dado.
  5. 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.

5. Conteúdo Programático

  1. Alocação dinâmica de memória [6 horas-aula]
    1. Variáveis estáticas e dinâmicas
    2. Ponteiros
    3. Passagem de parâmetros por referência, valor e nome
  2. Estruturas lineares [24 horas-aula]
    1. Listas
    2. Pilhas
    3. Filas
  3. Complexidade de algoritmos [6 horas-aula]
    1. Conceitos de Complexidade de Algoritmos
    2. Métodos práticos para Análise da Complexidade de Estruturas e Algoritmos
  4. Árvores [24 horas-aula]
    1. Árvore binária
    2. Árvores binárias semibalancedas (Árvore AVL, Árvore Red-Black)
    3. Árvore semibalanceadas multivias (Árvore B e B+)
    4. Árvores binárias multichaves (Árvore k-d)
    5. Árvores semibalanceadas multivias multichaves (Árvores k-b-d e b-k-d)
  5. Tabela de espalhamento (hash) [15 horas-aula]
    1. Tratamento de colisões
    2. Funções de espalhamento
  6. Métodos de ordenação [12 horas-aula]
    1. Conceitos básicos, implicações e premissas
    2. Métodos de Complexidade Quadrática
      1. Método por inserção
      2. Método por seleção
      3. Método da bolha
    3. Métodos Avançados e de Complexidade n log n
      1. Método Quicksort
      2. Método Heapsort
  7. Estruturas de dados em arquivo [21 horas-aula]
    1. Acesso direto e Acesso sequencial
    2. Organização de Arquvos de Índices
      1. Métodos indexados seqüenciais, ISAM e VSAM
      2. Indexação por Árvore
      3. Indexação por Multilistas e Lista Invertida

6. Bibliografia Básica

  1. DROZDEK, A. Estrutura de Dados e Algoritmos em C++. 4. ed. Cengage Learning, 2017. ISBN: 9788522126651. Disponível em: https://www.cengage.com.br/ls/ebook-estrutura-de-dados-e-algoritmos-em-c/ (acesso via http://portal.bu.ufsc.br/)
  2. MORIN, P. Open Data Structures (in C++). Edition 0.1G?. Disponível em: http://opendatastructures.org/
  3. LUCCHESI, C.L., KOWALTOWSKI, T. Estruturas de Dados e Técnicas de Programação. Instituto de Computação, UNICAMP, 2004. Disponível em: https://www.ic.unicamp.br/~mc202abcd/ln_tkcll.pdf
  4. RICARTE, I.L.M. Estruturas de dados. Faculdade de Engenharia Elétrica e de Computação, UNICAMP, 2008. Disponível em: http://calhau.dca.fee.unicamp.br/wiki/images/0/01/EstruturasDados.pdf

7. Bibliografia Complementar

  1. Materiais disponibilizados via Moodle.
  2. PEREIRA, Silvio do Lago. Estruturas de dados fundamentais: conceitos e aplicações. 12. ed., rev. e atual. São Paulo: Érica, 2009. 238 p. ISBN 9788571943704
  3. JOYANES AGUILAR, Luis. Programação em C++: algoritmos, estruturas de dados e objetos. São Paulo: McGraw Hill, 2008. xxxi, 768 p. ISBN 9788586804816
  4. WIRTH, Niklaus; ZÜRICH, Eth. Algoritmos e estruturas de dados. Rio de Janeiro: LTC, 1999. 255 p. ISBN 978-85-216-1190-5
  5. HOROWITZ, Ellis. Fundamentos de estruturas de dados.. Rio de Janeiro: Ed. Campus, 1986.
  6. CLAYBROOK, Billy G. (Billy Gene). Tecnicas de gerenciamento de arquivos. 2. ed. Rio de Janeiro: Campus, 1987. 248p. ISBN 8570012608
  7. SILBERSCHATZ, KORTH E SUDARSHAN. Database System Concepts. 4ª ed., McGraw-Hill, 2001.
  8. THARP, A. File Organization and Processing. John Wiley, 1988.
  9. SEDGEWICK, R. Algorithms in C++. Addison Wesley, 1996.
  10. GOODRICH, M.T., TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 4a. Edição. Ed. Bookman, 2007.
  11. AMERAAL, L. Algorithms and Data Structures in C++. Editora John Wiley, 1996.
  12. TENNENBAUM, A., LANGSAM, Y. Data Structures using C and C++. 2ª Ed. Prentice-Hall, 1995.