Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20201

Aprovado pelo Departamento em: 5-8-2020

  1. Identificação: Visualizar em PDF
    • Disciplina: INE5408 - Estruturas de Dados
    • Carga horária: 108 horas-aula      Teóricas: 54      Práticas: 54
    • Período: 1º semestre de 2020 até a presente data
  2. Curso(s):
    • Ciências da Computação (208)
    • Matemática, Habilitação Bacharelado (222)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5404 - Programação Orientada a Objetos II
    • Matemática, Habilitação Bacharelado (222)
      • INE5404 - Programação Orientada a Objetos II
  4. 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.
  5. 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:
      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.
  6. 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]
      • Listas
      • Pilhas
      • Filas
    • 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 (Árvore AVL, Árvore Red-Black)
      • Árvore semibalanceadas multivias (Árvore B e B+)
      • Árvores binárias multichaves (Árvore k-d)
      • Árvores semibalanceadas multivias multichaves (Árvores k-b-d e b-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 de Índices
        • Métodos indexados seqüenciais, ISAM e VSAM
        • Indexação por Árvore
        • Indexação por Multilistas e Lista Invertida
  7. Bibliografia Básica:
    • 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/)
    • MORIN, P. Open Data Structures (in C++). Edition 0.1Gβ. Disponível em: http://opendatastructures.org/
    • 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
    • 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
  8. Bibliografia Complementar:
    • Materiais disponibilizados via Moodle.
    • 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
    • JOYANES AGUILAR, Luis. Programação em C++: algoritmos, estruturas de dados e objetos. São Paulo: McGraw Hill, 2008. xxxi, 768 p. ISBN 9788586804816
    • WIRTH, Niklaus; ZÜRICH, Eth. Algoritmos e estruturas de dados. Rio de Janeiro: LTC, 1999. 255 p. ISBN 978-85-216-1190-5
    • HOROWITZ, Ellis. Fundamentos de estruturas de dados.. Rio de Janeiro: Ed. Campus, 1986.
    • CLAYBROOK, Billy G. (Billy Gene). Tecnicas de gerenciamento de arquivos. 2. ed. Rio de Janeiro: Campus, 1987. 248p. ISBN 8570012608
    • SILBERSCHATZ, KORTH E SUDARSHAN. Database System Concepts. 4ª ed., McGraw-Hill, 2001.
    • THARP, A. File Organization and Processing. John Wiley, 1988.
    • SEDGEWICK, R. Algorithms in C++. Addison Wesley, 1996.
    • GOODRICH, M.T., TAMASSIA, R. Estruturas de Dados e Algoritmos em Java. 4a. Edição. Ed. Bookman, 2007.
    • AMERAAL, L. Algorithms and Data Structures in C++. Editora John Wiley, 1996.
    • TENNENBAUM, A., LANGSAM, Y. Data Structures using C and C++. 2ª Ed. Prentice-Hall, 1995.