Estruturas de Dados e Algoritmos

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

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

• 11/08/15

  • 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; e
  • Precedência de operadores.
    

• 13/08/15 (não houve aula)

• 18/08/15

  • Operadores: binários, ternário e sizeof(tipo);
  • Entrada e saída básicas (scanf e printf);
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break;
  • Seleção com switch-case-default;
  • Exemplo de aplicação: calculadora de inteiros;
  • Funções e pilha de execução; e
  • Lista de exercícios.
    

• 20/08/15

  • Continuação de funções e pilha de execução;
  • Ponteiros;
  • Exemplo de aplicação: cálculo das raízes de uma equação de segundo grau;
  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Exemplo de aplicação: ordenação (usando bubble sort e insertion sort) dos dados de um vetor; e
  • Lista de exercícios.
    

• 25/08/15

  • Ordenação de vetor usando o quicksort;
  • Alocação dinâmica de vetores usando malloc 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: versões iterativa e recursiva de strcpy e strcmp; e
  • Lista de exercícios.
    

• 27/08/15

  • 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;
  • Parâmetros da função main (isto é, os argumentos do programa); e
  • Lista de exercícios.
    

• 01/09/15

  • Tipo estrutura;
  • Variáveis do tipo estrutura;
  • Ponteiros para o tipo estrutura;
  • Motivação para o uso de listas;
  • Definição de listas; e
  • 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; e
  • Operações básicas que possuem versões iterativa e recursiva: (a) impressão da lista e (b) liberação da lista.
    

• 03/09/15

  • Mais operações básicas (versões iterativa e recursiva): (a) remoção de um elemento da lista, (b) busca de um elemento e (c) inserção de um elemento na lista ordenada; e
  • Exemplo desenvolvido em sala de aula (versões iterativa e recursiva): retirada de todos os elementos repetidos de uma lista.
    

• 08/09/15

  • Exemplos desenvolvidos em sala de aula, com versões iterativa e recursiva: (a) merge de duas listas ordenadas, (b) cruzamento de duas listas, a partir de uma informação comum existente nelas (e passada como parâmetro de entrada), e (c) ordenação de uma lista; e
  • Lista de exercícios.
    

• 10/09/15

  • 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, e (f) retirada da primeira 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) inserção de um elemento no início da lista, e (f) remoção da primeira ocorrência de um elemento; e
  • Exemplos desenvolvidos em sala de aula: (a) merge de duas listas (duplamente encadeadas) ordenadas e (b) cruzamento de duas listas, a partir de uma informação comum existente nelas (e passada como parâmetro de entrada).
    

• 15/09/15

  • Motivação para o uso de pilhas;
  • Exemplos de uso: impressão de uma pilha, ordenação da própria pilha passada como parâmetro de entrada e merge de duas pilhas;
  • 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; e
  • Marcadas as datas das provas:
    • primeira prova: 06/10/15; e
    • segunda prova: 19/11/15.
      
    
    

• 17/09/15

  • Motivação para o uso de filas;
  • Exemplo de uso: merge de duas filas, mantendo as filas originais inalteradas;
  • Implementação de filas com vetores; e
  • Operações básicas: (a) inicialização e destruição da fila, (b) inserção de um elemento no fim da fila, (c) teste se a fila está vazia, e (d) retirada do início da fila.
    

• 22/09/15

  • 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;
  • Lista de exercícios;
  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Exemplo de uso: retornar o menor e o maior elemento da árvore; e
  • Operações básicas: (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.
    

• 24/09/15

  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca;
  • Operações básicas: (a) busca, (b) inserção e (c) remoção de um elemento, incluindo as implementações dos itens de (a) até (d) da aula relacionada às árvores binárias; e
  • Exemplo de uso: escrever uma árvore binária de busca a partir de um vetor ordenado.
    

• 29/09/15

  • 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; e
  • Código que mostra o funcionamento da AVL.
    

• 01/10/15

  • Exemplos de inserções e retiradas em AVL; e
  • Exercício desenvolvido em sala da aula: teste se uma árvore binária é AVL.
    

• 06/10/15 (primeira prova)

• 08/10/15 (não houve aula devido ao engarrafamento)

• 13/10/15

  • 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ó e
  • Ideia 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.
    

• 15/10/15 (não houve aula devido ao feriado)

• 20/10/15

  • Explicação dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B.
  • OBS.: a data da segunda prova foi alterada para 19/11/2015.
    

• 22/10/15

  • Código das funções da árvores B.
  • Trabalho Computacional: implementação das funções de árvore B⁺ em uma universidade hipotética. Os dados a serem armazenados dos alunos são a sua matrícula (isto é, int que é a informação única do discente, estando presente nos nós internos e nas folhas), o seu coeficiente de rendimento (float) e o seu nome (string de, no máximo, 30 caracteres). As duas últimas informações ESTARÃO ARMAZENADAS SOMENTE NAS FOLHAS:
    • a entrada de dados inicial pode ser realizada por meio do uso de arquivos ou via teclado;
    • deve ser permitido ao usuário do sistema: (a) buscar indivíduos; (b) imprimir informações relevantes, tanto da estrutura, quanto do discente; (c) inserir novos discentes; (d) retirar alunos de acordo com sua matrícula; (e) destruir a árvore B⁺; e (f) alterar o nome e o coeficiente de rendimento dos alunos. A informação de matrícula é constante;
    • a estrutura deve ser totalmente destruída pelo seu programa antes da execução ser finalizada;
    • grupo de no mínimo dois e de no máximo três discentes;
    • data de entrega: até o dia 23/11/15 às 23:59h; e
    • semana de apresentação: de 24/11 a 26/11/15.
      
    
    

• 27/10/15 (revisão da nota da primeira prova, com o fornecimento de um gabarito de respostas)

• 29/10/15

  • 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.
  • Ordem de apresentação do trabalho computacional:
    • 24/11/15 de 09:00 às 10:00h - G11 (José Valencia)
    • 24/11/15 de 10:00 às 11:00h - G10 (Julliano)
    • 24/11/15 de 11:00 às 12:00h - G03 (Gisele, Jéssica e Priscilla)
    • 25/11/15 de 11:00 às 12:00h - G05 (João Marcos, Philipe e Rodrigo)
    • 25/11/15 de 12:00 às 13:00h - G12 (Mark)
    • 25/11/15 de 14:00 às 15:00h - G09 (Izabella)
    • 25/11/15 de 15:00 às 16:00h - G07 (Glendys, Leonardo Luís e Yoan)
    • 25/11/15 de 16:00 às 17:00h - G04 (Bruno, Ian e Thiago)
    • 26/11/15 de 11:00 às 12:00h - G08 (Leonardo Manhães)
    • 26/11/15 de 12:00 às 13:00h - G06 (Alfredo, Daysel e José Ramon)
    • 26/11/15 de 14:00 às 15:00h - G01 (Ítalo e Sávio)
    • 26/11/15 de 15:00 às 16:00h - G02 (Alejandro e Fernando)
      
    
    

• 03/11/15

  • Motivação para o aprendizado de heaps;
  • Operações básicas de heaps;
  • Algoritmo de ordenação heapsort;
  • Algoritmo de ordenação quicksort (e o procedimento qsort existente na biblioteca stdlib.h); e
  • Lista de exercícios.
    

• 05/11/15

  • Motivação para o uso de tabelas hash (ou tabelas de dispersão);
  • Definição de tabelas hash;
  • Função de hash;
  • Características ideais de funções de hash: 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.
    

• 10/11/15

  • Grafos e dígrafos: apresentação de conceitos, representação por meio de matrizes de adjacências e exemplos de aplicação.
  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) impressão, (c) busca e (d) inserção de nós e arestas.
    

• 12/11/15

  • Operações em grafos: liberação do grafo e remoção de nós e de arestas;
  • Exercícios para a segunda prova; e
  • A segunda prova será dia 19/11 das 10:00 às 13:20h. A matéria da prova é composta de listas simplesmente encadeadas, árvores binárias, árvores balanceadas, heaps e tabelas hash.
    

• 17/11/15 (exercícios para a segunda prova)

• 19/11/15 (segunda prova das 10:00 às 13:20h)

• De 24 a 27/11/15 e de 30/11 a 02/12 (apresentação de trabalhos, que devem ser entregues, por meio digital, até o dia 23/11/15 às 23:59h)

• 03/12/15 (revisão das notas da segunda prova e dos trabalhos)