Conteúdo da 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 3 MAR, QUA	Problema do Máximo Divisor Comum Algoritmo café-com-leite: invariantes; análise de correçao através de invariantes; Self-certifying algorithms. Algoritmo de Euclides (versão recursiva).
AULA 2 5 MAR, SEX	Problema do Máximo Divisor Comum Algoritmo de Euclides (versão recursiva): correção, análise de desempenho. Algoritmo de Euclides estendido: algoritmo self-certifying Programas para brincar: mdc.c, euclides-r.c, euclides-i.c, euclides-r-x.c, teste-drive.c.
AULA 3 10 MAR, QUA	Chão, log, teto, etc. Análise assintótica: O, Omega e Theta. Veja também Notação O. Delimitações inferiores e notação Omega. Introdução à análise de algoritmos: análise da ordenação por inserção. Veja também Introdução à AA.
AULA 4 12 MAR, SEX	Análise de algoritmos iterativos. Recursão. Veja também Recursão. Mergesort. Mais notação O. Mais delimitações inferiores: notação Omega.
AULA 5 17 MAR, QUA	Algoritmos por divisão e conquista. Mergesort. Recorrências.
AULA 6 19 MAR, SEX	Algoritmos por divisão e conquista e algoritmos híbridos. Mais recorrências. Recorrências com notação O. Análise de algoritmos recursivos.
AULA 7 24 MAR, QUA	Mais algoritmos por divisão e conquista: multiplicação de números inteiros gigantescos (algoritmo de Karatsuba - O(n^{lg 3})); e multiplicação de matrizes (algoritmo de Strassen - O(n^{lg 7})).
AULA 8 26 MAR, SEX	Heapsort: representação de árvores em vetores.
AULA 9 31 MAR, QUA	Heapsort (epílogo). Mais Heapsort.
AULA 10 2 ABR, SEX	PROVA 1.
RECESSO 7 ABR, QUA	Semana Santa. NÃO HAVERÁ AULA.
RECESSO 9 ABR, SEX	Semana Santa. NÃO HAVERÁ AULA.
AULA 11 14 ABR, QUA	Filas com prioridade Leftist heap.
AULA 12 16 ABR, SEX	Quicksort Mais Quicksort Tarefa 8
FERIADO 21 ABR, QUA	Tiradentes. NÃO HAVERÁ AULA.
AULA 13 13 ABR, SEX	Algoritmos probabilísticos "Teste driver" do algoritmo MÁXIMO e resultados de estudo experimental. Exercício relevante para o Quicksort Quicksort probabilístico "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 14 28 ABR, QUA	Quicksort probabilístico (continuação) Limite inferior para ordenação
AULA 15 30 ABR, SEX	Ordenação em tempo linear Estudos experimentais de algoritmos de ordenação incluindo o radixsort: resultados. "Teste driver" dos algoritmos de ordenação, incluindo o radix-sort. Tarefa 9
"BREAK" 5 MAI, QUA	Estudo individual. NÃO HAVERÁ AULA.
"BREAK" 7 MAI, SEX	Estudo individual. NÃO HAVERÁ AULA.
AULA 16 12 MAI, QUA	Programação dinâmica. 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 17 14 MAI, SEX	Mais programação dinâmica.
AULA 18 19 MAI, QUA	Mais programação dinâmica. 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 Subseqüência crescente máxima.
AULA 19 21 MAI, SEX	PROVA 2.
AULA 20 26 MAI, QUA	Problema da Mochila Implementação do algoritmo MOCHILA-BOOLEANA. Algoritmos gulosos.
AULA 21 28 MAI, SEX	Mais algoritmos gulosos
AULA 22 2 JUN, QUA	Busca de uma palavra em um texto: algoritmo KMP (Knuth, Morris e Pratt, CLRS cap. 32.4)
AULA 23 4 JUN, SEX	Busca de uma palavra em um texto (continuação): algoritmo KMP (CLRS cap. 32.4) Análise Amortizada (CLRS cap.17)
"BREAK" 9 JUN, QUA	Estudo individual. NÃO HAVERÁ AULA.
FERIADO 10 JUN, QUI	Corpus Christi. NÃO HAVERÁ AULA.
"BREAK" 11 JUN, SEX	Estudo individual. NÃO HAVERÁ AULA.
AULA 24 16 JUN, QUA	Complexidade Computacional. Proof Positive?.
AULA 25 18 JUN, SEX	Complexidade Computacional. Curiosidade: The Complexity Zoo (o Nelson me passou esse endereço).
AULA 26 23 JUN, QUA	Redução do problema do passeio hamiltoniano ao problema da satisfatibilidade. Diversão: The Mathematical Cartoons of Larry Gonick (o Nelson me passou esse endereço).
AULA 27 25 JUN, SEX	PROVA 3.
AULA 28 30 JUN, QUA
AULA 29 2 JUL, SEX
FIM 3 JUL, SAB	ENCERRAMENTO DAS AULAS.
NOTAS 12 JUL, SEG	Data máxima para entrega, pelos docentes, das listas de avaliação final do segundo semestre.
REC. 29 JUL, QUI	PROVA DE RECUPERAÇãO. Das 10:00 às 13:00 na sala 6 do bloco B.
NOTAS 06 AGO, SEX	Data máxima para que os docentes entreguem as listas de avaliação dos alunos que realizaram as provas de recuperação.

Página principal de Análise de Algoritmos.

Last modified: Thu Aug 19 18:55:53 BRT 2004