MAC324 - Estruturas de Dados para Engenharia

Poli/Elétrica - 1o. Semestre de 1999

Aulas

• 23/2/99 Discussão inicial sobre a disciplina. Discussão da ementa. Introdução a estruturas de dados. Vetores, crivo de Eratóstenes. O problema de Josephus. Solução fácil, com vetores, demora tempo proporcional a n log n. Existe um algoritmo de tempo linear?
• 25/2/99 Um algoritmo para o problema do Josephus com tempo de execução proporcional a mn: josephus.c. Usamos neste algoritmo a idéia de ponteiros. Em C, ponteiros podem ser implementadas de forma muito eficiente e transparente (será visto mais adiante). Estruturas em C. Dois exemplos: estrutura_simples.c e soma_complexos.c.
• 1/3/99 Vetores de estruturas, exemplo: vetor_complexo.c. Passagem de parâmetros por valor e endereço, exemplo: troca_complexos.c. Ponteiros para estruturas e alocação dinâmica de memória, exemplo: ponteiro_complexo.c. Para dar um pequeno nó na cabeça (é um bom exercício entender como funciona este programinha): troca_complexos2.c. Um desafio, ainda sobre Josephus (valendo meia-dúzia de Toblerones!).
• 4/3/99 Não houve aula.
• 8/3/99 Continuação da discussão sobre os exemplos de programas em C envolvendo estruturas e ponteiros (ponteiros para os exemplos discutidos encontram-se na entrada do dia 1/3/99).
• 11/3/99 Listas ligadas. Convenções para indicação de término de lista. Alocação de memória para elementos de listas ligadas (malloc()). Operações elementares sobre listas: inserção e remoção de elementos. Uma solução para o problema de Josephus. Como percorrer uma lista, como "inverter" uma lista, como ordenar uma lista. O uso de cabeça de listas [Seções 3.3 e 3.4 do livro de Sedgewick (3a. edição).]
• 15/3/99 Comentários sobre o desafio de Josephus (dicas aparecem no Volume 3, Sorting and Searching, da série da livros de Knuth, The Art of Computer Programming; procure "Josephus" no índice remissivo). Uma atualização do desafio: uma análise experimental bem feita do desempenho (eficiência) das solução sugeridas no livro de Knuth valem mais meia-dúzia de Toblerones! Voltando à vaca fria: algumas convenções para listas; listas com cabeça de lista e com NULL no campo next do último elemento, para indicação de fim de lista, listas sem cabeça de lista e com nesma convenção para término de lista, listas com cabeça e cauda. Interface para processamento de listas [list.h]. Exemplo de uso da interface para o problema de Josephus [Josephus_mais_abstracto.c]. Breve discussão sobre a implementação das funções cujos protótipos aparecem em list.h. [Seções 3.4 e 3.5 do livro de Sedgewick.]
• 18/3/99 [Em preparação] Programa para busca de padrões [Versão 1 | Versão 2 (versão com problemas de eficiência!)].
• 22/3/99 Funções básicas para processamento de strings [Tabela 3.2 do livro de Sedgewick].
  • Notícias sobre o desafio do Josephus. O Lennon Machado ficou de pôr a sua solução na lista, para admiração geral; acabei de receber uma solução de Mário Leston (um assistente da pós-graduação para esta disciplina). As soluções são basicamente as mesmas, mas vale a pena conferir! [Solução de Lennon Machado | Solução de Mario Leston] Uma coisa bacana sobre a solução do Mário é que há ponteiros para ponteiros nela, de forma que entendê-la é um exercício fortemente recomendado para aqueles que estão se familiarizando com ponteiros de C agora.
• 25/3/99 Discussão de um problema geométrico. Suponha que são dados um inteiro N e um real d com 0<d<1. Suponha que geramos N pontos uniformemente ao acaso no quadrado de lado unitário e que queremos determinar quantos pares destes pontos distam a menos de d entre si. Esta é a solução imediata para este problema: Programa 3.8 do livro de Sedgewick (Arquivos auxiliares: Point.h e Point.c). Esta solução tem tempo de execução proporcional a N^2. O mensagem central desta aula foi que o uso de estruturas de dados conveniente podem contribuir de forma essencial no projeto de algoritmos mais eficientes. Esta é a solução deste problema com tempo de execução proporcional a d^2N^2 (que é muito bom pelo fato de ser menor para valores menores de d): Programa 3.20 de Sedgewick. (Note que este programa também ilustra alocação dinâmica de memória para matrizes.) Uma observação: o Programa 3.20 acima gasta quantidade de memória proporcional a 1/d^2+N^2. Assim, existe um preço a pagar; para tirar proveito de valores pequenos de d, gastamos mais memória.
• 29/3/99 Semana Santa. Não houve aula.
• 1/4/99 Semana Santa. Não houve aula.
• 5/4/99 Tipos abstratos de dados; discussão genérica. Pilhas. A interface STACK.h. Exemplos de clientes: prog4.2.c (avaliação de expressões em notação pósfixa), prog4.3.c (transformação de expressões em notação infixa para pósfixa). Implementações: prog4.4.c (baseada em vetores), prog4.5.c (baseada em listas ligadas). Exercício: faça um programa que acopla os dois programas acima (4.2 e 4.3): o usuário especifica uma expressão infixa e o seu programa deve avaliar esta expressão.
• 8/4/99 Filas. Implementação de um tipo e rotinas que permitem o uso de várias filas simultaneamente: Item.h, QUEUE.c, QUEUE.h. Um exemplo de cliente: prog4.19.c; uma saída deste cliente: saida.txt. Capítulo 5 do Sedgewick . Recursão e Árvores. Exemplos iniciais de recursão: prog5.1.c (factorial()), prog5.2.c (puzzle()), prog5.3.c (Euclides).
• 12/4/99 Um exemplo mais sofisiticado de recursão: prog5.4.c (eval()). Exemplo de execução. Rotinas recursivas para manipulação de listas: prog5.5.c. Exercício fortemente sugerido: escreva uma versão iterativa de traverseR() (Sugestão. Use pilhas!). O problema das Torres de Hanói: prog5.7.c (hanoi()). Exercício fortemente sugerido: por que esta função recursiva para calcular números de Fibonacci é péssima? Breve discussão sobre o projeto.
• 15/4/99 Discussão sobre programação dinâmica: prog5.11.c, prog5.12.c, prog5.13.c. Introdução a árvores.
• 19/4/99 Breve discussão sobre tabelas de símbolos (veja a página de observações do projeto). Anúncio da possibilidade de entrega de duas versões do vip1. Árvores: prog5.17.c, prog5.18.c, prog5.19.c, prog5.20.c.
• 22/4/99 Continuação: prog5.20.c Exemplo de saída do prog5.20: prog5.20.saida.txt. Versões não-recursivas: prog5.15.c e prog5.16.c. Bom exercício sobre pilhas e filas. O que fazem estes programas não-recursivos? Bons exercícios envolvendo recursão e árvores. Escreva funções que, dada uma árvore, calcula o seu internal path length e o seu external path length. Escreva versões recursivas e não-recursivas! Árvores de busca binária (ABB). Tabela de símbolos baseada em ABBs: prog12.8.c. Veja este diretório para um exemplo de implementação de tabelas de símbolos baseada em ABBs.
• 26/4/99 Discussão dos exercícios da Lista de Exercícios de preparação para a primeira prova.
• 29/4/99 Primeira prova (com gabarito).
• 3/5/99 Tabela de símbolos baseada em ABBs (discussão detalhada): prog12.8.c. Veja este diretório para um exemplo de implementação de tabelas de símbolos baseada em ABBs. Tabela de símbolos baseada em ABBs aleatórias (início): veja este diretório para um exemplo de implementação de tabelas de símbolos baseada em ABBs aleatórias.
• 6/5/99 Tabela de símbolos baseada em ABBs aleatórias (continuação): veja este diretório para um exemplo de implementação de tabelas de símbolos baseada em ABBs aleatórias.
• 10/5/99 Tabelas de símbolos baseada em árvores splay: veja este diretório. Note que alterei o programa prog12.2.c de forma que ele agora pode imprimir a árvore produzida, usando uma variante do prog5.18.c. Ademais, inseri em ST.c o programa prog13.1.c, que faz um balanceamento explícito da árvore (baseado em prog12.14.c), de forma que você pode também imprimir uma versão totalmente balanceada da árvore produzida. Veja saida.txt para compilação e execuções. Uma página interessante com informações sobre ABBs do tipo splay é a seguinte: http://gs213.sp.cs.cmu.edu/prog/splay. Exercício fortemente recomendado [Sedgewick 13.27]: implemente STsearch() com splaying. Outro exercício. Estude este código, que é uma implementação de splay trees de Dan Sleator.
• 13/5/99 Splay trees: veja neste diretório a versão de ST.c onde implementei STsearch() com splaying (isto é, uma solução do exercício fortemente recomendado da aula passada). Veja aqui uma "simulação" para obter uma figura análoga à Figura 13.9 do livro de Sedgewick. Não deixem de ver http://gs213.sp.cs.cmu.edu/prog/splay! Neste local você pode brincar com um programa que tem interface gráfica para mostrar como funciona o processo de splaying. Exercício recomendado. Temos até o momento tabelas de símbolos implementadas com listas ligadas, com ABBs, com ABBs aleatórias, e com ABBs do tipo splay. Seria muito instrutivo você rodar o programa cliente prog12.2 com todas estas versões de ST.c, para comparar os respectivos desempenhos. Árvores 2-3-4 e árvores rubro-negras. Discussão inicial. Você já pode estudar a implementação de ABBs rubro-negras de Sedgewick neste diretório.
• 17/5/99 Árvores 2-3-4 e árvores rubro-negras (continuação). Exercício fortemente recomendado. Estude a implementação de ABBs rubro-negras de Sedgewick neste diretório!
• 20/5/99 Tabelas de espalhamento ("hashing"). Veja neste diretório uma implementação de tabelas de símbolos com hashing. Aqui, usamos resolução de colisões por encadeamento.
• 24/5/99 Tabelas de espalhamento ("hashing"). Veja neste diretório uma outra implementação de tabelas de símbolos com hashing. Aqui, resolvemos colisões por linear probing. Existe ainda double hashing; veja este diretório.
• 27/5/99 Hashing, continuação. Tabelas de hashing dinâmicas (discussão breve). Implementação.
• 31/6/99 Não houve aula (Yoshi fora de São Paulo).
• 3/6/99 Corpus Christi. Recesso escolar.
• 7/6/99 Aula de sobre C++ e elementos de orientação a objetos de Mário Leston (Yoshi fora de SP).
• 10/6/99 Aula de sobre C++ e elementos de orientação a objetos de Mário Leston, continuação (Yoshi fora de SP).
• 14/6/99 Heaps e heapsort. Vejam este diretório.
• 17/6/99 Heapsort (continuação) e quicksort. Vejam este diretório o quicksort.
• 21/6/99 Discussão sobre a lista de exercícios para a segunda prova.

Last modified: Tue Jun 22 20:08:21 EST 1999