Estruturas de Dados I (TCC-00.171)
horários das aulas: terças e quintas de 11:00 às 13:00h na sala 505 (UFASA)
Objetivos
Familiarizar os alunos com as principais estrururas de dados e suas correspondentes abstrações.
Tópicos Abordados
- Listas, pilhas e filas;
- Árvores binárias (e binárias de busca) e árvores balanceadas (AVP e AVL);
- Grafos e dígrafos; e
- Ordenação.
Critério de avaliação
O sistema de avaliação da disciplina consiste na realização de duas provas, de C trabalhos computacionais de grande porte e de L trabalhos de laboratório (listas de exercícios e DOJOS). A média final (MF), isto é, a nota que consta no histórico escolar do discente será calculada levando-se em consideração a média aritmética das notas das provas (MP) e a média aritmética dos trabalhos computacionais (MC). Se MP e MC forem maiores ou iguais a 6.0, MF será formada pela combinação aritmética das notas das provas e MC. Senão, se MP < 4.0 ou MC < 5.0, o aluno será reprovado com MF igual ao mínimo entre 3.9 e a combinação aritmética das notas das provas e MC. Senão, o discente fará uma verificação suplementar (VS), com data e horário pré-estabelecidos, respeitando-se o prazo de 48 horas após a divulgação das médias. As provas serão realizadas nos horários de aula. Haverá bônus em MF, somente para os aprovados e para os que farão a VS, considerando-se as notas obtidas em L.
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.
Horários de Monitoria
- Hugo: segundas de 16:00 às 20:00h e quintas de 14:00 às 18:00h; e
- Matheus: segundas de 14:00 às 17:00h, quartas de 14:00 às 17:00h e sextas de 10:00 às 12:00h.
Aulas ministradas
23/04/13
- Apresentação do curso: objetivos, tópicos a serem apresentados, critério de avaliação a ser empregado e literatura utilizada.
25/04/13
- Introdução a linguagem C: tipos, variáveis e constantes;
- Operadores: aritméticos, de incremento, de decremento, relacionais e lógicos; e
- Entrada e saída básicas (scanf e printf).
30/04/13
- Precedência de operadores;
- Decisões com if;
- Repetições com while e for;
- break;
- Seleção com switch-case-default;
- Exercício em sala: simulação de calculadora; e
- Pilha de execução.
02/05/13
- Funções;
- Pilha de execução; e
- Ponteiros; e
- Lista de exercícios.
07/05/13
- Declaração de vetores;
- Passagem de vetor como parâmetro de entrada de funções;
- Exemplo de aplicação: ordenação de um vetor usando o qsort implementado em stdlib.h;
- Alocação dinâmica de vetores; e
- Exemplo de aplicação: ordenação dos dados de um vetor em um outro vetor alocado dinamicamente.
09/05/13
- 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; e
- Lista de exercícios.
14/05/13
- Cadeia de caracteres;
- Leitura e escrita de cadeia de caracteres;
- Tipo estrutura;
- Variáveis do tipo estrutura; e
- Lista de exercícios.
16/05/13
- Ponteiros para o tipo estrutura;
- Motivação para o uso de listas;
- Definição de listas;
- Operações básicas: (a) inicialização, (b) inserção de um elemento no início da lista, (c) impressão da lista e (d) liberação da lista; e
- Lista de exercícios.
- OBS: Datas das provas
- primeira prova: 25/06/13
- segunda prova: 06/08/13
- VS: 15/08/13
21/05/13
- Mais operações em listas: (a) busca de um elemento, (b) inserção de um elemento na lista ordenada e (c) remoção de um elemento da lista; e
- Lista de exercícios.
23/05/13
- 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ção de um elemento na lista e (f) remoção de um elemento.
28/05/13
- 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 pilhas; e
- Exemplos de uso: impressão de uma pilha e cópia de uma pilha.
04/06/13 (aula de exercícios no LCC)
- Biblioteca que será usada para o desenvolvimento dos exercícios.
06/06/13
- Implementação dos exercícios da última aula;
- 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.
11/06/13
- 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, e (c) teste se a fila está vazia; e
- Exemplo de aplicação: merge de duas filas.
13/06/13
- Operação de retirada de fila 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;
- Exemplos desenvolvidos em sala de aula; e
- Lista de exercícios.
18/06/13
- Motivação para o uso de árvores;
- Implementação de árvores binárias; e
- Operações básicas: (a) inicialização, (b) impresão, (c) criação de árvores binárias e (d) liberação de árvores binárias.
20/06/13
- 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 e inserção de um elemento.
25/06/13 (primeira prova)
27/06/13
- Remoção em árvores binárias de busca.
02/07/13
- Motivação para o uso de árvores AVL;
- Implementação de árvores binárias AVL; e
- Operação básica de rotação a esquerda.
04/07/13
- Operações básicas: rotação a direita, rotação dupla esquerda-direita e rotação dupla direita-esquerda.
- Trabalho Computacional: sistema gerenciador de matrículas de discentes de um curso de graduação hipotético usando AVL.
- grupo de no mínimo dois e de no máximo três discentes;
- semana de entrega: de 29/07/13 a 02/08/13; e
- Arquivo de teste contendo matrícula, carga horária cursada com sucesso, número de semestres cursados e nome do discente.
09/07/13
- Gabarito e revisão da nota da primeira prova.
11/07/13
- Apresentação da operação de inserção em AVL.
16/07/13
- Remoção em AVL.
- Ordem de apresentação do trabalho computacional:
- 29/07/13 de 10:00 às 11:00h - G05 (Daniel Pinheiro, Filipe Tadeu e Igor)
- 29/07/13 de 11:00 às 12:00h - G08 (Diego e Victor José)
- 29/07/13 de 13:00 às 14:00h - G13 (Gustavo Tallarida e João Rudá)
- 29/07/13 de 15:00 às 16:00h - G14 (Ramayan e Victor Augusto)
- 29/07/13 de 16:00 às 17:00h - G03 (Gabriel, Roney e Tadeu)
- 30/07/13 de 16:00 às 17:00h - G02 (Ana, Bernardo e Vinícius)
- 30/07/13 de 17:00 às 18:00h - G10 (Matheus Guilherme e Rafael Teogenes)
- 30/07/13 de 18:00 às 19:00h - G11 (Arthur Caetano, Gustavo Marques e Leandro)
- 31/07/13 de 09:00 às 10:00h - G18 (Breno)
- 31/07/13 de 10:00 às 11:00h - G09 (Matheus Alves, Thiago e Willian)
- 31/07/13 de 13:00 às 14:00h - G19 (Newton)
- 31/07/13 de 14:00 às 15:00h - G04 (Carlos, João Lucas e Renan)
- 31/07/13 de 15:00 às 16:00h - G17 (Erick, Mathews Vaz e Victor dos Santos)
- 31/07/13 de 16:00 às 17:00h - G01 (Antonio, Guilherme e Lucas Seabra)
- 31/07/13 de 17:00 às 18:00h - G15 (Arthur Sanches, Eduardo e Rael)
- 01/08/13 de 16:00 às 17:00h - G20 (Wilker)
- 01/08/13 de 17:00 às 18:00h - G07 (Jonatha e Tayane Silva)
- 02/08/13 de 10:00 às 11:00h - G06 (Beatriz e Raissa)
- 02/08/13 de 11:00 às 12:00h - G16 (João Henrique)
- 02/08/13 de 13:00 às 14:00h - G12 (Jefferson e Taiane da Silva)
18/07/13
- Motivação para o aprendizado de heaps;
- Operações básicas de heaps; e
- Algoritmo de ordenação heapsort.
23/07/13
- Algoritmo de ordenação quicksort (e o procedimento qsort existente na biblioteca stdlib.h).
25/07/13 (não houve aula)
29/07/13 (apresentação do trabalho computacional)
30/07/13 (apresentação do trabalho computacional)
- Grafos e dígrafos: apresentação de conceitos, representação por meio de matrizes de adjacências e exemplos de aplicação.
31/07/13 (apresentação do trabalho computacional)
01/08/13 (apresentação do trabalho computacional)
- Representação de grafos por meio de listas encadeadas; e
- Lista de exercícios.
02/08/13 (apresentação do trabalho computacional)
06/08/13 (segunda prova)
13/08/13 (revisão da nota da segunda prova na sala 505 (UFASA) das 11:00 às 12:30h)
15/08/13 (VS - das 11:00 às 14:00h - na sala 505 da UFASA)
- Notas finais; e
- Revisão da nota da VS: 19/08/13 das 11:00h às 12:00h.