MAC 323 - Estruturas de Dados - 2004 |
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 (sala) ou 3091-6135 (secretaria)
Sala do Professor: Sala 293 (2.o andar) - Bloco A do IME
Monitor da disciplina: Djogo Patrão (Email: djogo at vision. ime. usp. br)
Disciplina oferecida: ao Bacharelado de Ciência da Computação - IME
Pré-requisitos: Boa experiência em programação, em Pascal ou C.
Local das aulas: Sala 2 Bloco B - Térreo - IME
Horário das aulas: 3.a feira 14 - 16 h e 5.a feira 8 - 10 h
Bibliografia:
Programa:
Tipo de aulas: Aulas teóricas e práticas
Critérios de avaliação:
Duas provas P1 e P2 (mais uma terceira opcional): dando média P
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
(Apenas para o reprovados com condições de fazer recuperação.)
Uma prova de recuperação dando uma nota denominada P.
O aluno pode completar, se quiser, os exercícios e programas não entregues no semestre regular.
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 na recuperação"
senão A = (0.5 E + 3.5 Pg + 6 P )/10 Com A >= 5 o aluno está "aprovado na recuperação".
Regime de oferecimento: Cada semestre (1.o semestre de cada ano)
Duração: 25 de fevereiro a 29 de junho de 2002
Carga horária semanal e número de créditos: 4 horas - 4 créditos
Calendário da Graduação para 2004.
Dia 12 de agosto (quinta feira) as 12 horas.
Local: a ser marcado (ver nesta página).
ATENÇÃO 1: os programas podem ser feitos em DUPLA.
ATENÇÃO 2: podem ser usadas linguagens C, C++, Java ou Pascal.
ATENÇÃO 3: O que é para entregar?
Voce deve entregar (pode ser listagens em papel ou enviar os respectivos arquivos
por email para song@ime.usp.br):
1. Uma listagem (ou arquivo) com o programa fonte e
2. uma listagem (ou arquivo) com
alguns testes e suas respostas, isto é, com
algumas entradas e suas respectivas saídas que permitem
verificar que o programa está de fato funcionando de acordo.
Não entreguem o diskette.
Aula 2 (04/03/04): Importância de estudar a complexidade de algoritmo; pior caso, caso médio e pior caso; notação O e Omega; limite superior e limite inferior. Um livro excelente que ensina como programar bem (já visando uma boa complexidade durante o projeto do algoritmo) é Jon Bentley, Programming Pearls, 2nd Edition, Addison-Wesley, 2000. (Tem na biblioteca do IME.) Passar Exercício 1 (entregar até 18/03/2004).
Aula 3 (09/03/2004): Conceito de pior caso, melhor caso e caso médio, onde a complexidade depende das particulares instâncias da entrada. Listas lineares (.ps) ou em pdf (.pdf): pilhas, filas. Destacar a diferença entre a especificação ou definição de uma estrutura de dados e sua representação/implementação. Alocação sequencial. Representação de uma pilha em alocação sequencial.
Aula 4 (11/03/2004): Várias pilhas em alocação sequencial, visando compartilhamento de um espaço único: problemas de rearranjo custoso que pode envolver grande movimentação de dados. Fila circuluar em alocação sequencial. Discussão crítica da vantagem e desvantagem da alocação sequencial.
Aula 5 (16/03/2003): Alocação ligada ou encadeada. Pilhas em alocação ligada. Passar o Programa 1. Filas em alocação ligada. Maneira de implementação da alocação ligada: linguagens que não possuem ponteiros e linguagens que possuem ponteiros.
Aula 6 (18/03/2004): 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. Lista circular com cabeça de lista. 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 7 (23/03/2004): 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. Exemplo de aplicação em engenharia (atividades onde há precedências entre alguns pares delas).
Aula 8 (25/03/2004): Idéia do algoritmo para obter uma ordenação topológica: número de predecessores e lista de sucessores, usar uma estrutura de dados (uma fila) para guardar os elementos com zero número de predecessores.
Aula 9 (30/03/2004): Apresentar o algoritmo completo para obter uma ordenação topológica.
Aula 10 (01/04/2004): 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. Algoritmo de inserção: complexidade O(log n).
Aula 11 (13/04/2004): Fila de prioridade implementada com um heap. Algoritmo de remoção: complexidade O(log n). Passar o Programa 2: soma de duas matrizes esparsas usando cabeças de lista, e listas ortogonais.
Aula 12 (15/04/2004): 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.
Aula 13 (20/04/2004): 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 14 (22/04/2004): Árvores, definições e exemplos, motivação para estudar árvores. Exemplos de uso de árvores: árvores de jogos (usadas em Inteligência Artificial).
Aula 15 (27/04/2004): Árvore: nomenclaturas - árvore ordenada, raiz, pai, filho, nível, grau, descendente, ancestral, nó interno, folha. Árvore binária. Algoritmos para percorrer uma uma árvore binária: pré-ordem, in-ordem (ou ordem simétrica), pós-ordem. 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.
Aula 16 (29/04/2004): Primeira Prova.
Aula 17 (11/05/2004): Conversão de uma floresta de árvores genéricas (com qualquer número de filhos) para uma árvore binária. Demonstrar que uma árvore binária de n nós tem n+1 apontadores para nil. Árvore binária com costura ( threaded binary tree): aproveitamento dos ponteiros nil para ajudar no percurso da árvore em algum ordem (exemplo: ordem simétrica ou in-ordem). Exemplo.
Aula 18 (18/05/2004): Dada uma árvore binária com costura à diretira, mostrar como 1) obter o primeiro nó visitado no percurso em ordem simétrica 2) dado um ponteiro pt1 a um nó, fazer o ponteiro pt2 apontar ao próximo nó em ordem simétrica. Transformar uma árvore binária sem costura em uma com costura à direita. (obs: não passei lista; presença coletiva :-)
Aula 19 (20/05/2004): Árvore binária de busca. Algoritmos de busca e de inserção. Complexidade. Passar o Programa 3.
Aula 20 (25/05/2004): Remoção da árvore binária de busca: dar apenas a idéia. 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. Árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave.
Aula 21 (27/05/2004): Dadas as frequências de acessos das n chaves, computar a árvore binária de busca ótima pelo método de programação dinâmica: caso mais geral: conhecidas as chaves e suas probabilidades de acesso a cada chave ki pi e probabilidades de fracasso q. Mostrar exemplos.
Aula 22 (01/06/2004): 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 (3/6/2004): 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 24 (17/06/2004): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL (árvore de Fibonacci).
Aula 25 (22/06/2004): 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) B-árvores, uma técnica para armazenamento e recuperação de grandes volumes de dados. Busca e inserção em B-árvores.
Aula 26 (24/06/2004): 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 27 (29/06/2004): Segunda Prova.
Aula 28 (13/7/2004): Terceira Prova. Toda a matéria. LISP não vai entrar.