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
O sistema de avaliação da disciplina consiste na realização de duas provas e de trabalhos de programação.
A média final do discente no curso será formada pela combinação das notas das provas e a média aritmética
dos trabalhos, com pesos (provavelmente distintos) entre as avaliações. As provas serão realizadas nos horários de aula.
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)