MAC 323 - Estruturas de Dados - 1999 |
Departamento: Departamento de Ciência da Computação
Professor responsável: Siang Wun Song
Telefones: 818-6101, 818-6102
Sala do Professor: Sala 293 (2.o andar) ou Sala da Diretoria (sala 40 térreo) - Bloco A do IME
Monitores da disciplina: Não sei ainda.
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 3 Bloco B - Térreo - IME
Horário das aulas: 2.a feira 10 - 11:40 e 5.a feira 8:00 - 9:40
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
Bibliografia:
Regime de oferecimento: Cada semestre (1.o semestre de cada ano)
Duração: do final de fevereiro a ao início de julho
Carga horária semanal e número de créditos: 4 horas - 4 créditos
Calendário da Graduação para 1999.
Nota: ver Prova 1 de 1997.
Aula 1 (22/02/1999): Descrição do curso; homepage do curso.
Aula 2 (25/02/1999): Complexidade de algoritmos. Passar Exercício 1. Passar Programa 1.
Aula 3 (01/03/1999): Limite ou cota superior (upper bound) e limite ou cota inferior (lower bound). 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.
Aula 4 (04/03/1999): Listas lineares (.ps) : pilhas, filas.
Aula 5 (08/03/1999): Alocação sequencial. Pilhas e filas em alocação sequencial.
Aula 6 (11/03/1999): Alocação ligada ou encadeada. Comparação entre as duas representações sequencial e ligada.
Aula 7 (15/03/1999): Pilhas e filas em alocação ligada.
Aula 8 (18/03/1999): Algoritmos para várias pilhas compartilhando um espaço único, usando alocação sequencial. Comparação com o caso de alocação ligada.
Aula 9 (22/03/1999): Maneira de implementação da alocação ligada: linguagens que não possuem ponteiros e linguagens que possuem ponteiros. Listas circulares ligadas. Listas cicrulares com cabeças de lista. Exemplo: representação de matriz bidimensional esparsa.
Aula 10 (25/03/1999): Passar Exercício 2. Listas duplamente ligadas. 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 11 (05/04/1999): Ordenação topológica: um exemplo que ilustra o uso de estruturas de dados.
Aula 12 (08/04/1999): Passar Programa 2: Listas ligadas.. Concluir o algoritmo de ordenação topológica.
Aula 13 (12/04/1999): Aula a ser dada pelo Prof. Carlos Eduardo Ferreira. Assunto de grande interesse: não percam!
Aula 14 (15/04/1999): Aula a ser dada pelo Prof. Carlos Eduardo Ferreira. Assunto de grande interesse: não percam!
Aula 15 (19/04/1999): Fila de prioridade: conceitos e implementações. Implementação com um "heap". Idéias do algoritmo.
Aula 16 (22/04/1999): Implementação de fila de prioridade com um "heap". Algoritmos de inserção e remoção. Curiosidade apenas: Fila de prioridade usando computação paralela.
Aula 17 (26/04/1999): Primeira prova.
Aula 18 (29/04/1999): Motivação para estudar árvores. Árvore. Definições e exemplo.
Aula 19 (03/05/1999): Passar Programa 3: Árvores.. Nomenclatura sobre vários termos usados em árvores. Exemplos de uso de árvores: árvores de jogos (usadas em Inteligência Artificial). Construção de árvore de altura mínima, perfeitamente balanceada.
Aula 20 (06/05/1999): Impressão de árvore (usando uma ordem de percurso semelhante à in-ordem). Maneiras de percorrer uma árvore binária: pré-ordem, in-ordem, pós-ordem, por largura (breadth-first) e por profundidade (depth-first). Exemplos que usam as várias ordens de percurso, incluindo exemplos de árvores de jogos (como xadrez).
Aula 21 (10/05/1999): Mais um exemplo: Uso de percursos por largura (breadth-first) e profundidade (depth-first) na resolução de problemas em IA (busca no espaço de soluções). Árvore binária de busca: característica. Exemplo: dada uma árvore binária de busca, tente percorrer em in-ordem, veja o que ela produz.
Aula 22 (13/05/1999): Busca na árvore binária de busca, comentário sobre sua complexidade. Inserção na árvore binária de busca, comentário sobre sua complexidade.
Aula 23 (17/05/1999): 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.
Aula 24 (20/05/1999): Análise do desempenho médio para busca na árvore binária de busca. Explicação do método mini-max para busca da melhor jogada numa árvore de jogo. Passar Programa Otelo, que é opcional e substitui EP3 e EP4...
Aula 25 (24/05/1999): Árvore de busca AVL: definição de árvore balanceada, estrutura da pior árvore AVL (árvore de Fibonacci). Algoritmo de inserção em árvore de AVL. (Informação do Prof. Arnaldo Mandel: 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 26 (27/05/1999): Árvore de busca AVL: Algoritmo de inserção: necessidade de rebalanceamento e tipos de rebalanceamento.
Aula 27 (31/05/1999): Árvore de busca AVL: Algoritmo de remoção. Árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave.
Aula 28 (17/06/1999): Árvore de busca ótima - Obtenção pelo método de programação dinâmica: ilustração do método por um exemplo. Passar Programa 4..
Aula 29 (21/06/1999): Árvore de busca ótima - Obtenção pelo método de programação dinâmica: formalização do método. Uso da técnica de programação dinâmica para resolver um outro problema: multiplicação de n matrizes.
Aula 30 (24/06/1999): B-árvores, uma técnica para armazenamento e recuperação de grandes volumes de dados.
Aula 31 (30/06/1999): LISP: uma aula prática para mostrar a linguagem LISP, rodando vários exemplos.
Aula 32 (05/07/1999): Segunda Prova.