MAC 5710 - Estruturas de Dados - 2008 |
Avisos:
A entrega de exercícios pode ser ou em papel ou por email.
Se voce entregar por
email, mande para
song"at"ime"ponto"usp"br".
Se prefere entregar em papel, entregue em aula ou na
Sala 293 Bloco A (pode ser colocado por baixo da porta se eu não estiver na sala).
Neste caso, mande-me um email avisando.
Disciplina oferecida pela Unidade: Instituto de Matemática e Estatística
Departamento: Departamento de Ciência da Computação
Professor responsável: Siang Wun Song
Telefones: 3091-6141, 3091-6135 (Secretaria do Depto.)
Sala do Professor: Sala 293 (2.o andar) - Bloco A do IME
Monitor da disciplina: Não há.
Disciplina oferecida: No curso de pós-graduação no IME/USP
Pré-requisito desejável: Boa experiência em alguma linguagem de programação alto nível (e.g., C, C++, Java, etc.).
Local das aulas: Sala 241 - Bloco A - 2.o andar - IME/USP
Horário das aulas: 3.a feiras: 10-12 h e 5.a feiras: 8-10 h
Programa:
Bibliografia:
Critérios de avaliação:Provas, exercícios e programas
Regime de oferecimento: Cada semestre (1.o semestre de cada ano)
Carga horária semanal e número de créditos: 4 horas - 8 créditos
Data da primeira prova:
Dia 29/04/2008 (terça-feira).
Prova com consulta.
Matéria: até a aula 10 inclusive.
Data da segunda prova:
Dia 26/06/2008.
Prova com consulta.
Matéria: da aula 11 à aula 21 inclusive.
Data da terceira prova (prova substitutiva opcional):
Dia 01/07/2008.
Prova com consulta.
Matéria: toda a matéria, da aula 1 até a aula 21 inclusive.
Demais informações: sobre sobre prazos de matrículas, trancamento, dias sem aula, etc. veja o
Calendário da Pós-Graduação para 2008.
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 (06/03/2008): 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 superior (upper bound) e cota inferior (lower bound). Exemplo de projeto de algoritmos eficientes para calcular o n-ésimo termo da sequência de Fibonacci. Slides sobre complexidade de algoritmos (continuação) (pdf 210K). Passar a Lista 1 de exercícios.
Aula 3 (11/03/2008): Listas lineares: pilha e fila. Conceito de tipos abstratos de dados. Encapsulamento e ocultamento de informação. Separação da especificação de um tipo de dado e da sua implementação. Alocação de memória sequencial. Representação de uma pilha em alocação sequencial: inserção e remoção. Slides sobre listas lineares (pdf 460K).
Aula 4 (13/03/2008): Representação de uma fila (circular) 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). Alocação ligada ou encadeada. Pilhas implementadas com alocação ligada. Slides sobre listas lineares - continuação (pdf 460K). Passar o . Programa 1.
Aula 5 (25/03/2008): Filas em alocação ligada. Várias maneiras alternativas 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. Slides sobre listas lineares - continuação (pdf 460K).
Aula 6 (01/04/2008): Passar Exercício 2 (em .html). 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. Aplicações da ordenação topológica. Um algoritmo eficiente para obter uma ordem topológica. Slides sobre listas lineares - continuação (pdf 460K).
Aula 7 (03/04/2008): Passar o Exercício 3 .pdf. Concluir o algoritmo de ordenação topológica. 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). Slides sobre Fila de Prioridade (pdf 136K).
Aula 8 (08/04/2008): Concluir o assunto fila de prioridade. Comentar o artigo de J. Stolfi sobre heapsort. Coletor de lixo (garbage collector) - 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. Slides sobre Coletor de lixo (garbage collector) (pdf 156K).
Aula 9 (10/04/2008): Concluir o assunto coletor de lixo. Árvore. Definições e exemplo. Nomenclatura sobre vários termos usados em árvores. Slides sobre árvores e árvores binárias (pdf 282K).
Aula 10 (22/04/2008): Passar o Programa 2: soma de duas matrizes esparsas usando cabeças de lista, e listas ortogonais. 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). Impressão de árvore por meio do procedimento printtree (usando uma ordem de percurso da árvore semelhante à in-ordem). Modos de percorrer uma árvore binária: pré-ordem, in-ordem. pós-ordem. Dar algoritmos recursivos e para o percurso pré-ordem e in-ordem. Slides sobre árvores e árvores binárias - continuação (pdf 282K).
Aula 11 (24/04/2008): Dar um algoritmo não recursivo (usando uma pilha) para percurso in-ordem. Comentar o percurso por nível ou por largura (breadth-first), que deve usar uma fila, e o percurso por profundidade (depth-first). 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. Slides sobre árvores e árvores binárias - continuação (pdf 282K).
Aula 12 (29/04/2008): Primeira prova.
Aula 13 (08/05/2008): Árvore binária de busca: conceitos e complexidade. Busca na árvore de busca (function loc). Inserção na árvore binária de busca. 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). Slides sobre árvore binária de busca (pdf 349K).
Aula 14 (13/05/2008): 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. Slides sobre árvore binária de busca (pdf 349K) - continuação.
Aula 15 (15/05/2008): Passar o Programa 3. 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. Slides sobre árvore binária de busca (pdf 349K) - continuação.
Aula 16 (20/05/2008): 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. Slides sobre árvore binária de busca ótima (pdf 362K).
Aula 17 (27/05/2008): 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. Slides sobre árvore binária de busca ótima (pdf 362K) - continuação.
Aula 18 (03/06/2008): Apresentar de forma sucinta o algoritmo da construção da árvore binária de busca ótima e discutir a sua complexidade. Slides sobre árvore binária de busca ótima (pdf 362K) - continuação.
Aula 19 (05/06/2008): Árvore rubro-negra: da classe de árvores binárias de busca ditas balanceadas. Definição e propriedades da árvore rubro-negra. Altura da árvore rubro-negra. Operações rotação: left-rotate e right-rotate. Complexidade das operações de rotação. Inserção em uma árvore rubro-negra. Slides sobre árvore rubro-negra (pdf 209K).
Aula 20 (10/06/2008): Inserção em uma árvore rubro-negra: rotina para re-arranjar a árvore caso a propriedade 2 ou 4 esteja violada. Discutir sem mostrar detalhes a operação de remoção. Slides sobre árvore rubro-negra - continuação (pdf 209K).
Aula 21 (12/06/08): 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. B-Árvores (pdf 431K).
Aula 22 (19/06/08): (Obs: Essa aula sobre LISP não entra nas provas.) Conceito da linguagem e uma pequena demonstração. Slides sobre a aula LISP (pdf 137K). Para quem quer brincar um pouco com o programinha nextterm.lsp, pode pegar o prorama aqui: nextterm.lsp. Execute-o no MuLISP com o comando (rds nextterm.lsp) depois do prompt $.
Aula 23 (26/06/08): Segunda Prova.
Aula 24 (01/07/08): Terceira Prova (opcional).