MAC 5710 - Estruturas de Dados - 2003 |
Semestre: 1.o semestre de 2003
Horário:
2.a feiras: 16 - 18 h
4.a feiras: 14 - 16 h
Sala de Aula: 259 Bloco A - 2.o andar
Data da primeira prova:
Dia 28 de abril de 2003 (segunda feira)
(Matéria da primeira prova: até a aula 10 inclusive.)
Data da segunda prova:
Dia 16 de junho de 2003 (segunda feira)
(Matéria da segunda prova: desde a aula 11 até a aula 23 inclusive.)
Data da terceira prova (opcional ver critério de avaliação abaixo):
Dia 2 de julho (quarta feira) às 14h.
(Toda matériada desde a aula 1 até a aula 23 inclusive.)
Requisitos:
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 2003.
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
Atenção: os programas devem ser feitos individualmente.
O que voce deve entregar: Deve ser entregue uma listagem com a impressão do programa fonte, e a impressão do resultado (alguns testes que comprovam que o programa está funcionando de acordo). Não entregue o diskette.
Aula 2 (26/02/2003): Importância de estudar a complexidade de algoritmos. Como melhorar a eficiência de um programa: otimizações locais, uso de "profile" para conhecer o perfil de execução, analisar a complexidade e mudar a concepção do algoritmo visando obter uma complexidade melhor. Conceito de cota ou limite superior (upper bound) e cota ou limite inferior (lower bound).
Aula 3 (10/03/2003): Listas lineares (.ps) ou em pdf (.pdf): pilhas, filas, suas características e utilidades. Destacar a diferença entre a especificação ou definição de uma estrutura de dados e sua representação/implementação.
Aula 4 (17/03/2003): Alocação de memória sequencial. Representação de uma pilha em alocação sequencial. Representação de uma fila em alocação sequencial: inserção e remoção. Fila circular (em alocação sequencial). Problema de compartilhar um espaço único por várias filas e/ou pilhas. Vantagens (simplicidade) e desvantagens da alocação sequencial (alocação de espaço é estático, de difícil dimensionamento a priori, dificultando a expansão bem como o compartilhamento do mesmo espaço por várias estruturas de dados).
Aula 5 (19/03/2003): Alocação ligada ou encadeada. Pilhas em alocação ligada. Passar o Programa 1.
Aula 6 (24/03/2003): Filas em alocação ligada. Comparar as as duas representações sequencial e ligada apresentando as vantagens e desvantagens de cada uma. Várias maneiras de implementar a alocação ligada: (1) usando linguagens que não possuem ponteiros (você gerencia tudo, incluindo a lista livre e as rotinas ExtraiLivre e DevolveLivre)
Aula 7 (26/03/2003): Várias maneiras de implementar a alocação ligada: (2) usando linguagens que possuem ponteiros (o próprio sistema cuida da organização do espaço livre e ExtraiLivre e DevolveLivre são feitos pelo sistemas e recebem outros nomes e.g. new e dispose em Pascal). Listas circulares ligadas. Listas duplamente ligadas (tem dois links: um llink apontando para o elemento da esquerda e um rlink apontando para o elemento da direita). Passar o Exercício 2.
Aula 8 (31/03/2003): Exemplo do uso de listas circulares com cabeça de lista: representação de matriz bidimensional esparsa. Um esquema que permite caminhar nos dois sentidos (para direita e para esquerda) em uma lista linear ligada com um campo apenas para link. Introduzir o problema da ordenação topológica: um problema cuja solução ilustra bem o uso de várias estruturas de dados tanto em alocação sequencial como ligada, usando listas lineares ligadas, filas, etc.
Aula 9 (02/04/2003): Problema de ordenação topológica: relações de ordem parcial, propriedades, definição de ordem topológica, algoritmo para obter uma ordem topológica.
Aula 10 (09/04/2003): Fila de prioridade: conceitos, várias formas de implementação, implementação com o uso de heap. Representação de um heap com um vetor.
Aula 11 (23/04/2003): Passar Exercício 3 (em postscript .ps) (em .pdf) Passar Programa 2 (em postscript .ps) (em .pdf) Processamento de listas; processamento simbólico. Comentar sobre o exercício programa no. 2, sobre átomos, listas, e sua representação.
Aula 12 (28/04/2003): Primeira prova. Matéria: até a aula 10 inclusive.
Aula 13 (30/04/2003): Dar uma dica para ler uma lista (procedimento le_lista) e construir a representação correspondente na memória, de forma recursiva. "Garbage collection": reciclagem de células de memória quando se esgota a lista livre. Método 1: marcação e coleta (mark-scan).
Aula 14 (05/05/2003): Continuação "Garbage collection": Método 2: contador de referências. Árvore. Definições e exemplo. Nomenclatura sobre vários termos usados em árvores. Exemplos de uso de árvores: por exemplo em árvores de jogos (usadas em Inteligência Artificial).
Aula 15 (07/05/2003): Construção de árvore de altura mínima, perfeitamente balanceada (função tree). Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem).
Aula 16 (12/05/2003): Para o algoritmo dado na aula anterior, fornecer uma entrada e mostrar o resultado da execução (a árvore construída). Modos de percorrer uma árvore binária: pré-ordem, in-ordem, pós-ordem. Dar algoritmos recursivos e para o percurso pré-ordem, in-ordem e pós-ordem. Comentar o percurso por nível ou por largura (breadth-first), que deve usar uma fila.
Aula 17 (19/05/2003): Comentar que o procedimento visto printtree (visitar a subárvore direita, visita a raiz, visita a subárvore esquerda) é parecido com o percurso da árvore em in-ordem (invertendo direita e esquerda). Arvore binária de busca: conceitos e complexidade. Inserção na árvore binária de busca, comentário sobre sua complexidade: pior caso é O(n) para uma árvore degenerada (desbalanceada). Será mostrado em aulas futuras que a complexidade do caso médio é O(log n).
Aula 18 (21/05/2003): Remoção da árvore binária de busca. Três casos considerados: nó a ser removido não está na árvore (fácil), nó a ser removido possui 0 ou 1 filho, nó a ser removido possui 2 filhos. Comentário sobre sua complexidade.
Aula 19 (26/05/2003): Analisar a complexidade média: número de comparações para buscar uma chave qualquer entre as $n$ possíveis chaves da árvore de busca, quando a árvore de busca é uma arbitrária entre todas as árvores correspondentes às $n!$ permutações das $n$ chaves. Passar Programa 3.
Aula 20 (28/05/2003): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL. Algoritmo de inserção em árvore de AVL, por meio de rotações visando o rebalanceamento. (Informação do Prof. Arnaldo Mandel para quem quer usar árvore AVL: Foi instalada uma biblioteca implementando árvores AVL e Red-Black. A documentação pode ser lida no info (emacs), nó Avl. Os programas fonte estão em /usr/gnu/avl-1.4.0)
Aula 21 (02/06/2003): Árvore de busca AVL: Algoritmo de remoção. Introduzir o conceito de árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave.
Aula 22 (04/06/2003): Algoritmo para criação de uma árvore de busca ótima, dadas as chaves e suas probabilidades de acesso: método de programação dinâmica; ilustração do método por um exemplo.
Aula 23 (09/06/2003): B-árvores, uma técnica para armazenamento e recuperação de grandes volumes de dados. Busca, inserção e remoção em B-árvores: O(log_n N) onde o log é na base n= a ordem da B-árvore, N é o número de chaves na B-árvore.
Aula 24 (11/06/2003): Uma aula prática para apresentar a linguagem LISP, rodando vários exemplos.
Aula 25 (16/06/2003): Segunda prova. Matéria: desde a aula 11 até a aula 23 inclusive.