Estruturas de Dados e seus Algoritmos (TCC-00.348)

horários das aulas: terças e quintas de 11:00 às 13:00h na sala 213

Objetivos

Tópicos Abordados

• Árvores binárias, binárias de busca e AVL;
• Grafos;
• Arquivos;
• Ordenação externa de arquivos binários e texto (para o último tipo de arquivo, a ordenação é dividida em duas etapas: geração de partições classificadas e intercalação de partições);
• Árvores B e B⁺;
• Tabelas hash (ou de dispersão) mantidas em memórias principal e secundária; e
• Listas de prioridade (ou heaps) mantidas em memórias principal e secundária.

Critério de avaliação

Bibliografia básica

• T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill, 2009.
• J. Szwarcfiter e L. Markenzon, Estruturas de Dados e Algoritmos, LTC, 1994.
• W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus, 2004.
• I.N. Ferraz, Programação com Arquivos, Manole Ltda, 2003.
• B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Campus, Segunda Edição, 1990.

Bibliografia complementar

• A.M. Tenenbaum, Y. Langsam e M.J. Augenstein, Estruturas de Dados Usando C, Pearson, Primeira Edição, 1995.
• R. Ramakrishnan, Database Management Systems, McGraw Hill, Third Edition, 2003.

Aulas ministradas

• 13/03/18

  • Apresentação do curso: tópicos a serem apresentados e critério de avaliação a ser empregado; e
  • Revisão da linguagem C, especialmente ponteiros e recursão (versões iterativa e recursiva de ordenação de listas).
  • Datas importantes:
    • P1: 22/05/18
    • P2: 03/07/18
    • VR: 05/07/18
    • VS: 17/07/18
    • Entrega do trabalho: 01/07/18 até às 23:59
    • Entrega de todas as notas da disciplina (antes da VS): 12/07/18

• 15/03/18

  • Revisão de recursão na linguagem C em:
    • listas simplesmente encadeadas: inserções na última posição e ordenada; e
    • strings: implementação da função strcmp da biblioteca string.h.

• 20/03/18

  • Motivação para o uso de árvores e árvores binárias;
  • Implementação de árvores binárias;
  • Percurso em árvores binárias: pré-ordem (ou profundidade), simétrica, pós-ordem e largura;
  • Operações básicas: (a) inicialização e (b) diversas formas de impressão: profundidade (versões recursiva e iterativa, por meio do uso de uma implementação específica de pilha), simétrica (versão recursiva), pós-ordem (versão recursiva) e largura (versão iterativa usando uma implementação específica de fila); e
  • Exercícios.

• 22/03/18

  • Outras operações sobre árvores binárias desenvolvidas em sala: (a) libera todos os nós, (b) busca um elemento na árvore e (c) cria uma árvore (a partir dos seguintes parâmetros de entrada: a informação do nó raiz e as sub-árvores esquerda e direita) e (d) calcula a altura de uma árvore binária;
  • Motivação para o uso de árvores binárias de busca (ABB);
  • Implementação de árvores binárias de busca;
  • Operações básicas (que diferem de árvore binária original): busca e inserção de um elemento.
  • Exemplo feito em sala: criação de uma árvore de busca binária mais "balanceada" possível a partir de um vetor ordenado; e
  • Exercícios.

• 27/03/18

  • remoção em árvores binárias de busca;
  • Motivação para o uso de árvores binárias AVL;
  • Definição de árvores binárias AVL; e
  • Operações básicas: (a) rotação simples a esquerda e (b) rotação simples a direita.

• 03/04/18

  • Rotações duplas esquerda-direita e direita-esquerda;
  • Apresentação, por meio de exemplos, das operações de inserção e retirada em AVL, utilizando, quando necessário, as operações de rotação supracitadas; e
  • Exercícios.

• 05/04/18

  • Código da árvore binária de busca AVL;
  • Grafos e dígrafos: apresentação de conceitos;
  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) impressão e (c) liberação da estrutura.

• 10/04/18

  • Demais operações em grafos: busca, inserção e retirada, realizadas em nós e arestas do grafo; e
  • Exemplo de aplicação: função que verifica se um nó tem cor diferente de seus vizinhos. A função retorna UM se a propriedade é válida para todos os nós do grafo e ZERO, caso contrário.

• 12/04/18 (aula no Laboratório 306)

  • Pacote de bibliotecas usadas para a resolução dos exercícios.
  • Exercícios sobre as seguintes estruturas de dados:
    1. grafos:
       • verificar se o grafo, passado como parâmetro de entrada, é completo; e
       • testar se dois grafos são iguais.
    2. árvores binárias:
       • verificar se uma árvore binária, passada como parâmetro de entrada, é zigue-zigue;
       • testar se uma árvore binária, passada como parâmetro de entrada, é zigue-zague;
       • testar se duas árvores possuem os mesmos nós; e
       • verificar se uma árvore binária possui o seguinte padrão: o filho da esquerda é sempre folha e o filho da direita ou é nulo, ou possui dois filhos.

• 17/04/18

  • Definição de arquivo, stream e de buffer;
  • Tipos de arquivos: binários e de texto;
  • Outra classificação de arquivos: sequenciais e em série;
  • Funções para manipulação de arquivos em C (biblioteca stdio.h):
    • fopen e fclose para abrir e fechar arquivos, respectivamente;
    • fscanf e fprintf para leitura e escrita de informações em arquivos texto, respectivamente;
    • fgetc e fputc para leitura e escrita de caracteres em arquivos texto, respectivamente;
    • fflush para descarregar o buffer; e
    • Exemplo de uso destas funções: merge de dois arquivos texto ordenados, gerando um terceiro também ordenado sem elementos repetidos.

• 19/04/18

  • Funções para manipulação de arquivos binários em C (biblioteca stdio.h):
    • fread e fwrite para leitura e escrita de informações, respectivamente;
    • fseek para mover a posição de um arquivo binário para uma nova posição específica;
    • rewind para colocar o cursor no início do arquivo binário; e
    • ftell para obter a posição corrente do arquivo binário.
  • Outras funções aplicadas sobre arquivos: feof, rename e remove; e
  • Exemplos de uso destas funções: geração de arquivos ordenados (modo texto e modo binário), e algoritmos já conhecidos na literatura e implementados em arquivos binários: busca binária e ordenação por inserção.

• 24/04/18

  • Implementações de busca binária e ordenação por seleção;
  • Código do QuickSort em arquivos; e
  • Exercícios: reescreva os algoritmos de ordenação e de busca binária desenvolvidos nesta disciplina, de modo que eles suportem quaisquer tipos de dados.

• 26/04/18

  • Motivação para classificação (ou ordenação) externa;
  • Etapas da classificação externa: geração de partições ordenadas e intercalação dessas partições;
  • Algoritmos que podem ser usados na etapa de geração de partições classificadas: ou classificação interna, ou seleção com substituição, ou seleção natural;
  • Implementação de classificação interna; e
  • Ideia do algoritmo de seleção com substituição.

• 03/05/18

  • Implementação do algoritmo de seleção com substituição;
  • Ideia e desenvolvimento da primeira versão do algoritmo de seleção natural;
  • Pacote de algoritmos de geração de partições classificadas; e
  • Exercício: reescreva o algoritmo de seleção natural (com o reservatório implementado em memórias primária e secundária), sendo (a) o reservatório maior que a memória principal e (b) o reservatório menor que a memória principal.

• 08/05/18

  • Segunda etapa da classificação externa: intercalação;
  • Objetivo desta etapa;
  • Intercalação de arquivos sequenciais ordenados: cenário de uso;
  • Algoritmo básico: O(n) na busca pela menor chave;
  • Otimização do algoritmo básico - uso de árvores binárias de vencedores: O(log n) na busca pela menor chave; e
  • Exercício: refaça o algoritmo de árvores binárias de vencedores usando a estrutura de árvore binária no lugar da implementação prévia de heap.

• 10/05/18

  • Implementação do algoritmo básico de intercalação e do algoritmo de árvores binárias de vencedores;
  • Problema da etapa de intercalação: geração do arquivo final a partir de arquivos de partições, com a limitação de um sistema operacional manter um número finito de arquivos abertos;
  • Medida de eficiência: número de passos;
  • Ideia do algoritmo de intercalação ótima;
  • Motivação para o uso de árvores de múltiplos caminhos;
  • Introdução a árvores B; e
  • Exercício: considerando um dos algoritmos de geração de partições classificadas e árvores binárias de vencedores, implemente a intercalação ótima, com a limitação de um sistema operacional hipotético manter somente 10 arquivos abertos simultaneamente.

• 15/05/18

  • Definição de árvores B; e
  • Implementação da estrutura de árvore B e das seguintes operações: (a) inicializa, (b) cria nó de árvore B, (c) busca, (d) imprime e (e) libera.

• 17/05/18 (aula de dúvidas para a P1)

• 22/05/18 (P1 de 11:00 às 13:00h na sala 213)

• 24/05/18

  • Implementação da operação de inserção, bem como das operações de divisão e de inserção em um nó não completo necessárias para o funcionamento dessa codificação; e
  • Trabalho computacional - manipulação de árvore B⁺ por meio do gerenciamento de uma playlist hipotética → dados, como parâmetros de entrada do seu programa, o fator de ramificação (t) da árvore B⁺ e uma playlist qualquer num formato bem definido, seu programa deve ser capaz de distinguir entre as informações principais consideradas chaves primárias (nesse caso, o nome do cantor, acrescido do ano de publicação da obra) e as informações subordinadas (nome do álbum, número de faixas e tempo total da mídia). É importante salientar que em árvores B⁺ as informações subordinadas (e as informações principais) encontram-se nas folhas dessas árvores. Os nós internos só possuem as chaves primárias. As seguintes operações que devem ser implementadas nesse trabalho:
    • inserção e remoção de nós da árvore B⁺;
    • busca das informações subordinadas, dada a chave primária;
    • alteração SOMENTE das informações subordinadas;
    • busca de todas as obras de um(a) artista; e
    • retirada de um(a) artista e todas as suas obras de uma playlist.
    Informações importantes:
    • exemplo de formato de arquivo de entrada (que deve ser seguido pelo seu programa);
    • grupo de no mínimo dois e de no máximo três discentes;
    • data limite de entrega: 01/07/18 às 23:59h; e
    • semana de apresentação: de 02 até 06/07/18.

• 29/05/18 (não houve aula porque a UFF estava fechada)

• 05/06/18

  • Explicação dos casos necessários (1, 2A, 2B, 2C, 3A e 3B) para o desenvolvimento do algoritmo de remoção em árvores B, ilustrando-os com exemplos; e
  • Execução de um código que implementa árvore B.

• 07/06/18 (revisão da nota da primeira prova e disponibilização de parte do gabarito utilizado)

• 12/06/18

  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Discussão de algumas operações em árvores B⁺:
    • Implementação da operação de encontrar, dada a chave, um nó na árvore;
    • Explicação de como tratar as divisões de nós requeridas na operação de inserção, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas; e
    • Soluções encontradas para tratar os casos 3A e 3B da operação de retirada, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas.

• 14/06/18

  • Ordem de apresentação do trabalho computacional;
  • Motivação para o uso de tabelas hash (ou tabelas de dispersão);
  • Definição de tabelas hash;
  • Funções de hash;
  • Características ideais destas funções: ser facilmente computável, ser determinística, ser uniforme e produzir um número baixo de colisões; e
  • Definição das operações (usando tentativa linear): (a) inicializa, (b) aloca, (c) insere e (d) busca.

• 19/06/18

  • Tipos de tratamento de colisões: (a) por endereçamento aberto, (b) por encadeamento externo e (c) por encadeamento interno;
  • Outras tentativas de cálculo de novo endereçamento devido as colisões, além da linear: (a) quadrática e (b) dispersão dupla;
  • Outras operações para o tratamento de colisão por meio do uso de endereçamento aberto em memória principal: (a) retira e (b) libera;
  • Tratamento de colisão usando encadeamento externo para a memória principal;
  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória principal: (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera; e
  • Discussão do tratamento de colisões por encadeamento interno em memória principal.

• 21/06/18

  • Tratamento de colisão usando encadeamento interno em memória principal;
  • Definição das operações para o tratamento de colisões baseado em encadeamento interno em memória principal: (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera;
  • Implementações dos tratamentos de colisão em memória principal: endereçamento aberto, encadeamento interno, encadeamento externo;
  • Discussão do tratamento de colisão por encadeamento externo em memória secundária; e
  • Exercício: desenvolver as operações (a) inicializa, (b) aloca, (c) insere, (d) busca, e (e) retira para o tratamento de colisão por encadeamento externo em memória secundária.

• 26/06/18

  • Motivação para o uso de listas de prioridades ou heaps binários;
  • Definição das operações de heaps em memória principal:
    • int pai (int indice);
    • int esquerda (int indice);
    • int direita (int indice);
    • void max_heapfy (int* heap, int n, int indice);
    • void build_maxheap (int* heap, int n); e
    • void heapsort (int* heap, int n).
  • Implementação das operações supracitadas para memória secundária, exceto build_maxheap e heapsort.
  • Exercício: desenvolver build_maxheap e heapsort para heaps binários em memória secundária.

• 28/06/18 (aula de dúvidas para a P2)

• 03/07/18 (P2 de 11:00 às 13:00h na sala 213)

• 05/07/18 (VR de 11:00 às 13:00h na sala 213)

• 03, 09, 11, 12/07/18 (apresentações dos trabalhos computacionais)

• 12/07/18 (revisão de nota da P2 e da VR)

• 13/07/18 (nota do Trabalho Computacional e das revisões da P2 e da VR)

• 17/07/18 (VS de 11:00 às 13:00h na sala 213)

  • Divulgação das notas finais.