MAC 710 - Estruturas de Dados - 1997 |
Semestre: 1.o semestre de 1997
Horário:
3.a feiras: 16 - 18 h
5.a feiras: 14 - 16 h
Sala: 259 Bloco A - 2.o andar
Data da primeira prova: dia 13 de maio de 1997
Data da segunda prova: dia 24 de junho de 1997
Data da terceira prova (opcional ver critério de avaliação abaixo): dia 1 de julho de 1997
Requisitos:
- Manual de uso do sistema ("guia de sobrevivência") em .html
ou em postscipt .ps disponível também para Xerox na pasta do Siang na Sala de Xerox, bloco B térreo.
- Notas de aula sobre orientação a objetos e tipos abstratos de dados (em postscipt .ps) disponível também para Xerox na pasta do Siang na Sala de Xerox, bloco B térreo.
Outros avisos:
Para informações sobre prazos de matrículas, trancamento, dias sem aula, etc. veja o
Calendário da Pós-Graduação para 1997.
Listas de exercícios: média E
Listas de programas: média ponderada Pg
Nota de aproveitamento final A:
se Pg < 5 ou P < 5 então A = min(Pg, P) ``reprovado''
senão A = (0.5 E + 3.5 Pg + 6 P )/10
Aula 1 (11/03/1997): Descrição do curso; uso de equipamentos; homepage do curso; Complexidade de algoritmos. Passar para casa Exercício 1.
Aula 2 (13/03/1997): Limite ou cota superior (upper bound) e limite ou cota inferior (lower bound); listas lineares (.ps) : pilhas, filas.
Aula 3 (18/03/1997): Implementação de pilhas e filas usando alocação sequencial. Passar o programa 1.
Aula 4 (25/03/1997): Exercício em classe: como compartilhar um espaço de tamanho m por n pilhas, usando alocação sequencial. Alocação ligada ou encadeada: motivação, lista livre, rotinas para sua manipulação. Pilha em alocação ligada. Algoritmo para inserir na pilha.
Aula 5 (01/04/1997): Continuação de alocação ligada ou encadeada: algoritmo para remover da pilha; algoritmos para inserir e remover da fila. Alocação dinâmica de espaço em Pascal (comandos new, dispose etc.) Passar para casa Exercício 2.
Aula 6 (03/04/1997): Listas ligadas circulares; listas duplamente ligadas. Exercício em classe sobre um algoritmo ingenhoso (devido a Knuth) que permite percorrer uma lista linear ligada em ambos os sentidos, sem usar dois apontadores por elemento.
Aula 7 (08/04/1997): Ordenação topológica: um exercício usando várias estruturas de dados. Passar para casa Exercício 3 (em postscript .ps).
Aula 8 (10/04/1997): Ordenação topológica: continuação da aula anterior, concluindo o algoritmo. Comentar sobre o exercício programa no. 2, sobre átomos, listas, e sua representação.
Aula 9 (15/04/1997): Fila de prioridade, conceito, alternativas de implementacao.
Aula 10 (17/04/1997): Coleta de lixo (garbage collection): conceito, método de marcação e varredura; método de contador de referências.
Aula 11 (22/04/1997): Conceitos de programação orientação a objetos e tipos abstratos de dados.
Aula 12 (24/04/1997): Exemplo de especificação de um tipo abstrato de dados: pilha. Árvores: conceitos e nomenclatura.
Aula 13 (29/04/1997): Árvores binárias; representar expressões aritméticas com operadores binários; contrução de uma árvore binária perfeitamente balanceada. Passar o Exercício 4. Passar o Programa 3.
Aula 14 (06/05/1997): Algoritmos para percorrer uma árvore binária de maneira sistemática, visitando todos seus nós: pré-ordem, in-ordem, pós-ordem. Pergunta: o procedimento printtree visto na aula passada parece com que tipo de percurso? Árvore binária de busca: característica. Percorrer uma árvore de busca em in-ordem produz os valores em ordem crescente.
Aula 15 (08/05/1997): Aulas de exercícios em classe.
Aula 16 (13/05/1997): Prova. Local da prova: Sala 1 do bloco B.
Aula 17 (15/05/1997): Árvore binária de busca: algoritmos para localizar um dado (função loc) e inserir um dado novo (procedimento search).
Aula 18 (20/05/1997): Resolução da prova. Árvore binária de busca: algoritmo para remover um dado.
Aula 19 (22/05/1997): Análise do desempenho (número médio de comparações). Discussão sobre quando é interessante usar a árvore binária de busca.
Aula 20 (27/05/1997): Aula não dada e a ser reposta com aulas mais longas nas próximas duas terças feiras.
Aula 21 (03/06/1997): Aula "reforçada" com 3 horas de duração: Árvore AVL - árvore de busca balanceada (alturas de subárvores diferem em no máximo um). Rotação LL, RR, LR e RL para rebalanceamento da árvore. Árvore ótima de busca: definição e exemplos.
Aula 22 (05/06/1997): Árvore ótima de busca: algoritmo de construção usando a técnica de programação dinâmica.
Aula 23 (10/06/1997): Aula "reforçada" com 3 horas de duração: Árvore ótima de busca: idéia do algoritmo de construção usando a técnica de programação dinâmica. Outro exemplo usando programação dinâmica: multiplcação de n matrizes. B-árvores: motivação e um exemplo simples.
Aula 24 (12/06/1997): B-árvores: definição, busca, inserção e remoção. Tabela de espalhamento (hashing).
Aula 25 (17/06/1997): Tabela de espalhamento (hashing): tratamento de colisão. LISP: introdução.
Aula 26 (19/06/1997): LISP: definição de funções, exemplos. Aula com demonstração.