Estruturas de Dados II (TCC-00.295)

horários das aulas: terças e quintas de 14:00 às 16:00h na sala 206

Objetivos

Tópicos Abordados

• Tutorial sobre manipulação de arquivos em C;
• Exemplos de manipulação de arquivos;
• Ordenação externa: geração de partições classificadas e intercalação de partições;
• Listas de prioridade (ou heaps);
• Arquivos de acesso direto: tabelas hash (ou de dispersão);
• Arquivos indexados: árvores B e suas variantes B⁺ e B^*;
• Arquivos indexados por chaves secundárias; e
• Compressão de arquivos.

Critério de avaliação

Literatura básica

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

Aulas ministradas

• 23/03/17

  • Apresentação do curso: tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
  • Definição de arquivo e de buffer;
  • Tipos de arquivos: binários e de texto;
  • Funções para manipulação de arquivos em C:
    • fopen e fclose para abrir e fechar arquivos, respectivamente;
    • fscanf e fprintf para leitura e escrita de informações em arquivos texto, respectivamente;
    • fread e fwrite para leitura e escrita de informações em arquivos binários, 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;
    • ftell para obter a posição corrente do arquivo binário; e
    • Exemplos de uso destas funções: geração de arquivos texto e binário, e merge de dois arquivos texto ordenados, gerando um terceiro também ordenado.
    
    

• 28/03/17

  • Algoritmos já conhecidos na literatura e implementados em arquivos: busca binária e ordenação por inserção.
  • Datas das provas:
    • P1: 30/05/17
    • P2: 29/06/17
    • VR: 04/07/17
    • VS: 18/07/17
    
    

• 30/03/17

  • Método da bolha em memória secundária;
  • 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.
    

• 04/04/17

  • Motivação para o uso de listas de prioridades ou heaps binários;
  • Definição das operações de heaps em memória principal, desconsiderando a posição zero da estrutura de dados:
    • 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ícios: desenvolver build_maxheap e heapsort para heaps binários em memória secundária; e implementar heaps k-árias para as memórias principal e secundária.
  
  

• 06/04/17

  • Motivação para classificação (ou ordenação) externa;
  • Etapas da classificação externa: geração de partições classificadas e intercalação;
  • 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.
    

• 11/04/2017

  • Implementação do algoritmo de seleção com substituição;
  • Ideia e desenvolvimento da primeira versão do algoritmo de seleção natural; 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.
    

• 13/04/17 (não houve aula)

• 18/04/17

  • 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;
  • Exercício: refaça o algoritmo de árvores binárias de vencedores usando:
    • a posição zero da heap binária;
    • o conceito de heap k-ária; e
    • a estrutura de árvore binária, no lugar da implementação prévia de heap.
      
    
    

• 20/04/17

  • Funcionamento 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; 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 25 arquivos abertos simultaneamente.
    

• 25/04/17 (não houve aula)

• 27/04/17

  • 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;
  • Tipos de tratamento de colisões: (a) por endereçamento aberto, (b) por encadeamento exterior e (c) por encadeamento interior;
  • Tratamento de colisão por meio do uso de endereçamento aberto (em memória principal);
  • Tentativas de cálculo de novo endereçamento devido as colisões: (a) linear, (b) quadrática e (c) dispersão dupla; e
  • Definição das operações (usando tentativa linear): inicializa, aloca, insere, busca, libera e retira para o tratamento de colisões baseado em endereçamento aberto.
    

• 02/05/17

  • Tratamento de colisão usando encadeamento externo para a memória principal;
  • Definição das operações (em memória principal): inicializa, aloca, insere, busca, libera e retira para o tratamento de colisões baseado em encadeamento externo;
  • Tratamento de colisão usando encadeamento externo para a memória secundária; e
  • Definição das operações (em memória secundária): inicializa, aloca e busca para o tratamento de colisões baseado em encadeamento externo.
    

• 04/05/17

  • Definição das demais operações (em memória secundária): insere e retira para o tratamento de colisões baseado em encadeamento externo; e
  • Implementações dos tratamentos de colisão usando encadeamento externo em memória principal e em memória secundária.
    

• 09/05/17

  • Execução das implementações dos tratamentos de colisão usando encadeamento externo;
  • Tratamento de colisão usando encadeamento interior para a memória secundária;
  • Ideias das operações em memória secundária;
  • Tratamento de colisão usando encadeamento interior para a memória principal; e
  • Definição das operações (em memória principal): inicializa, aloca e libera para o tratamento de colisões baseado em encadeamento interior.
    

• 11/05/17

  • Definição das demais operações para o tratamento de colisões baseado em encadeamento interior em memória principal: insere, busca e retira;
  • Implementação do encadeamento interno em memória principal;
  • Definição de índice;
  • Uso de estruturas de dados hierárquicas para representar os índices;
  • Revisão de árvores de busca: (a) árvore de busca binária, (b) AVL e (c) AVP; e
  • Exercício: implemente as operações inicializa, aloca, insere, busca, libera e retira para o tratamento de colisões baseado em encadeamento interior para a memória secundária. Este tipo de tratamento é semelhante ao tratamento de colisões baseado em encadeamento externo para o mesmo tipo de memória.
    

• 16/05/17

  • Motivação para o uso de árvores de múltiplos caminhos;
  • Introdução a árvores B;
  • Definição de árvores B; e
  • Implementação das funções inicializa, aloca nó de árvore B, busca e libera.

• 18/05/17

  • 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 usadas no código de insere; e
  • Trabalho computacional - manipulação de árvore B em memória secundária:
    • grupo de no mínimo dois e de no máximo três discentes;
    • data limite de entrega: 25/06/17 às 23:59h; e
    • semana de apresentação: de 26 até 30/06/17.
      
    
    

• 23/05/17

  • Explicação dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B, ilustrando-os com exemplos;
  • Implementação de árvore B; e
  • Ordem de apresentação do trabalho computacional:
    • 26/06/17 às 13:00h - G09 (CAIO RIBEIRO SARACUZA LUZ e LUCAS LOPES DE MORAES PINTO)
    • 26/06/17 às 15:00h - G05 (GUSTAVO PERGOLA BAHIENSE DIAS, NICHOLAS VASCONCELOS QUINTELLA e PEDRO PAULO BASTOS TEIXEIRA)
    • 26/06/17 às 16:00h - G06 (LUCAS DIAS DE ESPINDOLA, NATALIA ROCHA DE ALMEIDA PIPAS e VICTOR CARNEIRO FARDIM)
    • 27/06/17 às 15:00h - G02 (CARLOS HENRIQUE DOMINGOS CORREIA SANTOS, FABRICIO MARTINS FARIAS e GABRIELA GOMES DA SILVA)
    • 30/06/17 às 11:00h - G08 (MATEUS AZEREDO TORRES e RENATO ARAUJO BASTOS)
    • 30/06/17 às 13:00h - G01 (JULIA FIGUEIREDO SIMAO FALCAO, RAFFAEL MURALHA PARANHOS e RAPHAEL LEARDINI BENDAS ROBERTO)
    • 30/06/17 às 14:00h - G03 (FELIPE GENU SIMOES, HELENA CAMPO MACEIRA BELAY e JULIA DRUMMOND NOCE)
    • 30/06/17 às 15:00h - G04 (GABRIEL COSTA E SILVA, GABRIEL FIUZA DE ALBUQUERQUE EL HAGE e VITOR AUGUSTO BASTOS PINHEIRO)
    • 30/06/17 às 16:00h - G10 (GABRIEL DUARTE RODRIGUES, HENRIQUE PROENCA DICKSON SERRANO e RODRIGO QUEIROZ SOUZA DA CONCEICAO)
    • 30/06/17 às 17:00h - G07 (PHELIPE GONCALVES MARTINS, RENATO LUIZ MOURA DE AZEVEDO e RODRIGO FABRICANTE DE CASTRO)
      
    
    

• 25/05/17 (dúvidas para a P1)

• 30/05/17 (P1 de 13:00 às 15:45h na sala 206)

• 01/06/17

  • Execução de um código que implementa árvore B; e
  • Discussão sobre árvores B⁺.
    

• 06/06/17

  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Discussão de algumas operações em árvores B⁺: busca (com exemplo de implementação), insere e retira;
  • Explicação para tratar as divisões de nós requeridas na operação de inserção; e
  • Soluções encontradas para tratar os casos 3A e 3B da operação de retirada, quando estão envolvidos somente nós internos, e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas.
    

• 08/06/17

  • Implementação de árvores B⁺;
  • Motivação para o uso de arquivos indexados por chaves secundárias;
  • Tipos de índices secundários: arquivos com lista, arquivos invertidos e arquivos multilista;
  • Ideia de implementação da solução por meio de arquivos com lista;
  • Desenvolvimento da solução por meio de arquivos invertidos para a indexação de arquivos por chaves secundárias; e
  • Exercício: implemente a operação de retirada de nós em árvores B⁺.
    

• 13/06/17 (revisão da nota da primeira prova, disponibilizando o gabarito utilizado)

• 15/06/17 (não houve aula)

• 20/06/17

  • Implementação da solução por meio de arquivos invertidos, juntamente com o arquivo de entrada usado;
  • Arquivos multilista (apresentação dos seis passos do Algoritmo de Lefkowitz); e
  • Desenvolvimento da solução por meio de arquivos com lista para a indexação de arquivos por chaves secundárias.
    

• 22/06/17

  • Implementação da solução por meio de arquivos com lista, juntamente com o arquivo de entrada usado; e
  • Motivação para o uso de compressão de arquivos; e
  • Ideia de compressão de arquivos usando Código de Huffman.
    

• 27/06/17

  • Revisão para a P2: (a) inserções e retiradas em árvores B e B⁺, (b) explicação sobre o uso de arquivos indexados por chaves secundárias (arquivos com lista e arquivos invertidos) e (c) descoberta do antecessor de uma chave numa árvore B.
    

• 29/06/17 (P2 de 13:00 às 15:45h na sala 206)

• 04/07/17 (VR de 13:00 às 15:45h na sala 206)

• 06/07/17 (revisão de nota da P2 e da VR)

• 18/07/17 (VS de 13:00 às 15:45h na sala 215)

• 20/07/17 (revisão de nota da VS e publição das notas finais.)