Estruturas de Dados II

1. Componente Curricular:

Estrutura de Dados II

2. Carga Horária:

60 horas

3. Objetivo:

Tendo como base a execução de atividades práticas e o desenvolvimento de produtos, apresentar ao estudante os principais conceitos relacionados as principais formas de uso avançado das Estrutura de Dados computacionais.

4. Ementa Oficial:

• • Heaps. Filas de prioridades. Tabelas de espalhamento. Árvores: árvores de busca binária, árvores AVL, árvores vermelho-preto, árvores B. Grafos: representação de grafos, busca em largura, busca em profundidade, ordenação topologia e componentes fortemente conexos.

5. Conteúdo Programático:

1. Revisão de Algoritmos e Estrutura de Dados.

2. Introdução à Teoria dos Grafos.

3. Árvores Binárias.

4. Árvores Múltiplas.

5. Ordenação.

6. Abordagem Metodológica:

Aprender fazendo e fazer aprendendo. As ações implementadas têm como foco o aprendizado de Estrutura de Dados pelo uso de recursos computacionais - privilegiando o projeto por simuladores e o desenvolvimento prático; seguido de exposições teóricas, apoiadas por: simulações, slides e vídeos. Em resumo, a metodologia tem como base a tríade Conteúdo, Atividade e Produto.

A nota final será dada pelas avaliações dos artefatos (relatório, lista de exercício - manuscritas, apresentação oral, pôster, postagem, vídeo, ...) produzidos durante as aulas e entregues em cada uma das datas especificadas. O aluno também será avaliado através de outros recursos, como p.ex. a frequência e a apresentação de artefatos não obrigatórios - os quais poderão até ter pontuação extra.

7. Plano de Aprendizado:

Aula 1

Conteúdo:

• • • Revisão: Algoritmos e Estrutura de Dados.

      • Drozdek, A. Estrutura de Dados e Algoritmos em C++. Capítulos 3 e 4.

      • O que é Algoritmo?

      • Estrutura de dados com Roberta Arcoverde.

      • Estruturas de Dados - Ponteiros e Referências.

Atividades:

• • • Listas, Pilhas e Filas em Estruturas de Dados - Qual a diferença?

      • Implementando uma Fila com Orientação a Eventos (Programa).

      • Implementando uma Lista com Orientação a Objetos (também em Assembly).

Produtos:

• • • Algoritmo e Estrutura de Dados: O início da Jornada de um Programador!

    • O que é uma arquitetura orientada por eventos?

    • Listas, pilhas e filas em C++.

    • Programa de Iniciação Científica - Apostilas.

    • Ferramentas: 8-Bit Assembler (tutorial), JDoodle, Tynker.

    • Outros: Tabela ASCII.

Aula 2

Conteúdo:

• • • Introdução à Teoria dos Grafos.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 8.1 a 8.5).

      • Uma Introdução Sucinta à Teoria dos Grafos.

      • Grafos - Conceitos básicos.

Atividades:

• • • Aplicações de Grafos.

      • Implementando Grafo para Solução de Labirinto (Programa).

      • Tabelas Hash.

Produtos:

• • • Estruturas de dados para grafos.

    • Grafos - Conceitos e Implementação Simples (Java).

    • Introdução à Teoria dos Grafos. Programação, Matemática e Curiosidades.

    • Busca em Profundidade.

    • Tabela de Dispersão.

Aula 3

Conteúdo:

• • • Árvores Binárias - Conceito e Características.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 6.1 a 6.3).

      • Introdução a árvores binárias.

      • Introdução Sobre Árvores Binárias.

Atividades:

• • • Árvore Binária de Busca.

      • Binary Search Tree.

        • Implementando uma Árvore Binária com Orientação a Eventos (Programa).

        • Implementando uma Árvore Binária com Orientação a Objetos.

Produtos:

• • • Árvores binárias.

    • Estruturas de Dados: Árvores Binárias.

    • DEG4Tree: Um Jogo Educacional Digital de Apoio ao Ensino de Estruturas de Dados.

    • Um jogo educacional para exercitar propriedades de arvores binarias de busca.

Aula 4

Conteúdo:

• • • Árvores Binárias - Operações e Aplicações.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 6.4 a 6.6).

      • Árvores Binárias - Operações.

Atividades:

• • • PARA QUE usar Árvores (Binária ou Não)?

      • Perguntas:

        • Qual o motivo da escolha?

        • Uma árvore é um tipo de grafo ou um grafo é um tipo de árvore?

    • Método fácil para percursos em Árvore Binária (Pré-Ordem, Em-Ordem, Pós-Ordem).

      • Implementando Percursos em Árvore Binária.

      • Pergunta: Como implementar a definição do nível hierárquico de cada nó?

Produtos:

• • • Algoritmo Colônia de Formigas - Aplicado Ao Problema do Caixeiro Viajante.

    • Determinação de Superfícies Visíveis Para Jogos na Plataforma Playstation Usando Árvores BSP.

    • BSTLearner - An interactive visualization of binary search trees.

    • BST Animation.

Aula 5

Conteúdo:

• • Revisão de conteúdos e 1ª Avaliação.

Atividades:

• • Relatório de Produto 1 ou Prova Prática 1.

Aula 6

Conteúdo:

• • • Árvores Binárias - Balanceamento e Ajuste.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 6.7 e 6.8).

      • O que são ÁRVORES BALANCEADAS? Complexidade de BUSCA, INSERÇÃO, REMOÇÃO.

      • Árvores Balanceadas - AVL.

Atividades:

• • • Árvore AVL.

      • Pergunta: Como implementar o cálculo da altura de cada sub-árvore?

    • Árvores AVL.

      • Implementando Árvore AVL com Orientação a Objetos.

      • Pergunta: Como balancear uma árvore pronta (armazenada em arquivo).

Produtos:

• • • O Que é Árvore AVL, Propriedades da Árvore AVL e Por que AVL é Balanceada.

    • Como implementar uma Árvore AVL - Árvore balanceada?

    • AVL Tree.

Aula 7

Conteúdo:

• • • Árvores Binárias - Heaps e Filas com Prioridade.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópico 6.9).

      • Heap binaria - introdução.

      • O que são FILAS DE PRIORIDADE?

Atividades:

• • • Estrutura de Dados - Heaps.

      • Implementando Árvore Heap com Orientação a Objetos.

      • Tarefa: Implementar Ordenação.

      • Pergunta: Heaps podem facilitar a implementação de Filas com Prioridade?

Produtos:

• • • Heapsort.

    • Organizando dados em Heap e o Heapsort em c++ - Parte 1.

    • Organizando dados em Heap e o Heapsort em c++ - Parte 2.

    • Min Heap.

    • Binary Tree Visualiser.

Aula 8

Conteúdo:

• • • Árvores Binárias - Treaps e K-d.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 6.10 e 6.11).

      • Árvores Treap.

      • Treap (Uma Árvore de Pesquisa Binária Aleatória).

      • Curso Sistemas de Gerenciamento de Bancos de dados (Kd-Trees).

Atividades:

• • • Random Binary Search Tree (TREAP).

      • Implementando Árvore Treap com Orientação a Objetos.

Produtos:

• • • Implicit Treap.

Aula 9

Conteúdo:

• • • Árvores Binárias - Avaliação de Expressões.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópico 6.12).

      • Árvores de Análise Sintática.

Atividades:

• • • Notação infixa para pós-fixa.

      • STALLINGS, W. Arquitetura e Organização de Computadores: Projeto para Desempenho, 8a ed (pg. 323 e 324).

      • Implementando Notação Pós-fixada.

    • Construção de uma árvore de expressão.

      • Implementando uma Árvore de Expressão.

Produtos:

• • • Notação polonesa inversa.

    • Pilhas.

    • Listas, pilhas e filas em C++.

    • Namespaces e Strings em C++.

Aula 10

Conteúdo:

• • Revisão de conteúdos e 2ª Avaliação.

Atividades:

• • Relatório de Produto 2 ou Prova Prática 2.

Aula 11

Conteúdo:

• • • Árvores Múltiplas - Família das Árvores B.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópico 7.1).

      • Árvore B.

      • Arvores B.

      • Árvore B+ Inserção.

      • Árvore B*.

Atividades:

• • • Diferenciando Árvores B de Árvores B+ (inserir 15 números em ordem decrescente).

      • Questões:

        • Qual é a mais eficiente no processo de inserção?

        • Liste pelo menos 2 aplicações para estas árvores.

Produtos:

• • • Índices: Árvore B e B+.

    • B-Tree Indexes.

Aula 12

Conteúdo:

• • • Árvores Múltiplas - Tries.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópico 7.2).

      • Árvores N árias: Tries.

Atividades:

• • • Observando a criação de uma Árvore Trie.

      • Questão: Liste pelo menos 2 aplicações para estas árvores.

Produtos:

• • • Tries - Árvores de Prefixos.

Aula 13

Conteúdo:

• • • Ordenações elementares e Árvore de Decisão.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópicos 9.1 e 9.2).

      • Algoritmos clássicos de ordenação I.

      • COMPLEXIDADE de Selection, Bubble, Insertion Sort.

      • Aplicação para Ordenações e Árvores.

        • Fundamentos Matemáticos para Computação - Árvores de decisão.

        • Árvores de Decisão - Exemplo completo com construção e cálculo.

Atividades:

• • • Observando e Comparando Algoritmos de Ordenação.

      • Questões:

        • Qual a importância dos algoritmos de ordenação?

        • Liste pelo menos 2 aplicações para estas árvores.

    • Simplificando o processo de aprendizado.

      • Algoritmos de Ordenação.

      • Como que computadores ordenam dados?

Produtos:

• • • Árvore de decisão - Como funciona (Machine Learning).

    • Modelos de Machine Learning, qual algoritmo usar?

    • A visual introduction to machine learning.

Aula 14

Conteúdo:

• • • Ordenações Eficientes.

      • DROZDEK, A. Estrutura de Dados e Algoritmos em C++ (Tópico 9.3).

      • Ordenação: CountingSort.

      • Radix sort + Pokémon.

      • Introdução às Árvores Patricia.

Atividades:

• • • Comparando Radix Sort com Radix Tree.

Produtos:

• • • Introdução ao Radix sort e exemplo de implementação em Java.

    • Radix Tree visualization web Demo.

Aula 15

Conteúdo:

• • Revisão de conteúdos e 3ª Avaliação.

Atividades:

• • Relatório de Produto 3 ou Prova Prática 3.

8. Bibliografia:

• • Cormen, T. H., Leiserson, C. E., Rivest, R. L., e Stein, C. (2012). Algoritmos – Teoria e Prática. Campus, 3a edição.

  • Drozdek, A. (2017). Estrutura de Dados e Algoritmos em C++. Cengage, 4a edição.

  • Goldbarg, M. C. e Goldbarg, E. (2012). Grafos – Conceitos, Algoritmos e Aplicações. Elsevier, 1a edição.