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:
- 17/9/98 Continuação.
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:
- 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.
- 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].
Página principal de MAC122 (BCC - 2o. semestre de 1998).
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Fri Mar 26 12:11:28 EST 1999