Estruturas de Dados II (TCC-00.215)

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

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, Manole Ltda.
• 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.
• 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

• Carlos: segundas de 10:00 às 12:00h, e terças, quartas e quintas de 9:00 às 11:00h.

Aulas ministradas

• 23/04/13

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

• 25/04/13

  • Revisão da linguagem C:
    • Tipos: básicos da linguagem e definidos pelo usuário (listas);
    • Variáveis: globais, locais e dinâmicas;
    • Pilha de execução: análise detalhada da execução de um programa;
    • Variáveis do tipo ponteiro; e
    • Exemplos: funções básicas de listas simplesmente encadeadas e programa que ordena vetores usando o método de ordenação quicksort já definido na linguagem (qsort).
      
    
    

• 30/04/13

  • 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
    • fread e fwrite para leitura e escrita de informações em arquivos binários, respectivamente.
    
    

• 02/05/13

  • Outras funções para manipulação de arquivos em C:
    • fscanf, fgetc e fgets para leitura de informações em arquivos de texto;
    • fprintf, fputc e fputs para escrita de informações em arquivos de texto;
    • 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.
    

• 07/05/13

  • Algoritmos já conhecidos na literatura e implementados em arquivos:
    • ordenação por inserção; e
    • ordenação usando o quicksort.
    
    

• 09/05/13

  • ordenação usando o quicksort para arquivos;
  • DOJO: ordenação em arquivos usando bolha.
  • Primeiro exercício computacional: bolha implementado para arquivos.
    

• 14/05/13

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

• 16/05/13

  • Implementação do algoritmo balance line; e
  • Segundo exercício computacional: balance line usando registros compostos de matrícula, CR, porcentagem de curso concluída, ano de ingresso, nome e e-mail.
  • OBS: Datas das provas
    • primeira prova: 27/06/13
    • segunda prova: 08/08/13
    • VS: 15/08/13
      

• 21/05/13

  • Revisão de heaps;
  • Intercalação de arquivos sequenciais ordenados: cenário de uso;
  • Algoritmo básico: O(n) na busca pela menor chave; e
  • Otimização do algoritmo básico - uso de árvores binárias de vencedores: O(log n) na busca pela menor chave.

• 23/05/13

  • Funcionamento do algoritmo que utiliza árvores binárias de vencedores; e
  • Terceiro exercício computacional: otimizar o algoritmo de árvore binária de vencedores, contendo somente nós ligados diretamente a arquivos.
    

• 28/05/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 e seleção com substituição.
    

• 04/06/13

  • Funcionamento do algoritmo de seleção com substituição.
    

• 06/06/13

  • Ideia do algoritmo de seleção natural;
  • Funcionamento do algoritmo: arquivo original e as cinco partiçãoes geradas (P₁, P₂, P₃, P₄ e P₅); e
  • Quarto exercício computacional: modificação de duas partes do método de seleção natural: (a) o reservatório deve estar em memória secundária e (b) a possibilidade do tamanho do reservário ser maior que a memória principal.
    

• 11/06/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;
  • Algoritmos que podem ser usados nesta etapa: intercalação balanceada de N caminhos e intercalação ótima; e
  • Revisão de arquivo de acesso direto.
    

• 13/06/13

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

• 18/06/13

  • Tratamento de colisão por meio do uso de listas lineares;
  • Definição das operações inicializa, insere, busca, libera e retira com este tipo de tratamento de colisão;
  • Definição de hash em arquivos de acesso direto; e
  • Ideia da implementação das operações básicas.
    

• 20/06/13 (aula de exercícios no LCC)

  • Biblioteca que será usada para o desenvolvimento dos exercícios.
    

• 25/06/13 (revisão da máteria da primeira prova)

• 27/06/13 (primeira prova - sala 230 do bloco D da Engenharia)

• 02/07/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
  • Definição de árvores B.

• 04/07/13

  • Trabalho Computacional: sistema gerenciador de matrículas de discentes de um curso de graduação hipotético usando árvore B⁺.
    • grupo de no mínimo dois e de no máximo três discentes;
    • semana de entrega: de 05/08/13 a 07/08/13; e
    • arquivo de teste contendo matrícula, carga horária cursada com sucesso, número de semestres cursados e nome do discente.
      
    
    

• 09/07/13

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

• 11/07/13

  • Revisão da nota da primeira prova.
    

• 16/07/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.
  • Ordem de apresentação do trabalho computacional:
    • 05/08/13 de 11:00 às 12:00h - G6 (Alessandro, Lucas e Vinícius)
    • 05/08/13 de 13:00 às 14:00h - G5 (Artur, Paulo e Tomás)
    • 05/08/13 de 15:00 às 16:00h - G3 (Bárbara, Guilherme e Rafael)
    • 06/08/13 de 14:00 às 15:00h - G1 (Gabriel, Gustavo e Roberto)
    • 06/08/13 de 15:00 às 16:00h - G7 (Carlos)
    • 07/08/13 de 11:00 às 12:00h - G4 (Alexandre, Julius e Victor)
    • 07/08/13 de 13:00 às 14:00h - G2 (Anna, Daniel e Ian)
      
    
    

• 18/07/13

  • Explicação dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B.
    

• 23/07/13

  • Exemplo de execução das funções de árvores B, incluindo a remoção.
    

• 25/07/13 (não houve aula)

• 29/07/13

  • Arquivos indexados por chaves secundárias: arquivos com lista, arquivos invertidos e arquivos multilista (apresentação dos seis passos do Algoritmo de Lefkowitz).
    

• 01/08/13

  • Discussão sobre operações em árvores B⁺: busca, insere e retira.
    

• 05/08/13 (apresentação do trabalho computacional)

• 06/08/13 (apresentação do trabalho computacional)

• 07/08/13 (apresentação do trabalho computacional)

• 08/08/13 (segunda prova)

• 12/08/13 (revisão da nota da segunda prova das 14:00 às 16:00h)

• 15/08/13 (VS - das 11:00 às 14:00h - na sala 505 da UFASA)

  • Notas finais; e
  • Revisão da nota da VS: 19/08/13 das 11:00h às 12:00h.