Estruturas de Dados II (TCC-00.295)

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

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.

Horários de Monitoria

• Maria Edoarda Vallim Fonseca (mavericktailsdoll@gmail.com): terças de 11:00 às 13:00h, quartas de 14:00 às 18:00h, e quintas de 11:00 às 13:00h.

Aulas ministradas

• 30/08/16

  • Apresentação do curso: tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
    

• 01/09/16

  • 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;
    • fread e fwrite para leitura e escrita de informações em arquivos binários, respectivamente;
    • fscanf e fprintf para leitura e escrita de informações em arquivos texto, respectivamente; 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.
  • Datas das provas:
    • P1: 17/11/16
    • P2: 15/12/16
    • VR: 03/01/17
    • VS: 17/01/17
    
    

• 06/09/16

  • Mais funções para manipulação de arquivos em C:
    • remove para apagar arquivos;
    • rename para renomear arquivos;
    • tmpfile para criar arquivos temporários;
    • fseek para mover a posição de um arquivo para uma nova posição específica;
    • rewind para colocar o cursor no início do arquivo; e
    • ftell para obter a posição corrente do arquivo.
  • Algoritmos já conhecidos na literatura e implementados em arquivos: busca binária e ordenação por inserção.
    

• 08/09/16 (não houve aula)

• 13/09/16

  • QuickSort em arquivos;
  • DOJO: ordenação pelo método da bolha; 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.
    

• 15/09/16

  • 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: classificação interna e seleção com substituição; e
  • Ideia do algoritmo de seleção com substituição.
    

• 20/09/16

  • Seleção com substituição desenvolvido em sala.
    

• 22/09/16

  • Funcionamento do algoritmo de seleção com substituição;
  • Ideia 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.
    

• 27/09/16

  • 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;
  • Funcionamento do algoritmo que utiliza árvores binárias de vencedores CORRIGIDO. Foram geradas 10 partições e a implementação foi testada variando o número de arquivos N no intervalo [1,10]; e
  • Exercício: refaça o algoritmo de árvores binárias de vencedores usando:
    • a posição zero do vetor que armazena a heap; e
    • a estrutura de árvore binária, no lugar da implementação prévia de heap.
      
    
    

• 29/09/16

  • 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;
  • Algoritmos que podem ser usados nesta etapa: intercalação balanceada de N caminhos e intercalação ótima; e
  • Exercício: considerando um dos algoritmos de geração de partições classificadas e árvores binárias de vencedores, implemente os algoritmos de intercalação balanceada de N caminhos e intercalação ótima, com a SUPOSTA limitação de um sistema operacional hipotético manter somente 4 arquivos abertos simultaneamente.
    

• 04/10/16

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

• 06/10/16

  • 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;
  • 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 e busca para o tratamento de colisões baseado em endereçamento aberto.
    

• 11/10/16

  • Desenvolvimento das demais operações (usando tentativa linear): libera e retira para o tratamento de colisões baseado em endereçamento aberto;
  • 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 e aloca para o tratamento de colisões baseado em encadeamento externo.
    

• 13/10/16

  • Definição das demais operações (em memória secundária): busca, insere e retira para o tratamento de colisões baseado em encadeamento externo; e
  • Ideias de como podem ser implementados os encadeamentos internos em memória principal e em memória secundária.
    

• 18/10/16 (não houve aula)

• 20/10/16 (não houve aula)

• 25/10/16

  • Tratamento de colisão usando encadeamento interior 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 interior;
  • Tratamento de colisão usando encadeamento interior para a memória secundária;
  • Ideia das operações em memória secundária; 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.
    

• 27/10/16

  • Execuções dos tratamentos de colisão supracitados;
  • 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 e (b) AVL;
  • 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 cria nó de árvore B e inicializa.

• 01/11/16

  • Implementação de mais algumas operações: (a) busca, (b) libera e (c) insere, bem como das operações de divisão e de inserção em um nó não completo usadas no código de insere.
    

• 03/11/16

  • Explicação dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B, ilustrando-os com exemplos.
    

• 08/11/16

  • Execução de um código que implementa árvore B;
  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺; e
  • Discussão sobre operações em árvores B⁺: busca, insere e retira.
    

• 10/11/16

  • Mais discussão sobre as operações busca (com exemplo de implementação), insere e retira em árvores B⁺;
  • Soluções encontradas para tratar os casos 3A e 3B 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;
  • Trabalho computacional - manipulação de árvore B⁺ em memória principal: considere que uma Universidade hipotética possui três currículos vigentes - (a) currículo 1 com 2955h, com tempos nominal e máximo de 8 e 16 períodos, respectivamente; (b) currículo 2 com 3524h, com tempos nominal e máximo de 8 e 12 períodos, respectivamente; e (c) currículo 3 com 3200h, com tempos nominal e máximo de 8 e 12 períodos, respectivamente - para um mesmo curso de graduação, e que seu grupo tenha sido contratado para desenvolver esta base de dados usando árvores B⁺. Assim, seu grupo deve implementar as seguintes funcionalidades:
    1. desenvolver todas as operações relacionadas a árvores B⁺;
    2. implementar todas as operações de manipulação da estrutura de dados dos discentes (isto é, alterar coeficiente de rendimento, número de trancamentos, carga horária cursada com aprovação, número de períodos que o discente está na referida Universidade);
    3. remover os formandos do referido curso;
    4. retirar da árvore B⁺ todos os discentes que violem a regra de 50% curso não concluído no tempo nominal do curso;
    5. remover da árvore B⁺ todos os alunos que violem a regra de tempo máximo sem concluir a graduação; e
    6. requisitos de implementação:
       • grupo de no mínimo dois e de no máximo três discentes;
       • exemplo de arquivo de entrada com o seguinte formato, onde todos os campos separados com espaço em branco: matrícula, coeficiente de rendimento, número de trancamentos, carga horária cursada com aprovação, número de períodos que o discente está na referida Universidade, seu currículo e nome;
       • data limite de entrega: 18/12/16 às 23:59h; e
       • semana de apresentação: de 19/12/16 até 20/12/16.
         
    
    

• 15/11/16 (não houve aula)

• 17/11/16 (P1 de 13:00 às 16:00 na sala 204)

• 22/11/16 (não houve aula)

• 24/11/16

  • Exercício de árvore B⁺: encontrar o primeiro antecessor e sucessor de um elemento (se eles existirem); e
  • Divulgação do calendário de apresentações de todos os trabalhos:
    • 19/12/16 às 11:15h → G2 (ERICK SIMAS GRILO, MATHEUS TAVARES PRADO e VITOR SANTOS DE ARAÚJO)
    • 19/12/16 às 13:00h → G4 (ALYSSON GERALDO GOMES DA SILVA e FELIPE DE BRITO VIEIRA)
    • 19/12/16 às 13:45h → G5 (ANDRÉ LUIZ PEREIRA DE OLIVEIRA JUNIOR, CAROLINA ALVES DE OLIVEIRA RANSATTO e JOÃO PEDRO SÁ MEDEIROS)
    • 19/12/16 às 14:30h → G1 (ARTHUR BASTOS BRAGA COELHO, ARTHUR MONTEIRO FERRAZ e LEONARDO SCHIMPF MACHADO)
    • 19/12/16 às 16:00h → G6 (JOÃO PEDRO ABREU DE SOUZA, MAURÍCIO DA SILVA PIRES e MAURO SERGIO LOPES DOS SANTOS JUNIOR)
    • 19/12/16 às 16:45h → G3 (FELIPE JOSÉ PERPÉTUO ASSAD, FELIPE RESAFFI TAVARES e THIAGO AUGUSTO SIVIRINO)
      
    
    

• 29/11/16 (revisão da nota da primeira prova, disponibilizando o gabarito utilizado)

• 01/12/16

  • 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;
  • Implementação da solução por meio de arquivos com lista para a indexação de arquivos por chaves secundárias; e
  • Ideia de implementação da solução por meio de arquivos invertidos.
    

• 06/12/16

  • Implementação da solução por meio de arquivos invertidos para a indexação de arquivos por chaves secundárias.
    

• 08/12/16 (não houve aula)

• 13/12/16 (não houve aula)

• 15/12/16 (P2 de 13:00 às 16:00h na sala 204)

• 19/12/16 (apresentação de trabalho computacional)

• 20/12/16 (não houve aula)

• 22/12/16 (não houve aula)

• 03/01/17 (VR de 13:00 às 16:00h na sala 204)

• 05/01/17 (não houve aula)

• 10/01/17 (revisão de nota da P2)

• 12/01/17 (não houve aula)

• 17/01/17 (VS de 13:00 às 16:00h na sala 204)

• 19/01/17 (revisão de nota da VS)

  • Divulgação das notas.