Estruturas de Dados e seus Algoritmos (TCC-00.348)

horários das aulas: terças e quintas de 11:00 às 13:00h na sala 202

Objetivos

Tópicos Abordados

• Árvores binárias, binárias de busca e AVL;
• Grafos;
• Arquivos;
• Ordenação externa de arquivos binários e texto (para o último tipo de arquivo, a ordenação é dividida em duas etapas: geração de partições classificadas e intercalação de partições);
• Árvores B e B⁺;
• Tabelas hash (ou de dispersão) mantidas em memórias principal e secundária; e
• Listas de prioridade (ou heaps) mantidas em memórias principal e secundária.

Critério de avaliação

Bibliografia básica

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

Bibliografia complementar

• A.M. Tenenbaum, Y. Langsam e M.J. Augenstein, Estruturas de Dados Usando C, Pearson, Primeira Edição, 1995.
• R. Ramakrishnan, Database Management Systems, McGraw Hill, Third Edition, 2003.

Aulas ministradas

• 14/08/2018

  • Apresentação do curso: objetivos, tópicos a serem apresentados e critério de avaliação a ser empregado.
  • Datas importantes:
    • P1: 09/10/2018
    • P2: 06/12/2018
    • VR: 11/12/2018
    • VS: 18/12/2018
    • Entrega de todas as notas da disciplina (antes da VS): 13/12/2018

• 16/08/2018

  • Assuntos da aula de revisão:
    • definição de lista simplesmente encadeada de inteiros;
    • operações básicas desse tipo: (a) inicialização e (b) inserção de um elemento no início da lista; e
    • versões (iterativa e recursiva) de algumas operações básicas desse tipo: (a) inserção de um elemento no fim da lista, (b) busca de um elemento, (c) impressão de uma lista (ordens direta e inversa), e (d) inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação.

• 21/08/2018

  • versões (iterativa e recursiva) das demais operações básicas da lista simplesmente encadeada de inteiros: (a) retirada da primeira ocorrência de um elemento em uma lista, (b) liberação da lista e (c) ordenação de uma lista, cujo o cabeçalho é void ordena (TLSE *l);
  • Motivação para o uso de árvores e árvores binárias;
  • Implementação de árvores binárias;
  • Operações básicas: (a) inicialização e (b) criação de uma árvore, a partir dos seguintes parâmetros de entrada: a informação do nó raiz e as sub-árvores esquerda e direita; e
  • Exercício: dados um vetor ordenado e seu tamanho, gere uma árvore binária com o mesmo número de filhos nas sub-árvores esquerda e direita, usando as operações supracitadas.

• 23/08/2018

  • Implementação de árvores binárias;
  • Percurso em árvores binárias: pré-ordem (ou profundidade), simétrica, pós-ordem e largura;
  • Operações básicas mostrando as diversas formas de impressão: profundidade (versões recursiva e iterativa, por meio do uso de uma implementação específica de pilha), simétrica (versão recursiva), pós-ordem (versão recursiva) e largura (versão iterativa usando uma implementação específica de fila);
  • Outras operações sobre árvores binárias desenvolvidas em sala: (a) libera todos os nós, (b) busca um elemento na árvore e (c) calcula a altura de uma árvore binária; e
  • Exercícios.

• 28/08/2018

  • Motivação para o uso de árvores binárias de busca (ABB);
  • Implementação de árvores binárias de busca;
  • Operações básicas (que diferem de árvore binária original): retira, busca e inserção de um elemento.
  • Exercícios.

• 30/08/2018

  • Motivação para o uso de árvores binárias AVL;
  • Definição de árvores binárias AVL; e
  • Operações básicas: (a) rotação simples a esquerda - RSE, (b) rotação simples a direita - RSD, (c) rotação dupla esquerda-direita - RED e (d) rotação dupla direita-esquerda - RDE.

• 04/09/2018

  • Ilustração do código de inserção em AVL;
  • Apresentação, por meio de exemplos, das operações de inserção e retirada em AVL, utilizando, quando necessário, as operações de rotação supracitadas;
  • Código da árvore binária de busca AVL;
  • Grafos: apresentação de conceitos;
  • Representação de grafos por meio de listas encadeadas;
  • Operações em grafos: (a) inicialização e (b) busca, realizada em nós e arestas do grafo; e
  • Exercícios.

• 06/09/2018

  • Exercício feito em sala: retirada de todos os pares de uma árvore binária;
  • Operações em grafos: (a) impressão, (b) liberação da estrutura, e (c) inserção e retirada, realizadas em nós e arestas do grafo; e
  • Exercícios.

• 11/09/2018

  • Definição de arquivo e de buffer;
  • Tipos de arquivos: binários e de texto;
  • Funções para manipulação de arquivos em C (biblioteca stdio.h):
    • fopen e fclose para abrir e fechar arquivos, respectivamente;
    • fflush para descarregar o buffer;
    • 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; e
    • ftell para obter a posição corrente do arquivo binário.
  • Exemplos de uso destas funções: geração de arquivos no modo texto e no modo binário, e merge de dois arquivos texto ordenados, gerando um terceiro também ordenado sem elementos repetidos.

• 13/09/2018 (aula no Laboratório 306)

  • Pacote de bibliotecas usadas para a resolução dos exercícios.
  • Exercícios sobre as seguintes estruturas de dados:
    1. grafos:
       • verificar se o grafo, passado como parâmetro de entrada, possui todos os nós com grau igual a k - int testek(TG *g, int k); e
       • testar se dois grafos são iguais - int ig(TG *g1, TG *g2).
    2. árvores binárias:
       • testar se uma árvore é zigue-zague, isto é, todos os nós internos possuem exatamente uma sub-árvore vazia - int zz(TAB *a);
       • verificar se uma árvore é estritamente binária, isto é, os nós dessa árvore possuem ou zero ou dois filhos - int estbin(TAB *a); e
       • testar se duas árvores possuem os mesmos nós - int mn(TAB *a1, TAB *a2).
  • Exercício do Instagram, gentilmente cedido pela Professora Vanessa Braganholo.

• 18/09/2018

  • Implementações de busca binária e ordenação por seleção; e
  • Exercícios: reescreva os algoritmos de ordenação e de busca binária desenvolvidos nesta aula, de modo que eles suportem quaisquer tipos de dados.

• 20/09/2018

  • Códigos: busca binária, ordenações por seleção e usando QuickSort;
  • Motivação para classificação (ou ordenação) externa;
  • Etapas da classificação externa: geração de partições ordenadas e intercalação dessas partições;
  • 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; e
  • Ideia do algoritmo de classificação interna.

• 25/09/2018

  • Ideia do algoritmo de seleção com substituição;
  • Entendimento do algoritmo de seleção natural; e
  • Desenvolvimento da primeira versão do algoritmo de classificação interna.

• 27/09/2018 (aula no Laboratório 306)

  • Exercícios sobre arquivos:
    • escrever o algoritmo de ordenação por bolha - void BolhaBin(char *nomeArq);
    • desenvolver um procedimento que receba o nome de um arquivo texto e retire deste texto palavras consecutivas repetidas. O seu programa deve retornar, no arquivo de saída, informado como parâmetro dessa função, a resposta desta questão. Por exemplo, se o conteúdo de um arquivo texto for: "Isto e um texto texto repetido repetido repetido . Com as repeticoes repeticoes fica fica sem sem sentido . Sem elas elas elas melhora melhora um um pouco .", a saída do seu programa será: "Isto e um texto repetido . Com as repeticoes fica sem sentido . Sem elas melhora um um pouco ." - void RetRepet(char *ArqEnt, char *ArqSaida);
    • implementar um algoritmo que receba como parâmetro de entrada, o nome de um arquivo texto, cujo conteúdo são o nome do aluno e as duas notas dos alunos do curso, uma em cada linha, e que ordene o arquivo de saída em ordem crescente pela média do aluno. Isto é, se eu tiver como entrada o arquivo: "P C/10.0/10.0-J J/3.0/4.0-G G/7.0/7.0-A A/0.5/1.5-I I/5.0/6.0", a saída será: "A A/1.0-J J/3.5-I I/5.5-G G/7.0-P C/10.0" - void media(char *ArqEnt, char *ArqSaida); e
    • escrever um procedimento que receba o nome de um arquivo texto, cujo conteúdo são valores inteiros, e um inteiro N e imprima na tela o número de vezes que N aparece e em quais linhas - void infoN(char *Arq, int N).

• 02/10/2018

  • Pacote de algoritmos de geração de partições classificadas;
  • Exercício: reescreva o algoritmo de seleção natural (com o reservatório implementado em memórias primária e secundária), sendo o reservatório menor que a memória principal;
  • Segunda etapa da classificação externa: intercalação;
  • Objetivo desta etapa;
  • Intercalação de arquivos sequenciais ordenados: cenário de uso considerando o número de partições n menor que o limite de arquivos abertos simultaneamente em um sistema operacional;
  • Algoritmo básico: O(n) na busca pela menor chave; e
  • Ideia do algoritmo básico de intercalação.

• 04/10/2018

  • Otimização do algoritmo básico de intercalação - uso de árvores binárias de vencedores: O(log n) na busca pela menor chave;
  • Ideia do algoritmo de árvores binárias de vencedores;
  • Pacote de algoritmos de intercalação: básico e de árvores binárias de vencedores;
  • Exercícios:
    • reorganize o código original de árvores binárias de vencedores a fim de usar a primeira posição da heap; e
    • refaça o algoritmo de árvores binárias de vencedores usando a estrutura de árvore binária no lugar da implementação prévia de heap.
  • 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 o de árvores binárias de vencedores, implemente a intercalação ótima, com a limitação de um sistema operacional hipotético manter somente quatro arquivos abertos simultaneamente.

• 09/10/2018 (P1 de 11:00 às 13:00h na sala 202)

• 11/10/2018 (não houve aula)

• 16/10/2018 (não houve aula devido a Agenda Acadêmica)

• 18/10/2018 (não houve aula devido a Agenda Acadêmica)

• 23/10/2018

  • Motivação para o uso de árvores de múltiplos caminhos;
  • Introdução a árvores B;
  • Definição de árvores B; e
  • Implementação da estrutura de árvore B e das seguintes operações: (a) inicializa, (b) cria nó de árvore B, (c) busca e (d) libera.

• 25/10/2018

  • Revisão da nota da primeira prova;
  • Implementação da operação de impressão; e
  • Ideia da operação de inserção.

• 30/10/2018

  • 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 necessárias para o funcionamento dessa codificação;
  • Explicação dos casos necessários (1, 2A, 2B, 2C, 3A e 3B) para o desenvolvimento do algoritmo de remoção em árvores B, ilustrando-os com exemplos; e
  • Trabalho computacional - manipulação de árvore B em arquivos por meio do gerenciamento de um catálogo de filmes de um aplicativo de straming de vídeo, como o Netflix → seu programa deve receber como entrada os seguintes parâmetros: o fator de ramificação (t) da árvore B e um catálogo inicial no formato previamente especificado. Além disso, sua implementação deve ser capaz de distinguir entre as informações principais consideradas chaves primárias (nesse caso, o título do filme - string de 81 caracteres, acrescido do ano de lançamento da obra - int) e as informações subordinadas (nome do diretor - string de 51 caracteres, gênero do filme (ficção, terror, romance, etc) - string de 31 caracteres, tempo total de duração do filme, em minutos - int). A árvore B deve ser armazenada em disco. As seguintes operações devem ser implementadas nesse trabalho:
    • inserção e remoção de nós da árvore B;
    • busca das informações subordinadas, dada a chave primária;
    • alteração SOMENTE das informações subordinadas;
    • busca de todos os filmes de um diretor; e
    • retirada de todos os filmes de uma determinada categoria do catálogo.
    Informações importantes:
    • exemplo de formato de arquivo de entrada (que deve ser seguido pelo seu programa);
    • grupo de no mínimo dois e de no máximo três discentes;
    • data limite de entrega: 02/12/2018 às 23:59h; e
    • semana de apresentação: de 03 até 07/12/2018.

• 01/11/2018

  • Execução de um código que implementa árvore B;
  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Discussão de algumas operações em árvores B⁺:
    • Implementação da operação de encontrar, dada a chave, um nó na árvore; e
    • Explicação de como tratar as divisões de nós requeridas na operação de inserção, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas.

• 06/11/2018

  • Código referente a árvore B⁺, com exceção da operação de retirada;
  • Soluções encontradas para tratar os casos 3A e 3B da operação de retirada, quando estão envolvidos somente nós internos (caso idêntico ao da árvore B original), e quando os tipos dos nós são heterogêneos, isto é, nós internos e folhas;
  • Exercício: considerando que só existam as chaves primárias, do tipo int, na implementação suparcitada, implemente a operação de retirada em árvore B⁺;
  • Motivação para o uso de tabelas hash (ou tabelas de dispersão);
  • Definição de tabelas 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; e
  • Exemplo de função de hash - método da divisão.

• 08/11/2018

  • Tipos de tratamento de colisões: (a) por endereçamento aberto, (b) por encadeamento externo e (c) por encadeamento interno;
  • Tentativas de cálculo de novo endereçamento devido as colisões para endereçamento aberto: (a) linear, (b) quadrática e (b) dispersão dupla;
  • Definição das operações (usando tentativa linear): (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera;
  • Tratamento de colisão usando encadeamento externo para a memória principal; e
  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória principal: (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera.

• 13/11/2018

  • Definição dos grupos, dos dias e dos horários das apresentações;
  • Discussão do tratamento de colisão por encadeamento externo em memória secundária;
  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória secundária: (a) inicializa, (b) aloca, (c) busca e (d) retira; e
  • Exercício: desenvolver a operação de inserção para o tratamento de colisão por encadeamento externo em memória secundária.

• 22/11/2018

  • Tratamento de colisão usando encadeamento interno para a memória principal;
  • Definição das operações (usando tentativa linear): inicializa, aloca, libera, insere, busca e retira;
  • Tratamento de colisão usando encadeamento interno para a memória secundária;
  • Ideias das operações em memória secundária; e
  • Exercício: desenvolver as operações básicas para o tratamento de colisão por encadeamento interno em 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/11/2018

  • Implementações de tabelas hash desenvolvidas em sala de aula;
  • Motivação para o uso de listas de prioridades ou heaps binários;
  • Definição das operações de heaps em memória principal:
    • int pai (int indice);
    • int esquerda (int indice);
    • int direita (int indice);
    • void max_heapfy (int* heap, int n, int indice); e
    • void build_maxheap (int* heap, int n).

• 29/11/2018

  • Implementação da operação de heapsort em memória principal;
  • Definição das operações de heaps em memória secundária; e
  • Exercícios.

• 06/12/2018 (P2)

• 11/12/2018 (VR)

• 13/12/2018 (revisão de nota da P2 e da VR, e divulgação de todas as notas da disciplina)

• 18/12/2018 (VS)

• 20/12/2018 (revisão de nota da VS e publicação das notas finais)