Estruturas de Dados II (TCC-00.215)

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

Tópicos Abordados

• 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 (henriquezplay@hotmail.com): segundas e quartas de 8:00 às 11:00h, e terças e quintas de 8:00 às 9:00h.

Aulas ministradas

• 10/09/13

  • Apresentação do curso: tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
  • Revisão da linguagem C:
    • Tipos: básicos da linguagem;
    • Variáveis: globais, locais e dinâmicas;
    • Pilha de execução: análise detalhada da execução de um programa; e
    • Variáveis do tipo ponteiro.
      
  • Definição de arquivo, stream e buffer; e
  • Tipos de arquivos: binários e de texto.
  • Datas das provas:
    • P1: 14/11/13
    • P2: 17/12/13
    • VS: 14/01/13
    
    

• 12/09/13

  • Funções para manipulação de arquivos em C:
    • 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;
    • 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;
    • ftell para obter a posição corrente do arquivo; e
    • fread e fwrite para leitura e escrita de informações em arquivos binários, respectivamente.
  • Algoritmos já conhecidos na literatura e implementados em arquivos: busca binária.
    

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

• 19/09/13 (não houve aula)

• 24/09/13

  • Algoritmos já conhecidos na literatura e implementados em arquivos:
    • busca binária; e
    • ordenação por seleção.
    
    

• 26/09/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;
  • ordenação usando o quicksort para arquivos;
  • Primeiro exercício computacional: heapsort implementado para arquivos.
    

• 01/10/13

  • Atualização em lote: cenário de uso;
  • Arquivos ordenados por chave primária: mestre e de transações; e
  • Funcionamento e implementação do algoritmo balance line (arquivos mestre e de transações).
  • Segundo exercício computacional: balance line usando registros de contas compostos de tipo da conta, código da conta, saldo e data do último depósito. Devem ser implementadas restrições nas operações de inclusão (contas poupanças e de investimentos não podem ser criadas com saldos negativos) e de modificação (contas poupanças e de investimentos não podem negativar seus saldos, e contas de investimento só podem ser modificadas 30 dias após a última operação de manipulação de saldo).
    

• 03/10/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 de listas lineares; e
  • Definição das operações inicializa, insere, busca, libera e retira com este tipo de tratamento de colisão.
    

• 08/10/13

  • Definição de hash em arquivos de acesso direto; e
  • Ideia da implementação das operações básicas.
    

• 10/10/13

  • Implementação das operações básicas de hash em arquivos de acesso direto.
  • Terceiro exercício computacional: implementar hash em arquivos de acesso direto cujos registros são compostos de matrícula (chave primária), carga horária cursada com sucesso, número de semestres cursados, CR e ano de ingresso.
    

• 17/10/13

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

• 29/10/13

  • Funcionamento do algoritmo que utiliza árvores binárias de vencedores;
  • Motivação para classificação (ou ordenação);
  • 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.
    

• 31/10/13

  • Funcionamento do algoritmo de seleção com substituição: algoritmo e arquivo de teste; e
  • Ideia do algoritmo de seleção natural.
    

• 05/11/13

  • Funcionamento do algoritmo de seleção natural;
  • Quarto exercício computacional: modificação do método de seleção natural, implementando o reservatório em memória secundária;
  • 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.
    

• 07/11/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;
  • Definição de árvores B; e
  • Implementação das funções cria nó de árvore B e inicializa.

• 12/11/13

  • Revisão da matéria da P1; e
  • Implementação de algumas operações de árvores B: busca e libera.
  • Trabalho computacional: árvore B em arquivos
    • grupo de no mínimo dois e de no máximo três discentes; e
    • semana de entrega: de 07/01/14 a 09/01/14.
      
    
    

• 14/11/13 (primeira prova)

• 19/11/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.
    

• 21/11/13

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

• 26/11/13

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

• 28/11/13

  • Exercícios de árvores B.
    

• 03/12/13 (revisão da nota da primeira prova)

• 05/12/13

  • 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/12/13

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

• 12/12/13 (aula de dúvidas para a segunda prova)

• 17/12/13 (segunda prova na sala 102H (UFASA))

• 19/12/13 (divulgação do calendário de apresentações de todos os trabalhos)

  • 20/12/13 (sex) de 14:00h às 15:00h → G00 (Bruno Nascimento, Gustavo Tallarida e João Rudá)
  • 07/01/14 (ter) de 11:00h às 12:00h → G03 (Gabriel e Raissa)
  • 07/01/14 (ter) de 12:00h às 13:00h → G01 (Ana, Bernardo e Victor)
  • 07/01/14 (ter) de 16:00h às 17:00h → G10 (Carlos e Ramayan)
  • 08/01/14 (qua) de 11:00h às 12:00h → G04 (Daniel Pinheiro, Diego e Renan)
  • 08/01/14 (qua) de 12:00h às 13:00h → G07 (Arthur, Gustavo e Leandro)
  • 08/01/14 (qua) de 16:00h às 17:00h → G06 (Bruno, Guilherme e Matheus)
  • 08/01/14 (qua) de 17:00h às 18:00h → G12 (Daniel e Lucas Stuart)
  • 09/01/14 (qui) de 09:00h às 10:00h → G08 (Claudio, João Lucas e Thiago)
  • 09/01/14 (qui) de 10:00h às 11:00h → G02 (Filipe, Hugo e Tadeu)
  • 09/01/14 (qui) de 11:00h às 12:00h → G09 (Carlos Alberto e Vinicius)
  • 09/01/14 (qui) de 14:00h às 15:00h → G11 (Beatriz e Tayane)
  • 09/01/14 (qui) de 15:00h às 16:00h → G05 (Jefferson e Taiane)
    

• 07/01/14 (revisão da nota da segunda prova)

• 14/01/14 (VS)

  • Notas finais.