Estruturas de Dados e Algoritmos

horários das aulas: terças de 9:00 às 11:00h na sala 237D e quintas de 9:00 às 11:00h na sala 101H

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; e
• Algoritmos de ordenação.

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/03/14

  • 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/03/14

  • Entrada e saída básicas (scanf e printf);
  • Pilha de execução;
  • Decisões com if;
  • Repetições com while, for e do-while;
  • break;
  • Seleção com switch-case-default; e
  • Exemplos de aplicação.
    

• 18/03/14

  • Funções;
  • Pilha de execução;
  • Ponteiros;
  • Declaração de vetores;
  • Passagem de vetor como parâmetro de entrada de funções;
  • Alocação dinâmica de vetores;
  • Exemplo de aplicação: ordenação dos dados de um vetor; e
  • Lista de exercícios.
    

• 20/03/14

  • Exemplo desenvolvido em aula;
  • Cadeia de caracteres;
  • Leitura e escrita de cadeia de caracteres; e
  • Lista de exercícios.
    

• 25/03/14

  • Declaração de matrizes;
  • Passagem de matriz como parâmetro de entrada de funções;
  • Alocação dinâmica de matrizes;
  • Exemplo de aplicação: representação de matrizes simétricas;
  • Tipo estrutura;
  • Variáveis do tipo estrutura;
  • Ponteiros para o tipo estrutura; e
  • Lista de exercícios.
    

• 27/03/14

  • Motivação para o uso de listas;
  • Definição de listas; e
  • Operações básicas (versões iterativa e recursiva): (a) inicialização, (b) inserção de um elemento no início e no final da lista, (c) impressão da lista, (d) liberação da lista e (e) remoção de um elemento da lista.
    

• 01/04/14

  • Mais operações em listas (versões iterativa e recursiva): (a) busca de um elemento e (b) inserção de um elemento na lista ordenada; e
  • Exemplos desenvolvidos em sala de aula (versões iterativa e recursiva): inserção de antecessores de um elemento passado como parâmetro de entrada e merge de duas listas ordenadas.
    

• 03/04/14

  • 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;
    • Complexidade de funções recursivas; e
    • Lista de exercícios.
      
    
    

• 08/04/14

  • 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;
  • Motivação para o uso de listas duplamente encadeadas;
  • Definição de listas duplamente encadeadas; e
  • Operações básicas: (a) inicialização, (b) busca de um elemento, (c) impressão da lista, (d) liberação da lista, (e) inserções de um elemento na lista (inserção mais barata e inserção ordenada) e (f) remoção de um elemento.
    

• 10/04/14

  • Exemplos desenvolvidos em sala de aula: (a) merge de duas listas (duplamente encadeadas) ordenadas, sendo que a lista de resposta não possui elementos repetidos; (b) inserção de antecessores e de sucessores de um elemento passado como parâmetro de entrada; e (c) retirada de todos os elementos repetidos.
    

• 15/04/14

  • Motivação para o uso de pilhas; e
  • Exemplos de uso: impressão de uma pilha e cópia de uma pilha.
  • 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.
  • Motivação para o uso de filas;
  • Implementação de filas com vetores;
  • 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; e
  • Exemplo de aplicação: cópia de uma fila.
    

• 22/04/14

  • 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; e
  • Operações básicas: (a) inicialização e (b) busca.
  • OBS: Datas das provas
    • primeira prova: 22/05/14
    • segunda prova: 10/06/14
      
    
    

• 24/04/14

  • Mais operações básicas: (a) impressão (pré-ordem, pós-ordem, simétrica e largura), (b) criação de árvores binárias, informando a raiz e as duas sub-árvores, e (c) liberação de árvores binárias;
  • Motivação para o uso de árvores binárias de busca;
  • Implementação de árvores binárias de busca; e
  • Operações básicas: busca, inserção e remoção de um elemento.
    

• 29/04/14

  • Motivação para o uso de árvores AVL e AVP;
  • Implementação de árvores binárias AVL; e
  • Operação básica: rotação a esquerda.
  • Trabalho computacional: manipulação de grafos não-orientados.
    • Grupo de no mínimo dois e de no máximo três discentes.
    • Semana de entrega: de 26/05/14 a 30/05/14.
    • Descrição: dado um grafo de entrada (que inicialmente é definido em um arquivo texto, cujo nome será informado como argumento para a main), seu programa deve possibilitar as seguintes operações ao usuário:
      1. inserir e retirar nós e arestas;
      2. verificar se o grafo é conexo. Se a resposta for verdadeira, seu programa deve informar:
         1. no arquivo AGM.txt a árvore geradora mínima, usando ou Algoritmo de Prim, ou o Algoritmo de Kruskal; e
         2. no arquivo CMC.txt o caminho mais curto de um nó (passado como parâmetro de entrada) a todos os demais, utilizando o Algoritmo de Dijkstra.
            
      3. armazenar no arquivo novo.txt o grafo modificado pelo usuário.
         
    • Exemplo de arquivo de entrada.
      
    
    

• 06/05/14

  • Operações básicas: rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda;
  • Apresentação das operações de inserção e de remoção de nós em AVL; e
  • Código que mostra o funcionamento da AVL.
    

• 08/05/14

  • Representação de grafos por meio de listas encadeadas; e
  • Operações em grafos: (a) inicialização, (b) destruição, (c) impressão, (d) busca de nós e (e) inserção e remoção de nós e arestas.
    

• 13/05/14

  • Motivação para árvores B;
  • Definição de árvores B; e
  • 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ó.
    

• 15/05/14

  • Implementação 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 de insere.
  • Ordem de apresentação do trabalho computacional:
    • 26/05/14 de 14:00 às 15:00h - G01 (Hedi, Javier e Mairon)
    • 26/05/14 de 15:00 às 16:00h - G07 (Alan e Frederico)
    • 26/05/14 de 16:00 às 17:00h - G02 (Pedro e Suliane)
    • 27/05/14 de 14:00 às 15:00h - G08 (Guilherme e João Felipe)
    • 27/05/14 de 15:00 às 16:00h - G06 (Mateus Felipe e Thiago)
    • 28/05/14 de 11:00 às 12:00h - G11 (Fabiano, Felipe e Thiago)
    • 28/05/14 de 14:00 às 15:00h - G09 (Carolina, Gleison e Helga)
    • 28/05/14 de 15:00 às 16:00h - G03 (Augusto e Cinthya)
    • 28/05/14 de 16:00 às 17:00h - G04 (Alexandre e Eider)
    • 28/05/14 de 17:00 às 18:00h - G10 (Andre, Jonas e Rodrigo)
    • 29/05/14 de 15:00 às 16:00h - G05 (Maicon, Natalie e Rogério)
    • 29/05/14 de 16:00 às 17:00h - G12 (Bruno e Mateus Pelegrino)
      
    
    

• 20/05/14 (dúvidas para a primeira prova)

• 22/05/14 (primeira prova)

• 27/05/14

  • Explicação dos casos necessários para o desenvolvimento do algoritmo de remoção em árvores B.
    

• 29/05/14

  • Implementação das funções de árvores B.
    

• 03/06/14 (não houve aula)

• 05/06/14 (revisão da nota da primeira prova e dúvidas para a segunda prova)

• 26/06/14 (revisão da nota da segunda prova de 10:00 às 11:30h na sala 101 da UFASA)

  • Notas finais.