MAC 5710 - Estruturas de Dados - 2005 |
Semestre: 1.o semestre de 2005
Horário:
2.a feiras: 14 - 16 h
4.a feiras: 16 - 18 h
Sala de Aula: Sala 243 - Bloco A - 2.o andar
Data da primeira prova:
Dia 4 de maio de 2005 (quarta feira).
(Prova com consulta. Matéria até a aula 10 inclusive.)
Data da segunda prova:
Dia 22 de junho de 2005 (quarta feira).
(Prova com consulta. Matéria desde a aula 11 até a aula 21 inclusive.)
Data da terceira prova (opcional ver critério de avaliação abaixo):
Dia 29 de junho de 2005 (quarta feira).
(Prova com consulta. Matéria: aulas 1 até a aula 21 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 2005.
Listas de exercícios: média E
Listas de programas: média 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). Os resultados testes devem ser impressos pelo seu programa. Não é para voce digitar esses testes. Não entregue o diskette.
Aula 2 (16/03/2005): Conceito de upper bound (limite ou cota superior) e de lower bound (limite ou cota inferior). Introduzir 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. Passar para fazer em casa (e entregar) Exercício 1.
Aula 3 (28/03/2005): Listas lineares: pilha e fila. 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. 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 4 (30/03/2005): Fila circular (em alocação sequencial). Alocação ligada ou encadeada. Pilhas implementadas com alocação ligada. Passar o Programa 1.
Aula 5 (06/04/2005): Filas em alocação ligada. Pedir para ler a apostila sobre as 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), e (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). Um esquema que permite caminhar nos dois sentidos (para direita e para esquerda) em uma lista linear ligada com um campo apenas para link.
Aula 6 (11/04/2005): 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. Problema de ordenação topológica: relações de ordem parcial, propriedades, definição de ordem topológica.
Aula 7 (13/04/2005): Aplicações da ordenação topológica, um algoritmo eficiente para obter uma ordem topológica.
Aula 8 (18/04/2005): Passar Exercício 2 (em .html). Passar o Exercício 3 (em .ps ou em .pdf). 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. Algoritmos de inserção e remoção: ambos de complexidade O(log n).
Aula 9 (25/05/05): Passar o Programa 2: soma de duas matrizes esparsas usando cabeças de lista, e listas ortogonais. Coletor de lixo (garbage collector) (.pdf 42K) - rotina do sistema para identificar e recuperar dados não mais ativos. Vemos dois métodos. Método 1 "marca-varre ("mark-scan"): é o método mais geral (sem funciona) e consiste de duas fases, uma de marcação e outra de varredura. Método 2 (mais restrito, não funciona em certas condições) chamado método de contador de referências. Não recolhe o lixo constituído de listas circulares, nem quando o contador tem seu valor máximo já atingido.
Aula 10 (27/04/2005): Á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). Construção de árvore de altura mínima, perfeitamente balanceada (função tree).
Aula 11 (02/05/2005): Resolver dúvidas de listas de exercícios. Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem). 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, e o percurso por profundidade (depth-first).
Aula 12 (04/05/2005): Primeira Prova.
Aula 13 (09/05/05): Aplicação dos métodos para percorrer árvores: mostrar um algoritmo para calcular as alturas de todos os nós de uma árvore binária dada, usando pós-ordem e uma rotina apropriada de visita. Conversão de uma floresta de árvores genéricas (com qualquer número de filhos) para uma árvore binária. Explicar e passar o Programa 3.
Aula 14 (11/05/05): Arvore binária de busca: conceitos e complexidade. Busca na árvore de busca (function loc). Inserção na árvore binária de busca (procedimento search, ou seja, busca com inserção). Comentário sobre a complexidade de busca e de inserção: depende da altura da árvore. O 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 15 (16/05/05): 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 16 (18/05/05): 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.
Aula 17 (30/05/05): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL.
Aula 18 (01/06/05): Inserção e remoção em árvore de AVL, por meio de rotações visando o rebalanceamento: rotação LL, rotação RR, rotação LR e rotação RL. (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 19 (06/06/05): Introduzir o conceito de árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave. Algoritmo para criação de uma árvore de busca ótima, dadas as chaves e suas probabilidades de acesso.
Aula 20 (08/06/05): Obtenção árvore binária de busca ótima, dadas todas as chaves e suas probabilidades (ou frequências) de acesso, pelo método de programação dinâmica; ilustração do método por um exemplo.
Aula 21 (13/06/05): Uso da técnica de programação dinâmica para resolver um outro problema: multiplicação de n matrizes. 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 22 (15/06/05): Aula prática sobre LISP. Uma pequena introdução da linguagem LISP. Ver os vários sistemas LISP na Página do Prof. Marcelo Melo. (Obs: o assunto LISP não entra nas provas.)
Aula 23 (20/06/05): Aula para tirar dúvidas.
Aula 24 (22/06/05): Segunda Prova.
Aula 25 (29/06/05): Terceira Prova (opcional).