Estruturas de Dados e Algoritmos

horário: terças de 14:00 às 18:00h

Ementa da disciplina

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

Critério de avaliação

Literatura básica

• T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to algorithms, McGraw-Hill.
• J. Szwarcfiter e L. Markeson, Estrutura de Dados e Algoritmos, Editora LTC.
• W. Celes, R. Cerqueira e J.L. Rangel, Introdução a Estruturas de Dados, Campus.
• B.W. Kernighan e D.M. Ritchie, C: a linguagem de programação (Padrão ANSI), Editora Campus.

Aulas ministradas

• 21/08

  • Apresentação do curso: objetivos e tópicos abordados.
  • Critério de avaliação;
  • Introdução a linguagem C: tipos, variáveis e constantes;
  • Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos;
  • Precedência de operadores; e
  • Saída básica: printf.
    

• 28/08

  • Entrada básica: scanf;
  • Decisões com if;
  • Repetições com while, for e do;
  • break e continue;
  • Seleção com switch-case-default;
  • Exemplo em sala: cálculo de N primos após o número N;
  • Funções;
  • Pilha de execução;
  • Ponteiros para variáveis; e
  • Passagem de ponteiros para funções.
  • Lista de exercícios.
    

• 04/09

  • Recursão;
  • Exemplo em sala: representação binária de um número inteiro não negativo;
  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Alocação dinâmica de vetores; e
  • Lista de exercícios.
    

• 11/09

  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres;
  • Escrita de algumas funções da biblioteca string.h nas versões iterativa e recursiva;
  • Noções de complexidade de algoritmos:
    • Motivação;
    • Métodos empíricos versus analíticos;
    • Complexidades: pior caso, melhor caso e caso médio;
    • Notação O; e
    • Complexidade de funções recursivas.
      
  • OBS: Datas das provas
    • primeira prova: 30/10
    • segunda prova: 27/11
      
  • Lista de exercícios.
    

• 18/09 (não houve aula)

• 25/09

  • Tipo estrutura;
  • Variáveis do tipo estrutura e ponteiros para o tipo estrutura; e
  • Motivação para o uso de listas;
  • Definição de listas; e
  • Operações básicas: (a) inicialização, (b) inserções na lista, (c) busca de um elemento, (d) impressão da lista, (e) liberação da lista e (f) retirada de elementos da lista.
  • OBS: a aula da semana que vem (02/10) comecará às 15:00h devido a reunião de Departamento.
    

• 02/10

  • 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 na lista e (f) retirada de um elemento da lista; e
  • Exemplos desenvolvidos em sala de aula: inserções na última posição e na posição k de uma lista.
    

• 09/10

  • 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 (e) inserção de um elemento na lista; e
  • Exemplos de questões de provas de períodos anteriores.
  • OBS: Trabalho computacional com data prevista de entrega em 20/11.
    

• 16/10

  • Motivação para o uso de 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 e (d) teste se a pilha está vazia; e
  • Motivação para o uso de filas;
  • Implementação de filas com vetores e listas;
  • Operações básicas: (a) inicialização, (b) retirada do primeiro elemento da fila, (c) inserção de um elemento no fim da fila, e (d) teste se a fila está vazia;
  • Exemplo de aplicação: impressão de uma fila; e
  • Lista de exercícios.
    

• 23/10

  • Algoritmos de ordenação de vetores: bolha, seleção, quicksort e mergesort.
    

• 30/10 (Primeira prova - Auditório da Engenharia)

• 06/11

  • Motivação para o uso de heaps;
  • Heaps: implementação e operações;
  • Algoritmo de ordenação heapsort;
  • Motivação para o uso de árvores;
  • Implementação de árvores binárias;
  • Operações básicas: (a) inicialização, (b) impressão, (c) criação de árvores binárias, e (d) liberação; e
  • Travessia em árvores: pré-ordem (profundidade), simétrica (em-ordem) e pós-ordem.
    

• 13/11

  • Travessia em árvores em profundidade usando pilhas e em amplitude usando filas;
  • Motivação para o uso de árvores binárias de busca;
  • Exemplos de árvores binárias de busca: AVL, árvores vermelho e preto e árvores B (e suas variantes);
  • Implementação de árvores binárias de busca;
  • Operações básicas: busca, inserção de um elemento e remoção em árvores binárias de busca;
  • Exercícios de árvores: cálculo da altura da árvore, geração da árvore espelho e transformação de árvore binária de busca em lista ordenada, sem usar algoritmo de ordenação; e
  • Lista de exercícios.
  • OBS: foi acordado que a segunda prova será no dia 03/12 (segunda-feira) das 13:00 às 16:30h no Auditório da Engenharia.
    

• 20/11

  • Motivação para o uso de Tabelas hash (ou Tabelas de dispersão);
  • Definição de Tabelas hash;
  • Tratamentos de colisão: (a) uso da primeira posição livre, (b) uso de dispersão dupla e (c) uso de listas lineares;
  • Definição de operações comuns aos três tipos de tratamentos de colisão; e
  • Definição das operações busca, insere e retira em cada um dos tratamentos de colisão.
  • OBS: revisão da nota da primeira prova.
    

• 27/11 (Apresentação de trabalho computacional)

• 03/12 (Segunda prova: segunda-feira das 13:00 às 16:30h no Auditório da Engenharia)

• 11/12 (Revisão da nota da segunda prova)