Conteúdo das Aulas

"A good algorithm is like a sharp knife:
it does what it is supposed to do with a minimum amount of applied effort.
Using the wrong algorithm to solve a problem is like trying to cut a steak with a screwdriver:
you may eventually get a digestible result,
but you will expend considerably more effort than necessary,
and the result is unlikely to be aesthetically pleasing."
—Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms

Calendário Escolar da USP

AULA 1 23 AGO, SEG	Introdução à Análise de Algoritmos. Veja também a página Introdução à análise de algoritmos: análise da ordenação por inserção..
AULA 2 25 AGO, QUA	Notação assintótica. Análise com notação assintótica O. Mais notação assintótica.
AULA 3 30 AGO, SEG	Mais análise com notação `O`, Irmãos de `O` (`Omega` e `Theta`), Recursão, Divisão-e-conquista. Veja também Análise assintótica: O, Omega e Theta.
AULA 4 1 SET, QUA	Recursão, Divisão-e-conquista (continuação), Recorrências.
"BREAK" 6 SET, SEG	Estudo individual. NÃO HAVERÁ AULA.
"BREAK" 8 SET, QUA	Estudo individual. NÃO HAVERÁ AULA.
AULA 5 13 SET, SEG	Recorrências (continuação) e Recorrências com notação assintótica.
AULA 6 15 SET, QUA	Técnicas em projeto de algoritmos.
AULA 7 20 SET, SEG	Mais análise de algoritmos recursivos. Aqui vocês encontram um arquivo postscript com as aulas 1 a 7. Use, por exemplo, o `psnup` para condensar várias páginas em uma como você bem entender.
AULA 8 22 SET, QUA	Ordenação por seleção, Heapsort e Filas com prioridades [ps.gz].
AULA 9 27 SET, SEG	Quicksort [ps.gz]. "Teste driver" de vários algoritmos de ordenaçao. Estudos experimentais de algoritmos de ordenação: resultados 1, resultados 2, resultados 3, resultados 4.
AULA 10 28 SET, QUA	PROVA 1[ps.gz].
AULA 11 4 OUT, SEG	Análise probabilísticos e algoritmos aleatorizados [ps.gz].
AULA 12 6 OUT, QUA	Quicksort aleatorizado e limite inferior para ordenação [ps.gz].
"BREAK" 11 OUT, SEG	Estudo individual. NÃO HAVERÁ AULA.
"BREAK" 13 OUT, QUA	Estudo individual. NÃO HAVERÁ AULA.
AULA 13 18 OUT, SEG	Ordenação em tempo linear e seleção em tempo esperado linear. [ps.gz].
AULA 14 20 OUT, QUA	Seleção em tempo linear. [ps.gz].
AULA 15 25 OUT, SEG	Programação Dinâmica [ps.gz]. Implementação do algoritmo REC-MAT-CHAIN. Resultado da aplicação do algoritmo REC-MAT-CHAIN para obter a seqüência ótima de ordenação de 3 matrizes. Resultado da aplicação do algoritmo REC-MAT-CHAIN para obter a seqüência ótima de ordenação de 6 matrizes (eu tinha colocado 10, mas o arquivo ficava com 689826 bytes). Implementação do algoritmo MATRIX-CHAIN-ORDER.
AULA 16 27 OUT, QUA	Mais programação dinâmica [ps.gz]. Implementação do algoritmo LCS-LENGTH. Veja também Sequence Comparison: Some Theory and Some Practice de Imre Simon. Veja aqui o resultado da aplicação de `"diff -u"` aos arquivos abracadabra e yabbadabbadoo: meu_prompt>diff -u abracadabra yabbadabbadoo
"RECESSO" 1 NOV, SEG	RECESSO ESCOLAR. NÃO HAVERÁ AULA.
AULA 17 3 NOV, QUA	Problema booleano da mochila e algoritmos gulosos [ps.gz].
AULA 18 8 NOV, SEG	Mais algoritmos gulosos e análise amortizada [ps.gz].
AULA 19 10 NOV, QUA	PROVA 2 [ps.gz].
FERIADO 15 NOV, SEG	Proclamação da República. NÃO HAVERÁ AULA.
"BREAK" 17 NOV, QUA	Estudo individual. NÃO HAVERÁ AULA.
AULA 20 22 NOV, SEG	Mais análise amortizada e busca de uma palavra em um texto [ps.gz].
AULA 21 24 NOV, QUA	Busca de uma palavra em um texto [ps.gz].
AULA 22 29 NOV, SEG	Estruturas de dados para conjuntos disjuntos dinâmicos [ps.gz].
AULA 23 1 DEZ, QUA	Mais estruturas de dados para conjuntos disjuntos dinâmicos [ps.gz].
AULA 24 6 DEZ, SEG	Máximo divisor comum e complexidade computacional [ps.gz].
AULA 25 8 DEZ, QUA	Mais complexidade computacional [ps.gz].
AULA 26 13 DEZ, SEG	Mais complexidade computacional e algoritmos de aproximação [ps.gz].
AULA 27 15 DEZ, QUA	PROVA 3 [ps.gz].
FIM	ENCERRAMENTO DAS AULAS.

Página principal de Análise de Algoritmos.

Last modified: Tue Mar 1 20:17:17 EST 2005