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

• 19/03/2019

  • Apresentação do curso: objetivos, tópicos a serem apresentados e critério de avaliação a ser empregado;
  • Implementação de pilhas com listas;
  • Operações básicas: (a) criação, (b) retirada de um elemento do topo da pilha - a operação pop, (c) inserção de um elemento no topo da pilha - a operação push, (d) teste se a pilha está vazia, (e) algumas maneiras de liberação dos elementos da pilha e (f) várias formas de impressão da pilha.
  • Datas importantes:
    • P1: 21/05/2019
    • P2: 04/07/2019
    • VR: 09/07/2019
    • VS: 16/07/2019
    • Entrega de todas as notas da disciplina (antes da VS): 11/07/2019

• 21/03/2019

  • Motivação para o uso de filas;
  • Exemplos de uso: impressão de fila;
  • Implementação de fila com lista simplesmente encadeada;
  • Operações básicas: (a) inicialização da fila, (b) destruição da fila, (c) inserção de um elemento no fim da fila, (d) retirada do início da fila, e (e) teste se a fila está vazia;
  • Revisão de recursão: ordenação de uma lista e inserção de um elemento em uma lista previamente ordenada, mantendo a ordenação; e
  • Exercício de revisão: implemente os tipos abstratos de dados pilha e fila genéricos, usando void *.

• 26/03/2019

  • Motivação para o uso de árvores e de á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;
  • 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); e
  • Exercícios.

• 28/03/2019

  • Outras operações sobre árvores binárias desenvolvidas em sala: (a) libera todos os nós e (b) busca um elemento na árvore;
  • Exemplo de uso das operações supracitadas: 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 a operação de criação;
  • 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.

• 02/04/2019

  • Alguns exemplos desenvolvidos em sala de aula:
    • 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).
  • Ideia da operação básica de retirada de um elemento de uma árvore binária de busca.

• 04/04/2019

  • Retirada de um elemento de uma árvore binária de busca;
  • Implementação da função de altura de uma árvore binária;
  • Motivação para o uso de árvore binária de busca AVL;
  • Definição de árvore binária de busca AVL; e
  • Operações básicas: (a) rotação simples a esquerda - RSE e (b) rotação simples a direita - RSD.

• 09/04/2019 (não houve aula devido às chuvas)

• 11/04/2019

  • Pacote de bibliotecas usadas para a resolução dos seguintes exercícios:
    • 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);
  • Operações básicas: (a) rotação dupla esquerda-direita - RED e (b) 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;
  • Grafos: apresentação de conceitos; e
  • Exercícios.

• 16/04/2019

  • Algumas definições a respeito de grafos;
  • Representação de grafos por meio de listas encadeadas;
  • Operações em grafos: (a) inicialização, (b) busca de nós e de arestas do grafo, (c) impressão, (d) liberação da estrutura, e (e) inserção de nós e de arestas do grafo; e
  • Exercícios.

• 18/04/2019 (não houve aula devido ao feriado de Semana Santa)

• 23/04/2019 (não houve aula devido ao feriado de São Jorge)

• 25/04/2019

  • Retirada de nós em grafos;
  • Código da árvore binária de busca AVL;
  • 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.
  • Exemplo de uso das funções: merge de dois arquivos texto ordenados, gerando um terceiro também ordenado com elementos repetidos.

• 30/04/2019

  • 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 (nos modos binário e texto) ordenados, busca binária e ordenação por seleção em arquivos binários; 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.

• 02/05/2019

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

• 07/05/2019 (aula no Laboratório 306)

  • 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).
       • Exercício do Instagram, gentilmente cedido pela Professora Vanessa Braganholo.
    2. 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).

• 09/05/2019

  • Códigos: busca binária, e ordenações por seleção e usando QuickSort;
  • Pacote de algoritmos de geração de partições classificadas;
  • Dúvidas a respeito de AVL; 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.

• 14/05/2019

  • 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;
  • Ideia 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;
  • Ideia do algoritmo de árvores binárias de vencedores;
  • 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; 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.

• 16/05/2019

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

• 21/05/2019 (primeira prova)

• 23/05/2019

  • Implementação das operações de impressão e de liberação de árvores B; e
  • Início do desenvolvimento da operação de inserção.

• 28/05/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;
  • 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.

• 30/05/2019

  • Execução de códigos que implementam a intercalação de partições classificadas e a árvore B;
  • Exercícios de intercalação de partições classificadas:
    • reorganize o código original de árvores binárias de vencedores a fim de usar a primeira posição da heap;
    • 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; e
    • 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.
  • Motivação para o uso de árvores B⁺;
  • Definição de árvores B⁺;
  • Discussão de algumas operações em árvores B⁺:
    • 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; e
    • Soluções encontradas para lidar com 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; e
  • Código da árvore B⁺, com exceção da operação de retirada; e
  • Exercícios de árvores B e B⁺.
  • Trabalho computacional - manipulação de árvore B⁺ em arquivos por meio do gerenciamento de um catálogo de pizzas → 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 código da pizza - int) e as informações subordinadas (nome da pizza - string de 50 caracteres, nome da categoria - string de 20 caracteres e preço - float). 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 todas as pizzas de uma determinada categoria; e
    • remoção de todas as pizzas de uma determinada categoria.
    Informações importantes:
    • exemplo de arquivo de entrada no modo binário (que deve ser seguido pelo seu programa), bem como da estrutura usada para criá-lo, gentilmente cedida pela Professora Vanessa Braganholo. O uso das funções TPizza *le_pizza(FILE *in); e void imprime_pizza(TPizza *p); podem ser usadas para verificar a leitura correta do arquivo binário. A impressão do arquivo binário deve ser a mesma da descrita aqui;
    • grupo de no mínimo dois e de no máximo três discentes;
    • data limite de entrega: 01/07/2019 às 23:59h; e
    • apresentação dos trabalhos: dias 5, 8 e 9 de julho de 2019.

• 04/06/2019 (revisão da nota da primeira prova)

• 06/06/2019

  • Execução de código referente a árvore B⁺, com exceção da operação de retirada;
  • Exercício: considerando que só existam as chaves primárias, do tipo int, na implementação supracitada, 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 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;
  • 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.

• 11/06/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, (b) aloca e (c) insere.

• 13/06/2019

  • Definição dos grupos, dos dias e dos horários das apresentações;
  • Definição das operações para o tratamento de colisões baseado em encadeamento externo em memória secundária: (a) busca e (b) retira;
  • Ideia do tratamento de colisão usando encadeamento interno para a memória principal; e
  • Ordem de apresentação dos trabalhos:
    • 05/07 às 11:00h - G03 (BARBARA KEREN NASCIMENTO CARVALHO GUARINO e TAMIRES DA HORA DOS SANTOS)
    • 05/07 às 13:00h - G04 (JOAO PEDRO MONTEIRO DE MEDEIROS e VITOR BARDASSON LEITE)
    • 05/07 às 15:00h - G08 (JOAO VICENTE GAIDZINSKI COUTINHO DO NASCIMENTO e RODOLPHO VIANNA SANTORO)
    • 05/07 às 16:00h - G06 (FELIPE DA SILVA SIMOES, PEDRO HENRIQUE TINOCO PAIVA e THOMAS GOUVEIA LOPES)
    • 08/07 às 11:00h - G01 (GABRIEL ARAUJO SANTOS, JHONATAN AZEVEDO GONCALVES e LUCAS AMARAL PINHEIRO DA FONSECA)
    • 08/07 às 13:00h - G05 (GABRIEL DE ALMEIDA GUERREIRO, JOAO PEDRO DE ALMEIDA OLIVEIRA COSTA e PEDRO IVO TERRA BANDOLI)
    • 08/07 às 16:00h - G07 (GUSTAVO MULLER MOREIRA e NICOLE LUTTERBACH SUET)
    • 08/07 às 17:00h - G10 (BEATRIZ GONCALVES MILANEZ TANTOW, EDUARDO CANELLAS DE OLIVEIRA e RAFAEL MASCARENHAS DE OLIVEIRA AMORIM)
    • 09/07 às 9:00h - G02 (JENNIFFER CRYSTINE SOUZA DOS SANTOS, LUISA DIRCE FERREIRA HENRIQUE SILVA e VICTOR FARIA FERNANDES)
    • 09/07 às 10:00h - G14 (KAYALLA PONTES LINO, PEDRO PALERMO MARTINS e YAGO DE REZENDE DOS SANTOS)
    • 09/07 às 14:00h - G09 (GUILHERME FREITAS FRANCA, LUCAS TAVARES SOUSA e PEDRO TRINKENREICH HENRIQUE)
    • 09/07 às 15:00h - G13 (DANIEL MARCONDES BOUGLEUX SODRE e JOSE VICTOR DE PAIVA E SILVA)
    • 09/07 às 16:00h - G11 (ANNA LUIZA CALIXTO BARROS, JOAO PEDRO AZEREDO LOYOLA DE ARAUJO e JUAN PABLO MONTEIRO FERNANDES)
    • 09/07 às 17:00h - G12 (JOEL LEMOS VARELA DE SOUZA, JONATHAN MEIRELLES SOUZA e THIAGO LAET OLIVEIRA BERTO)

• 18/06/2019

  • Discussão do 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, juntando, num único arquivo, as informações de hash e de dados.
    

• 20/06/2019 (não houve aula devido ao feriado de Corpus Christi)

• 25/06/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);
    • void max_heapfy (int* heap, int n, int indice);
    • void build_maxheap (int* heap, int n); e
    • void heapsort (int* heap, int n).

• 27/06/2019

  • Definição das operações de heaps binários em memória secundária; e
  • Implementações de heaps desenvolvidas em sala de aula.

• 02/07/2019 (aula de dúvidas para a segunda prova no laboratório 306)

  • 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), void min_heapfy (int* heap, int n, int indice) e void build_minheap (int* heap, int n)), onde os métodos esquerda e direita são as operações filho (pos, 1) e filho(pos, 2), respectivamente.

• 04/07/2019 (segunda prova)

• 09/07/2019 (VR)

• 11/07/2019 (revisão de nota da segunda prova e da VR, e divulgação de todas as notas da disciplina)

• 16/07/2019 (VS)

• 18/07/2019 (revisão de nota da VS e publicação das notas finais)