MAC 323 - Estruturas de Dados - 2002 |
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
Monitora da disciplina: Danielle Passos de Ruchkys
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 9 Bloco B - Térreo - IME
Horário das aulas: 3.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: 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 2002.
ATENCAO: os programas podem ser feitos em DUPLA.
Aula 1 (26/02/2002): Descrição do curso: por que usar estruturas de dados? Homepage do curso.
Aula 2 (28/02/2002): Conceito de complexidade de algoritmos: tempo medido indiretamente pelo número de operações mais relevantes; complexidade em função do tamanho da entrada; notação O, importância de estudar a complexidade de algoritmo; pior caso, caso médio e pior caso. Passar Exercício 1 (entregar até dia 19 de março de 2002).
Aula 3 (12/03/2002): Conceito de cota ou limite superior (upper bound) e cota ou limite 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 (14/03/2002): Listas lineares (.ps) ou em pdf (.pdf): pilhas, filas. Alocação sequencial. Representação de uma pilha em alocação sequencial.
Aula 5 (19/03/2002): 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. Crítica da alocação sequencial.
Aula 6 (21/03/2002): (Não foi dada matéria normal da disciplina, por haver poucos alunos.) A aula foi usada para discutir assuntos de interesse como uma breve introdução sobre redes neurais, sobre sistemas híbridos, e sobre programas que jogam xadrez ou otelo.
Aula 7 (2/4/2002): Alocação ligada ou encadeada. Comparação entre as duas representações sequencial e ligada. Pilhas em alocação ligada. Passar o Programa 1.
Aula 8 (4/4/2002): Filas em alocação ligada. Maneira de implementação da alocação ligada: linguagens que não possuem ponteiros e linguagens que possuem ponteiros. Listas circulares ligadas. Passar o Exercício 2.
Aula 9 (16/04/2002): Listas cicrulares com cabeças de lista. Exemplo: representação de matriz bidimensional esparsa. 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 10 (18/04/2002): Ordenação topológica: um exemplo que ilustra o uso de estruturas de dados.
Aula 11 (23/04/2002): Fila de prioridade: conceitos e implementações. Implementação com um "heap". Representação de um heap com um vetor.
Aula 12 (25/04/2002): Passar Exercício 3 (em postscript .ps) (em .pdf) Passar Programa 2 (em postscript .ps) (em .pdf) (Dicas sobre esse programa a serem dadas em classe, na aula depois da primeira prova.) Fila de prioridade implementada com um heap: Algoritmos de inserção e remoção. Comentar Lista de Exerc. 3.
Aula 13 (30/04/2002): Primeira Prova.
Aula 14 (02/05/2002): Break.
Aula 15 (14/05/2002): Processamento de listas; processamento simbólico. Comentar sobre o exercício programa no. 2, sobre átomos, listas, e sua representação.
Aula 16 (16/05/2002): 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.
Aula 17 (21/05/2002): Motivação para estudar árvores. Árvore. Definições e exemplo. 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 18 (23/05/2002): Impressão de árvore (usando uma ordem de percurso semelhante à in-ordem). Maneiras de percorrer uma árvore binária: pré-ordem.
Aula 19 (04/06/2002): Maneiras de percorrer uma árvore binária: pré-ordem, in-ordem, pós-ordem. Dar algoritmos recursivos e para o percurso in-ordem dar um algoritmo também não recursivo, usando uma pilha. Comentar o percurso por nível ou por largura (breadth-first), que deve usar uma fila. Busca na árvore binária de busca, comentário sobre sua complexidade.
Aula 20 (06/06/2002): Inserção na árvore binária de busca, comentário sobre sua complexidade. 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. Comentar sobre o desempenho médio para busca na árvore binária de busca. Passar Programa 3 ( Atenção: Quem fizer o EP do Prof. Ernesto, a nota daquele programa já vale para este programa, isto é, não precisa fazer este programa 3.)
Aula 21 (11/06/2002): Dada pelo Prof. Carlos Eduardo Ferreira, sobre estruturas de dados para representação de grafos (matriz de adjacências, matriz de incidência e listas de adjacências). Como exemplo: mostrar como a complexidade do algoritmo de percorrer os vértices de um grafo em largura muda conforme o tipo de estrutura utilizada. Mostrar algoritmos para os seguintes problemas em grafos: - dado um grafo G, e dois vértices u, v decida se existe caminho no grafo que liga u a v - dado um grafo G, decida se G é um grafo bipartido. (Observação: a matéria dessa aula não vai cair nas provas.)
Aula 22 (18/06/2002): Á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: 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) Conceito de árvore de busca ótima: conhecidas as probabilidades de acesso de cada chave.
Aula 23 (20/06/2002): B-árvores, uma técnica para armazenamento e recuperação de grandes volumes de dados. Busca e inserção em B-árvores. Hash table (tabela de espalhamento): idéia, função hash, colisão e seu tratamento.
Aula 24 (25/06/2002): Segunda Prova.
Aula 25 (02/07/2002): Terceira Prova opcional.