Estruturas de Dados e Algoritmos

horários das aulas: quintas de 14:00 às 18:00h na sala 217

Ementa da disciplina

• Introdução: revisão de C, recursividade e complexidade de algoritmos;
• Listas lineares com alocações sequencial e encadeada;
• pilhas e filas com alocações sequencial e encadeada;
• Árvores: árvores binárias e árvores balanceadas;
• Heaps; e
• Tabelas hash.

Critério de avaliação

Literatura básica

• W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus.
• 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.
• B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Campus.

Aulas ministradas

• 14/03/2019

  • Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada;
  • Introdução a linguagem C: tipos e variáveis;
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos;
  • Precedência de operadores;
  • Operadores: binários, ternário e sizeof(tipo);
  • Entrada e saída básicas (scanf e printf);
  • Decisões com if;
  • Repetições com for; e
  • Exercícios.

• 21/03/2019

  • Repetições com while, for e do-while;
  • break e continue;
  • Seleção com switch-case-default;
  • Funções e pilha de execução; e
  • Ponteiros;
  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Exemplo de aplicação: versão iterativa dos algoritmos de ordenação bubble sort e selection sort; e
  • Exercícios.

• 28/03/2019

  • Implementação das versões iterativa e recursiva do algoritmo de ordenação selection sort;
  • Ordenação de vetor usando o algoritmo de ordenação quicksort, e apresentação da função qsort presente em stdlib.h;
  • Alocação dinâmica de vetores usando malloc, realloc e free da biblioteca stdlib.h;
  • Exemplo de aplicação: ordenação dos dados de um vetor, mantendo a ordem do vetor original;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Apresentação de funções da bilioteca string.h: implementação de versões iterativa e recursiva de strcpy e strcmp; e
  • Exercícios.

• 04/04/2019

  • Mais sobre funções recursivas: caso base e caso recursivo;
  • Declaração de matrizes;
  • Alocação dinâmica de matrizes;
  • Passagem de matriz como parâmetro de entrada de funções;
  • Exemplo de aplicação: função que verifica a simetria da matriz recebida como parâmetro de entrada, e retorna ou a matriz transposta, ou a matriz simétrica otimizada em relação à memória;
  • Tipo estrutura;
  • Variáveis do tipo estrutura;
  • Ponteiros para o tipo estrutura;
  • Motivação para o uso de listas;
  • Definição de listas;
  • Operações básicas que só possuem uma versão iterativa: (a) inicialização e (b) inserção de um elemento no início da lista;
  • Operações básicas que possuem versões iterativa e recursiva: (a) inserção de um elemento no fim de uma lista e (b) inserção de um elemento na lista ordenada; e
  • Exercícios.
  • Datas importantes:
    • P1: 16/05/2019
    • P2: 27/06/2019
    • Entrega de todas as notas da disciplina: 04/07/2019

• 11/04/2019

  • Outras operações básicas que possuem versões iterativa e recursiva: (a) impressão da lista, (b) liberação da lista, (c) remoção de um elemento da lista, (d) busca de um elemento e (e) ordenação de lista, alterando o conteúdo do campo info;
  • Motivação para o uso de listas circulares;
  • Definição de listas circulares;
  • Operações básicas: (a) inicialização, (b) busca de um elemento, (c) impressão da lista, (d) liberação da lista, (e) inserção mais barata, em termos de complexidade, de um elemento na lista, (f) inserção mais cara, em termos de complexidade, de um elemento na lista e (g) retirada de uma ocorrência de um elemento nesta lista;
  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas;
  • Operações básicas: (a) inicialização, (b) busca de um elemento, (c) impressão da lista, (d) liberação da lista e (e) inserção de um elemento no início da lista; e
  • Exercícios.

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

• 25/04/2019

  • Retirada de elementos de uma lista duplamente encadeada;
  • Exemplo desenvolvido em sala: retirada de todas as ocorrências de um elemento na lista circular;
  • Motivação para o uso de pilhas;
  • Exemplo de uso: ordenação da própria pilha passada como parâmetro de entrada;
  • Implementação de pilhas com vetores e listas;
  • Operações básicas: (a) inicializaçã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 (e) destruição da pilha;
  • Motivação para o uso de filas;
  • Exercício: implementação de filas com vetores;
  • Implementação de filas com listas;
  • Operações básicas: (a) inicialização, (b) inserção de um elemento no fim da fila, (c) teste se a fila está vazia, (d) retirada de um elemento do ínicio da fila e (e) destruição da fila;
  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Percorrimento em árvores binárias: pré-ordem, pós-ordem, simétrica e largura; e
  • Exercícios.

• 02/05/2019

  • Operações básicas de árvores binárias: (a) inicialização, (b) impressão (pré-ordem, pós-ordem, simétrica e largura), (c) criação de árvores binárias, informando a raiz e as duas sub-árvores, (d) liberação de árvores binárias e (e) busca de uma informação na árvore.
  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca;
  • Operações básicas (além das demais supracitadas): (a) busca, (b) inserção e (c) remoção de um elemento;
  • Exemplo de uso: escrever uma árvore binária de busca balanceada a partir de um vetor ordenado; e
  • Exercícios.

• 09/05/2019

  • Motivação para o uso de árvores AVL e AVP;
  • Definição de árvores binárias AVL;
  • Ideia das operações básicas: rotação a esquerda, rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda, inserção e de remoção de nós em AVL;
  • Exemplos de inserções e retiradas em AVL; e
  • Exercícios.
  • Trabalho Computacional: implementação das funções de árvores genéricas no número de filhos, árvores n-árias, e no tipo de informação armazenada, testando com as seguintes figuras geométricas: círculo, quadrado, retângulo, trapézio e triângulo:
    • deve ser permitido ao usuário do sistema: (a) buscar figuras geométricas, por meio de um código único; (b) imprimir informações relevantes, tanto da árvore, quanto das figuras, incluindo-se sua área; (c) inserir novas figuras; (d) retirar figuras, passando seus descendentes para outro pai; (e) destruir a árvore; e (f) alterar as dimensões de figuras;
    • transformar a árvore genérica numa árvore binária de busca balanceada, baseando-se no código único;
    • converter a árvore genérica numa árvore B, baseando-se no código único;
    • a entrada será fornecida por meio de arquivos texto. O arquivo texto será composto das seguintes informações, separadas por '/': código único, código único do pai (sendo que a raiz tem código do pai igual a zero) e as figuras geométricas, incluindo seu nome;
    • as dimensões das figuras geométricas obedecerão ao seguinte padrão: (a) se a figura for um círculo ou um quadrado, uma única dimensão será informada (ou o raio, ou o lado, respectivamente); (b) se a figura for um triângulo ou um retângulo, as duas dimensões informadas serão a base e a altura; e, por fim, (c) se a figura for um trapézio, três dimensões serão informadas, nessa ordem, base menor, base maior e altura;
    • exemplo de arquivo fornecido. PORÉM, SEU CÓDIGO DEVE FUNCIONAR COM QUALQUER ENTRADA QUE SEGUE O PADRÃO SUPRACITADO;
    • a estrutura deve ser totalmente destruída pelo seu programa antes da execução ser finalizada;
    • grupo de três discentes;
    • data de entrega: até o dia 12/06/2019 às 23:59h; e
    • dias de apresentação: 13/06/2019 e 14/06/2019.

• 16/05/2019 (primeira prova)

• 23/05/2019

  • Motivação para o uso de árvores B;
  • Definição de árvores B;
  • Implementação de algumas funções básicas, incluindo a criação de um nó de árvore B, a busca de um elemento na árvore e a liberação de toda estrutura alocada em cada nó;
  • Ideia da operação de inserção, bem como das operações de divisão e de inserção em um nó não completo usadas no código;
  • 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;
  • Código da árvore B; e
  • Exercícios.

• 30/05/2019

  • Código que mostra o funcionamento da AVL;
  • Exemplos de inserções e retiradas em AVL e árvores B;
  • Discussão a respeito do trabalho computacional;
  • Revisão da nota da primeira prova, com o fornecimento de um gabarito de respostas; e
  • Ordem de apresentação dos trabalhos:
    • 13/06 às 14:00h - G07 (Lauro Victor Ramos Cavadas e Samuel Eduardo da Silva)
    • 13/06 às 15:20h - G06 (Arthur Mariano Rocha de Azevedo Scalercio, Ricardo de Souza Moura e Sergio de Melo Barreto Junior)
    • 13/06 às 16:00h - G14 (Cafer Catarine da Cruz Pinto e Gabriel Reis Carrara)
    • 13/06 às 16:40h - G05 (Felix Oliver Sumari Huayta e Jose Miguel Huaman Cruz)
    • 13/06 às 17:20h - G17 (Marcela Correa Santos Ramos e Wilker de Oliveira Delfino)
    • 13/06 às 18:00h - G13 (Matheus Souza D'Andrea Alves)
    • 13/06 às 18:40h - G16 (Romulo Martins da Silva, Thais Luca Marques de Almeida e Victor Olimpio dos Santos Silva)
    • 14/06 às 10:30h - G04 (Daniel Leonardo Jasbick, Guilherme Henrique Apostolo e Igor Garcia Ballhausen Sampaio)
    • 14/06 às 11:10h - G11 (Bruno Vinicios Cunha de Sa e Sidney Loyola de Sa)
    • 14/06 às 11:50h - G03 (Andre Luiz Dias Montevecchi, Anselmo Luiz Eden Battisti e Flavio Miranda de Farias)
    • 14/06 às 13:30h - G18 (Bruno Erbisti Garcia e Daniel Prett Campagna)
    • 14/06 às 14:10h - G01 (Eduardo de Oliveira Andrade, Leonardo Pio Vasconcelos e Raissa dos Santos Barcellos)
    • 14/06 às 14:50h - G02 (Christian Willian Siqueira Pires, Magaywer Moreira de Paiva e Rodolfo Ribeiro Oliveira Neto)
    • 14/06 às 15:30h - G10 (Andre de Souza Andrade, Bruno Alves Hilario e Elbe Alves Miranda)
    • 14/06 às 16:10h - G09 (Luigy Alex Machaca Arcana e Roger Dante Ripas Mamani)
    • 14/06 às 16:50h - G15 (Jane Vieira Volotao)
    • 14/06 às 17:30h - G12 (Daniel Arena Toledo e Erick Simas Grilo)

• 06/06/2019

  • 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;
  • Exemplo de tratamento de colisões em tabelas hash armazenadas em memória principal - encadeamento externo;
  • Definição das operações para o tratamento de colisão usando encadeamento externo: (a) inicializa, (b) aloca, (c) insere, (d) busca, (e) retira e (f) libera;
  • Motivação para o aprendizado de heaps;
  • Operações básicas de heaps:
    • 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).
  • Algoritmo de ordenação heapsort.

• 13 e 14/06/2019 (apresentação de trabalhos, que devem ser entregues, por meio digital, até o dia 12/06/2019 às 23:59h)

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

• 27/06/2019 (segunda prova)

• 04/07/2019 (revisão das notas da segunda prova e dos trabalhos a partir das 15:00h)