MAC122 - Princípios de Desenvolvimento de Algoritmos

BCC - 2o. Semestre de 1998

Aulas

• 4/8/98 [Yoshi na 2a. Escola de Probabilidade - não houve aula]
• 6/8/98 Apresentação geral e questionário sobre perfil dos alunos; o problema de Josephus: solução recursiva e solução baseada na representação binária de n.
• 11/8/98 Recursão. Implementação da recorrência do Josephus [ex1.c]. Implementação com operações de shift [ex2.c] (mais uma curiosidade). Fibonacci [ex3.c].
• 13/8/98 Mais exemplos de recursão: torres de Hanói [ex4.c (versão simples) | ex5.c (versao com simulação dos movimentos)]. Demonstração da correção do algoritmo. Número de movimentos executados pelo algoritmo para resolver o problema com n discos.
• 18/8/98 [Yoshi está fora do país por duas semanas; o prof. Coelho dá as aulas.] Função recursiva para soma de dígitos [ex7.c]. Simulação da solução para o Problema das Torres de Hanói [ex4.c | ex5.c].
• 20/8/98 [Aula do prof. Coelho] Problema. O Problema das Panquecas da Maratona de Programação Júnior. Se a pessoa pensa recursivamente a solução pode sair de uma maneira natural! [Solução] Outro exemplo: geração de permutações [ex6.c].
• 25/8/98 [Aula do prof. Coelho] Cálculo do número de partições de um inteiro [ex9.c]. Curvas de Hilbert [ex10.c].
• 27/8/98 [Aula do prof. Coelho] Um pouquinho de C.
• 1/9/98 Discussão abstrata sobre pilhas, filas e deques. Implementação seqüencial e implementação através de listas ligadas (discussão de alto nível).
• 3/9/98 Continuação.
• 8/9/98, 10/9/98 Semana da Pátria: não há aulas.
• 15/9/98 Começamos a discussão de vários tópicos:
  • A versão de Knuth e Levy de wc [wc.dvi | wc.ps | wc.pdf | wc.c (uma versão em C, sem comentários e endentado mecanicamente) | wc.w (para quem sabe ou quer aprender CWEB, a linguagem preferida de Knuth)].
  • Manual de CWEB [dvi | PostScript | pdf].
  • Algoritmo para ordenação topológica. Descrição detalhada. Implementação em CWEB [ex11.dvi | ex11.ps | ex11.pdf | ex11.w | ex11_modif.c].
• 17/9/98 Continuação.
  • Um outro exemplo de programa em CWEB. Este programa ordena as linhas de um texto [ex12.dvi | ex12.ps | ex12.pdf | ex12.w | ex12.c]
  Introdução a tabelas de espalhamento (hashing)
• 22/9/98 Tabelas de espalhamento (continuação): funções de espalhamento e resolução de colisões por encadeamento.
• 24/9/98 Tabelas de espalhamento. Exemplo de uso, implementação, e testes estatísticos:
  • O programa-exemplo [freq.dvi | freq.ps | freq.pdf | freq.w | freq.c]
  • Os resultados dos experimentos.
    • entrada1.txt (52k), saida1.txt (11k), saida1_ord.txt (11k)
    • entrada2.txt (136k), saida2.txt (19k), saida2_ord.txt (19k)
    • entrada3.txt (1192k), saida3.txt (1429k), saida3_ord.txt (1429k)
  • Versão 2 do programa [freq_v2.c]
    • Os resultados: saida1_v2.txt (11k), saida2_v2.txt (19k), saida3_v2.txt (1429k).
• 29/9/98 Árvores binárias de busca. Discussão teórica. Leituras recomendadas: Knuth, vol. 1, Seções 2.3, 2.3.1 (até o Algoritmo T), e vol. 3, Seção 6.2.2 (até Algoritmo T), Kernighan e Ritchie, Seção 6.5.
• 1/10/98 Árvores binárias de busca. Exemplo de uso, implementação, e testes estatísticos:
  • O programa-exemplo [freq_ABB.dvi | freq_ABB.ps | freq_ABB.pdf | freq_ABB.w]
  • Os resultados dos experimentos. Abaixo, os arquivos entrada*_unsrt.txt correspondem a entradas cujas linhas foram aleatoriamente (des)ordenadas. No terceiro exemplo abaixo, não incluímos o arquivo entrada3.txt (palavras de um dicionário), pois as palavras deste arquivo estão em ordem alfabética, e portanto formam uma péssima entrada para freq_ABB.
    • entrada1.txt (52k), saida1_ABB.txt (11k); entrada1_unsrt.txt (52k), saida1_unsrt.txt (11k).
    • entrada2.txt (136k), saida2_ABB.txt (19k); entrada2_unsrt.txt (136k), saida2_unsrt.txt (19k)
    • entrada3_unsrt.txt (1192k), saida3_unsrt.txt (1429k).
• 6/10/98 Continuação sobre árvores de busca binária e introdução à busca seqüencial.
  • Altura de uma árvore binária, profundidade média dos nós de uma árvore binária; relevância algorítmica destas quantidades para árvores binárias de busca. "Pior caso" e "caso médio" do desempenho de um algoritmo/programa. Conceituação intuitiva de árvore binária balanceada. Discussão sobre alguns detalhes do programa-exemplo freq_ABB acima.
  • Busca seqüêncial em uma tabela. Pior caso e caso médio.
• 8/10/98 Discussão geral sobre o EP3. Busca seqüencial (continuação). Uso de sentinela, busca em tabela ordenada. Tabelas com "auto-organização." Possíveis alterações do programa-exemplo [freq.dvi | freq.ps | freq.pdf | freq.w | freq.c]. Busca binária em uma tabela com acesso aleatório.
• 13/10/98 Primeira Prova [prova1.dvi | prova1.ps | prova1.pdf]
• 15/10/98 Caso médio da busca de uma chave presente em uma árvore binária de busca; análise do caso de busca com sucesso e sem sucesso. Comprimento total externo e comprimento total interno de uma árvore binária. Otimalidade da árvore binária completa (sem prova). Ordenação por seleção, heaps e heapsort (discussão inicial).
• 20/10/98 Heaps e heapsort, continuação. Implementação: ex12 com heaps [ex12_heap.dvi | ex12_heap.ps | ex12_heap.pdf | ex12_heap.w]. Para confronto, esta é uma variante do ex12 (que usa o quicksort) que conta o número de comparações entre chaves (como faz o ex12_heap): [ex12_conta.dvi | ex12_conta.ps | ex12_conta.pdf | ex12_conta.w]. Vocês podem testar estes programas com as entradas usadas para os programas freq e freq_ABB acima.
• 22/10/98 Correção da prova. [gabarito1.dvi | gabarito1.ps | gabarito1.pdf]
• 27/10/98 Heaps e heapsort (implementações como em Algorithms in C, de R. Sedgewick). Estimativa do número de comparações entre chaves. Filas de prioridade. Número de comparações entre chaves para as operações de inserção e remoção.
• 29/10/98 Heaps (continuação). Estimativa do número de comparações entre chaves para a operação de construção de um heap. Notação O. Exemplo de uso de filas de prioridade: merging de k seqüências ordenadas. Merging e Mergesort. O paradigma da divisão-e-conquista (breve discussão). Implementação para vetores. Exercício sugerido: implemente mergesort para listas ligadas!
• 3/11/98 [S. do S./Yoshi no DIMACS/IAS Workshop on Randomized and Derandomized Algorithms for Discrete Structures]
• 5/11/98 [S. do S./Plantão de dúvidas do Armando]
• 10/11/98 Merge e mergesort para listas ligadas. Esta é uma implementação simples do mergesort para listas: ex13.c. Rotinas para manipulação de listas com cabeça e cauda: ex14.c. Exemplo de uso de listas circulares, o problema de Josephus: Josephus.c.
• 12/11/98 Mergesort: duas demonstrações de que mergesort executa O(n log n) comparações entre chaves para ordenar n elementos (uma demonstração baseada na "árvore de recursão" e outra no princípio da indução finita). Limitante inferior para o número de comparações que qualquer algoritmo de ordenação, baseado em comparações, executa para ordenar uma entrada de n elementos. Observação: provas corrigidas podem ser examinadas com o monitor, durante o plantão de 12/11 (tabela de notas).
• 17/11/98 Ordenação em tempo linear. Recordação do limite inferior para qualquer algoritmo de ordenação baseado em comparações. Validade de um limite do mesmo tipo para o tempo médio (sem demonstração). Ordenação por distribuição: radix sort [radix.dvi | radix.ps | radix.pdf | radix.w | radix.c (programa gerado automaticamente, a partir do radix.w)]. A linearidade do tempo de execução do radix sort. Rotina simples para geração de entradas para testar ex13 (mergesort) e radix: numeros_aleat.c. Exercício-extra [extra.dvi | extra.ps | extra.pdf]. Gabarito [extra_res.dvi | extra_res.ps | extra_res.pdf]. Notas.
• 19/11/98 Quicksort. Recordação do paradigma de divisão-e-conquista. O algoritmo de partição do quicksort (versão de Dijkstra); discussão detalhada, simulação, etc. Exemplo de uso do quicksort [ex12.dvi | ex12.ps | ex12.pdf | ex12.w | ex12.c].
• 24/11/98 Quicksort (continuação). Um exemplo de implementação que pode ser compararado com mergesort e radixsort: ex15.c. Este programa imprime também o número de comparações feitas e uma aproximação para o valor esperado no caso de entradas aleatórias. Podemos usar numeros_aleat.c para simular tais entradas. Prova formal de correção do algoritmo de partição; uso de "invariantes". Número médio de comparações feitas por quicksort em uma entrada aleatória (sem prova). Problema da determinação do k-ésimo menor elemento de uma seqüência dada. Exercício fortemente sugerido: escreva uma função que resolve este problema do k-ésimo elemento usando o algoritmo de partição do quicksort.
• 26/11/98 Códigos de Huffman para compactação de arquivos. Discussão teórica. Enunciado do EP4.
• 1/12/98 Busca de padrões em textos. O método da força bruta (ex16.c). Ilustração de que, no pior caso, o algoritmo da força bruta executa em torno de NM comparações entre caracteres. O algoritmo de Knuth, Morris, e Pratt (KMP). Um programa que usa o algoritmo KMP é um simulador de um jogo de moedas, brevemente discutido em sala. Veja Opta-fun!. O programa é este: [fun_ver.dvi | fun_ver.ps | fun_ver.pdf | fun_ver.w].
• 3/12/98 Aulas de exercícios. O problema das expressões bem-formadas de parênteses. Este programa gera as expressões com um número dado de parênteses: expr_pbf.c. Uma versão mais eficiente da solução anterior é esta: expr_pbf2.c. Um bom exercício é experimentar e tentar entender a razão desta segunda versão ser mais eficiente. Verifique sua resposta aqui.
• 8/12/98 Segunda prova [prova2.dvi | prova2.ps | prova2.pdf]. Gabarito [gg2.dvi | gg2.ps | gg2.pdf].
• 10/12/98 Prova substitutiva [prova3.dvi | prova3.ps | prova3.pdf].

Last modified: Fri Mar 26 12:11:28 EST 1999