Estruturas de Dados II (TCC-00.215)

horário: terças (UFASA: 303) e quintas (UFASA: 304) de 11:00 às 13:00h

Tópicos Abordados

• Conceitos importantes: entidades, atributos, registros, tabelas, chaves e arquivos;
• Tutorial sobre manipulação de arquivos em C;
• Arquivos sequenciais: busca, ordenação, atualização em lote e intercalação;
• Classificação: externa e interna;
• Arquivos de acesso direto: hashing;
• Arquivos indexados:
  • árvores de busca binária e árvores B e suas variantes (B⁺ e B^*);
  • arquivos com lista;
  • arquivos multilista; e
  • arquivos invertidos.

Critério de avaliação

Literatura básica

• I.N. Ferraz, Programação com Arquivos, Editora Manole Ltda.
• T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill.
• J. Szwarcfiter e L. Markeson, Estrutura de Dados e Algoritmos, Editora LTC.
• 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), Editora Campus.

Aulas ministradas

• 20/11/12

  • Apresentação do curso: objetivos, tópicos abordados e critério de avaliação.
    

• 22/11/12

  • Revisão da linguagem C: tipos, variáveis, funções, pilha de execução e ponteiros.
    

• 27/11/12

  • Definição: entidades, atributos e registros;
  • Chaves: primárias, secundárias e primárias alternativas;
  • Tabelas;
  • Arquivos; e
  • Exemplos ministrados em sala: aplicação bancária e locadora de automóveis.
    

• 29/11/12

  • Definição de arquivo, stream e buffer;
  • Tipos de arquivos: binários e de texto;
  • Outra classificação de arquivos: sequenciais e em série; e
  • Funções para manipulação de arquivos em C:
    • setbuf e setvbuf para gerenciar buffers;
    • fopen e fclose para abrir e fechar arquivos, respectivamente;
    • feof para verificar se foi alcançado o final de um arquivo;
    • fflush para armazenar todas as informações do buffer em um arquivo; e
    • fscanf, fgetc e fgets para leitura de informações em arquivos de texto.
    
    

• 04/12/12

  • Outras funções para manipulação de arquivos em C:
    • fprintf, fputc e fputs para escrita de informações em arquivos de texto;
    • fread e fwrite para leitura e escrita de informações em arquivos binários, respectivamente;
    • 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.
  • Revisão de algoritmos de ordenação: seleção, bolha e quicksort.
  • OBS: datas das provas
    • P₁: a definir
    • P₂: 07/03/13
    • VS: 14/03/13
      
    
    

• 06/12/12

  • Algoritmos já conhecidos na literatura e implementados em arquivos:
    • busca binária em arquivos ordenados; e
    • ordenação por seleção.
  • OBS: não haverá aulas nos dias 03/01/13 e 14/02/13.
    

• 11/12/12

  • DOJO: ordenação em arquivos usando bolha.
  • Primeiro exercício computacional: mergesort de arquivos usando arquivos temporários.
    

• 13/12/12

  • Atualização em lote: cenário de uso;
  • Arquivos ordenados por chave primária: mestre e de transações; e
  • Funcionamento do algoritmo balance line.
    

• 18/12/12

  • Implementação do algoritmo balance line.
  • 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
  • Funcionamento do algoritmo que utiliza árvores binárias de vencedores.
  • Segundo exercício computacional: balance line usando registros compostos de nome, CPF, matrícula, endereço, telefone, CR, porcentagem de curso concluída, ano de ingresso, identidade e e-mail.
    

• 20/12/12

  • Auxílio na implementação do mergesort: ordenação em arquivos usando quicksort;
  • Funcionamento do algoritmo de intercalação usando árvores binárias de vencedores; e
  • Terceiro exercício computacional: algoritmo de intercalação usando árvores binárias de vencedores e registros compostos de nome, CPF, matrícula, endereço, telefone, CR, porcentagem de curso concluída, ano de ingresso, identidade e e-mail.
    

• 03/01/13 (não houve aula)

• 08/01/13

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

• 10/01/13

  • Funcionamento do algoritmo de seleção com substituição;
  • DOJO: algoritmo de seleção natural; e
  • Quarto exercício computacional: implementação do método de seleção natural.
    

• 15/01/13

  • Segunda etapa da classificação externa: intercalação;
  • Objetivo desta etapa;
  • Problema da etapa de intercalação: como gerar o arquivo final a partir de arquivos de partições;
  • Medida de eficiência: número de passos; e
  • Algoritmos que podem ser usados nesta etapa: intercalação balanceada de N caminhos e intercalação ótima.
    

• 17/01/13

  • DOJO: algoritmo de intercalação ótima; e
  • Quinto exercício computacional: implementação do método de intercalação ótima.
    

• 22/01/13

  • Revisão de arquivo de acesso direto;
  • 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 uniforme e produzir um número baixo de colisões;
  • Exemplos de funções de hash: divisão, dobra e multiplicação;
  • Fator de carga;
  • Tratamento de colisão por meio do uso de listas lineares; e
  • Definição das operações inicializa e insere com este tipo de tratamento de colisão.
    

• 24/01/13

  • Definição das operações busca, libera e retira com tratamento de colisão por meio do uso de listas lineares;
  • Tratamento de colisão por meio do uso da primeira posição livre; e
  • Implementação das operações inicializa, insere, busca, libera e retira com este tratamento de colisão.
  • Definição da data da P₁: 21/02/13.
    

• 29/01/13

  • Tratamento de colisão por meio do uso de dispersão dupla;
  • Definição das operações inicializa, insere, busca, libera e retira com este tratamento de colisão.
  • Definição de hashing em arquivos de acesso direto; e
  • Implementação das operações inicializa e insere.
    

• 31/01/13

  • Implementação das operações de hashing em arquivos de acesso direto: retira e busca; e
  • DOJO: algoritmo de retirada de chaves que não estão sendo usadas neste tipo de arquivo.
    

• 05/02/13

  • 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) AVP e (c) AVL;
  • Motivação para o uso de árvores de múltiplos caminhos;
  • Introdução a árvores B; e
  • Trabalho computacional: implementação de árvore B em memória principal usando registros compostos de nome, matrícula, CR, CH total do curso e CH do curso concluída com sucesso.
    

• 07/02/13

  • Definição de árvores B; e
  • Implementação das operações inicializa, busca, libera e aloca (alocação de um nó da árvore B).
    

• 19/02/13 (revisão da máteria da primeira prova)

• 21/02/13 (primeira prova)

• 26/02/13

  • Implementação da operação de inserção (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.
  • OBS: mudança nas datas das provas
    • P₂: 12/03/13
    • VS: 21/03/13
      
    
    

• 28/02/13

  • Implementação da operação de impressão, bem como dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B.
    

• 05/03/13

  • Variantes de árvore B: B^* e B⁺;
  • Discussão sobre operações em árvores B⁺: busca e insere; e
  • Revisão da nota da primeira prova.
  • OBS: horário da apresentação dos trabalhos
    • G01 (Leonardo e Matheus): 14/03 de 11 às 12:00h
    • G11 (Breno): 14/03 de 12 às 13:00h
    • G06 (Felipe e Luiz Felipe Aires): 14/03 de 16 às 17:00h
    • G08 (Carlos e Lucas Vaccari): 14/03 de 17 às 18:00h
    • G02 (Igor, Leandro e Victor): 15/03 de 10 às 11:00h
    • G03 (Alexandre, Ian e Larissa): 15/03 de 11 às 12:00h
    • G09 (Marcelo Agostinho e Vinicius): 15/03 de 12 às 13:00h
    • G04 (Augusto, Fernando e Luana): 18/03 de 11 às 12:00h
    • G10 (Barbara, Gisele e Pedro): 18/03 de 13 às 14:00h
    • G07 (Lucas Paim e Marcelo Costa): 18/03 de 14 às 15:00h
    • G05 (Thadeu): 18/03 de 15 às 16:00h
      
    
    

• 07/03/13

  • Discussão da operação de retirada em árvores B⁺;
  • Arquivos indexados por chaves secundárias: arquivos com lista e arquivos invertidos.
    

• 12/03/13 (segunda prova)

• 14/03/13 (correção dos trabalhos computacionais)

• 15/03/13 (correção dos trabalhos computacionais)

• 18/03/13 (correção dos trabalhos computacionais)

• 19/03/13 (revisão da nota da segunda prova)

• 21/03/13 (VS)