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 217

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

• 13/08/2019

  • Apresentação do curso: objetivos, tópicos a serem apresentados e critério de avaliação a ser empregado;
  • Implementação de listas simplesmente encadeadas 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) inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação e (c) inserção de um elemento x na k-ésima posição. Se não existem k elementos nessa lista, então realiza-se a inserção de x várias vezes, até que ela passe a ter k elementos.
  • Datas importantes:
    • P1: 10/10/2019
    • P2: 03/12/2019
    • VR: 05/12/2019
    • VS: 17/12/2019
    • Entrega de todas as notas da disciplina (antes da VS): 12/12/2019

• 15/08/2019

  • Versões (iterativa e recursiva) de algumas operações de listas simplesmente encadeadas de inteiros: (a) impressão nas ordens direta e inversa, (b) ordenação de uma lista, (c) retirada da primeira ocorrência de um elemento na lista, (d) retirada de todas as ocorrências de um elemento na lista, e (e) retirada do elemento da k-ésima posição.
  • Exercício de revisão: implemente o tipo abstrato de dados lista simplesmente encadeada genérica, usando void *.

• 20/08/2019

  • Ordenação de vetores usando QuickSort;
  • Procedimento geral qsort existente na biblioteca stdlib.h;
  • Exemplo da função de comparação de int, usada em qsort;
  • Motivação para o uso de árvores e de árvores binárias;
  • Implementação de árvores binárias; e
  • Operações: (a) inicialização, (b) libera árvore, (c) contagem de nós e folhas de árvores binárias, e (d) descoberta do menor elemento.

• 22/08/2019

  • Operações básicas: (a) 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 (b) busca um elemento na árvore;
  • 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);
  • 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): busca e inserção de um elemento; e
  • Exercícios.

• 27/08/2019

  • Retirada de um elemento de uma árvore binária de busca;
  • Exemplo de uso das operações supracitadas: dados um vetor ordenado e seu tamanho, gere uma árvore binária de busca com o mesmo número de filhos nas sub-árvores esquerda e direita, usando a operação de criação;
  • Motivação para o uso de árvore binária de busca AVL;
  • Implementação da função de altura de uma árvore binária; e
  • Definição de árvore binária de busca AVL, com exemplos desse tipo de árvore.

• 29/08/2019

  • 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;
  • 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;
  • Uma versão do código que implementa a AVL; e
  • Exercícios.

• 03/09/2019

  • Resolução de exercício: retirada dos pares de uma árvore binária de busca;
  • Grafos: apresentação de conceitos;
  • Algumas definições a respeito de grafos;
  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) busca de nós e de arestas do grafo, (c) impressão, e (d) liberação da estrutura.

• 05/09/2019

  • Correção do exercício: retirada dos pares de uma árvore binária de busca;
  • Mais operações em grafos: inserção e retirada de nós e de arestas do grafo;
  • Exemplo de aplicação de grafos: testar se dois grafos são iguais; e
  • Exercícios.

• 10/09/2019 (aula no Laboratório 306)

  • Pacote de bibliotecas usadas para a resolução dos seguintes exercícios:
    • Copiar uma árvore binária - TAB* copia(TAB *a);
    • Espelhar uma árvore binária - TAB* espelho(TAB *a);
    • Versões iterativa, usando filas, e recursiva de coloração de árvores binárias balanceadas - void colore(TAB *a); e
    • Retornar o maior elemento da árvore binária - TAB* maior(TAB *a).
    • testar se uma árvore é zigue-zague, isto é, todos os nós internos possuem exatamente uma sub-árvore vazia - int zz(TAB *a);
    • retornar todos os ancestrais de um nó na árvore de busca binária, da raiz da árvore até o elemento passado como parâmetro, usando a biblioteca de lista encadeada - TLSE* ancestrais(TABB *a, int elem);
    • verificar se uma árvore é estritamente binária, isto é, os nós dessa árvore possuem ou zero ou dois filhos - int estbin(TAB *a);
    • testar se duas árvores possuem os mesmos nós - int mn(TAB *a1, TAB *a2);
    • 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);
    • testar se o grafo, passado como parâmetro de entrada, é completo - int completo(TG *g); e
    • fazer o exercício do Instagram, gentilmente cedido pela Professora Vanessa Braganholo.

• 12/09/2019

  • Definição de arquivos;
  • 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; e
    • fscanf e fprintf para leitura e escrita de informações em arquivos texto, respectivamente.

• 17/09/2019

  • Exemplos de uso das funções: merge de dois arquivos texto ordenados, gerando um terceiro também ordenado sem elementos repetidos e função que indica quantas vezes uma string aparece num arquivo texto;
  • Funções para manipulação de arquivos binários em C (biblioteca stdio.h):
    • fread e fwrite para leitura e escrita de informações, 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: criação de arquivos binários e busca binária; e
  • Exercício: reescreva o algoritmo de busca binária desenvolvido nesta aula, de modo que ele suporte quaisquer tipos de dados.

• 19/09/2019

  • Ordenação em arquivos binários: uso dos métodos já conhecidos da literatura;
  • Desenvolvimento do método da bolha em sala de aula;
  • Ordenação em arquivos texto:
    • Suposição: arquivo texto original não cabe em memória principal;
    • 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;
    • Ideia do algoritmo de classificação interna;
    • Desenvolvimento da primeira versão do algoritmo de classificação interna; e
    • Ideia do algoritmo de seleção com substituição.

• 24/09/2019

  • Ideia do algoritmo de seleção natural;
  • Segunda etapa da classificação externa: intercalação das partições geradas;
  • 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;
  • Desenvolvimento do algoritmo básico de intercalação;
  • Otimização do algoritmo básico de intercalação - uso de árvores binárias de vencedores: O(log n) na busca pela menor chave; e
  • Ideia do algoritmo de árvores binárias de vencedores;

• 26/09/2019

  • Códigos: busca binária, e ordenações por seleção e usando QuickSort;
  • Pacote de algoritmos de classificação externa; e
  • 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.

• 01/10/2019

  • Problema da etapa de intercalação: geração do arquivo final a partir de n arquivos de partições, com a limitação de um sistema operacional manter um número finito de arquivos abertos menor que n;
  • Medida de eficiência: número de passos;
  • Ideia do algoritmo de intercalação ótima;
  • Introdução a árvores B;
  • Definição de árvores B;
  • Implementação da estrutura de árvore B e das seguintes operações: (a) inicialização, (b) criação de nó de árvore B e (c) impressão desse tipo de árvore; e
  • Exercícios:
    • faça o algoritmo de árvores binárias de vencedores usando a estrutura de árvore binária; e
    • considerando um dos algoritmos de geração de partições classificadas e o de árvores binárias de vencedores (o último dsenvolvido no exercício supracitado), implemente a intercalação ótima, com a limitação de um sistema operacional hipotético manter somente quatro arquivos abertos simultaneamente.

• 03/10/2019

  • Implementação das operações de busca de um elemento e de liberação de árvores B;
  • Exemplo: encontrar o sucessor de um elemento em uma árvore B; e
  • Início do desenvolvimento da operação de inserção.

• 08/10/2019 (aula no Laboratório 306)

  • Exercícios sobre árvores feitos em laboratório: (a) retirada de todos os ímpares de uma árvore binária de busca e (b) coloração de uma árvore binária balanceada; e
  • 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).

• 10/10/2019 (primeira prova)

• 17/10/2019

  • 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, ilustrando-a com exemplos; e
  • Enunciado do trabalho computacional.

• 22/10/2019 (não houve aula devido à Semana Acadêmica)

• 24/10/2019 (não houve aula devido à Semana Acadêmica)

• 29/10/2019 (revisão da nota da primeira prova, com disponibilização do gabarito usado)

• 31/10/2019

  • Discussão do trabalho computacional;
  • 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
  • Código da árvore B.

• 05/11/2019

  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Definição das operações iguais a da árvore B: inicialização, impressão e liberação;
  • Discussão de algumas operações em árvores B⁺:
    • Criação de um nó vazio de B⁺;
    • Busca de um nó de B⁺ que contenha a informação passada como parâmetro de entrada;
    • Tratamento das 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.

• 07/11/2019

  • Soluções encontradas para lidar com os casos 3A e 3B da operação de retirada de árvores B⁺, 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;
  • Código da árvore B⁺, com exceção da operação de retirada;
  • Exercício: considerando a implementação supracitada, desenvolva 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 das funções de hash: ser facilmente computável, ser determinística, seguir a distribuição uniforme e produzir um número baixo de colisões;
  • Exemplo de função de hash - método da divisão; e
  • Tipos de tratamento de colisões: (a) por endereçamento aberto, (b) por encadeamento externo e (c) por encadeamento interno.

• 12/11/2019

  • 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; e
  • Definição das operações para o tratamento de colisão usando endereçamento aberto (e considerando tentativa linear): (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera; e
  • Ordem de apresentação dos trabalhos:
    • 28/11 às 09:00h - G08 (GERALDO FADA DE OLIVEIRA NETO e RODRIGO GONCALVES CORREA)
    • 28/11 às 10:00h - G17 (JOAO VITOR BRANQUINHO RIBEIRO e MICHEL LESSA ZIADE)
    • 28/11 às 14:00h - G12 (AUGUSTO DE SOUZA VILARINHO PEREIRA, ISAAC DE SOUZA MORAES DA SILVA e JUAN MULLER PEREIRA EVANGELISTA)
    • 28/11 às 15:00h - G06 (BARBARA KEREN NASCIMENTO CARVALHO GUARINO, CAMILLE ARAUJO DE SOUZA e FABIO DA SILVA CORREA DE PAULO)
    • 28/11 às 16:00h - G14 (FELIPE RESAFFI TAVARES, PEDRO HENRIQUE DOS SANTOS RIBEIRO e WILLIAN RODRIGUES BENEVIDES E SILVA)
    • 28/11 às 18:00h - G02 (JONATAS PEREIRA DE ALCANTARA ALVES e PEDRO IGOR VERISSIMO DO NASCIMENTO)
    • 29/11 às 10:30h - G01 (JONATHAN MEIRELLES SOUZA, MARIA CLARA MUSSI DA SILVA e SAMIRY RODRIGUES DE MATTOS)
    • 29/11 às 11:00h - G03 (GUSTAVO LUPPI SILOTO e LEONARDO COREIXAS BIASOTTO MIRAPALHETE)
    • 29/11 às 12:00h - G04 (GYSELLE REGINA GONCALVES DE MELLO, IGOR CRUZ FIGUEIREDO e NIASI MARQUES DE ANDRADE LUCIO MAGALHAES)
    • 29/11 às 14:00h - G11 (ANDREAS GOMES MUZZI, ARTUR GONCALVES MELO e JOHANN ANDRADE DAFLON)
    • 29/11 às 15:00h - G05 (ANTONIO ROMANO CARVALHO FERREIRA, THIAGO LAET OLIVEIRA BERTO e YAKSON MENECHINI CHAN)
    • 02/12 às 11:00h - G10 (FERNANDO DO NASCIMENTO VIEIRA, HENRIQUE YAN DE SETA COUTINHO e MARCOS FREDERICO RAPOSO HAYMAN)
    • 02/12 às 13:00h - G13 (FELIPE NOBREGA VIANNA BATISTA e PEDRO IVO TERRA BANDOLI)
    • 02/12 às 15:00h - G15 (GUILHERME FREITAS FRANCA, HENRIQUE BARREIRA PACHE DE FARIA e PEDRO TRINKENREICH HENRIQUE)
    • 02/12 às 16:00h - G07 (FELIPE DE ANDRADE ESSER, PEDRO HENRIQUE LUIZ BAZILIO e VICTOR BRANDAO)
    • 02/12 às 17:00h - G16 (ERIKY NUNES MARCIANO e KAYALLA PONTES LINO)
    • 03/12 às 10:00h - G09 (LEANDRO JOSINO CARVALHO, LUCAS FAUSTER LEITE PEREIRA e PAULO AUGUSTO DE MOURA FERREIRA)

• 14/11/2019

  • Tratamento de colisão usando encadeamento externo para a memória principal;
  • 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;
  • Discussão sobre o tratamento de colisão por encadeamento externo em memória secundária; e
  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória secundária: (a) inicializa e (b) busca.

• 19/11/2019

  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória secundária: (a) retira e (b) insere;
  • Ideia do tratamento de colisão usando encadeamento interno para as memórias principal e secundária; e
  • Exercício: desenvolver as operações básicas - inicializa, insere, busca e retira - para o tratamento de colisão por encadeamento interno em memórias principal (usando tentativa linear) e secundária. Este último tipo de tratamento é semelhante ao tratamento de colisões baseado em encadeamento externo para o mesmo tipo de memória, juntando, num único arquivo, as informações de hash e de dados.

• 26/11/2019

  • 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 binários de máximo em memória principal:
    • int pai (int indice);
    • int esquerda (int indice);
    • int direita (int indice); e
    • void max_heapfy (int* heap, int n, int indice).
  • Exercícios sobre as seguintes estruturas de dados:
    1. Árvores B e B⁺:
       • cópia de uma árvore: TAB* copia (TAB *a);
       • sucessor de um elemento na árvore. Se o elemento for o maior da estrutura, sua função deve retornar INT_MAX: int suc (TAB *a, int elem);
       • maior elemento da árvore: TAB* maior(TAB *a);
       • menor elemento da árvore: TAB* menor(TAB *a);
       • função que, dadas duas árvores deste tipo, testa se estas árvores são iguais. A função retorna um se elas são iguais e zero, caso contrário. A função deve obedecer ao seguinte protótipo: int igual (TAB* a1, TAB* a2);
       • função em C que, dada uma árvore qualquer, retire todos os elementos pares da árvore original. A função deve ter o seguinte protótipo: TAB* retira_pares (TAB* arv);
       • quantidade de nós internos: int ni(TAB *a);
       • quantidade de nós folha: int nf(TAB *a);
    2. Tabelas hash:
       • escreva uma operação de limpeza, em memória secundária, usando tratamento de colisão baseado em encadeamento externo: void limpeza(char *hash, char *dados, char *novodados, int N);
       • implemente um procedimento que, dados uma tabela hash, uma matrícula e um cr, retire dessa tabela todos os dados com a mesma colisão da matrícula passada como parâmetro de entrada, e que tenham cr menor ou igual ao cr supracitado: void f(char *hash, char *dados, int N, int mat, float cr);
    3. Heaps: generalize as operações de heaps binários de máximo para heaps ternários de mínimo - int filho (int indice, int pos), onde pos ∈ {1,2,3}, int pai (int indice) e void min_heapfy (int* heap, int n, int indice), onde os métodos esquerda e direita são as operações filho (pos, 1) e filho(pos, 2), respectivamente.

• 28/11/2019

  • Implementação das demais operações de heaps binários de máximo em memória principal:
    • void build_maxheap (int* heap, int n); e
    • void heapsort (int* heap, int n).
  • Dúvidas para a segunda prova.

• 03/12/2019 (segunda prova)

  • Remarcação das apresentações dos trabalhos para dia 05/12:
    • G10 - 10:30h;
    • G01 - 11:00h;
    • G03 - 12:00h;
    • G05 - 13:00h;
    • G04 - 14:00h;
    • G13 - 15:00h;
    • G16 - 16:00h; e
    • G11 - 18:00h.

• 05/12/2019 (VR)

• 12/12/2019 (aula do Laboratório 306: revisão de nota da segunda prova e da VR, e divulgação de todas as notas da disciplina)

• 17/12/2019 (VS)

• 19/12/2019 (aula do Laboratório 306: revisão de nota da VS e publicação das notas finais)