—— Veja www.ime.usp.br/~pf/analise_de_algoritmos ——

 

Transparências de aulas
MAC0338 é uma continuação natural de MAC0122 (Princípios de Desenvolvimento de Algoritmos).  Aquela disciplina estuda algoritmos eficientes e elegantes para alguns problemas computacionais básicos. Nesta, o conceito de eficiência é quantificado e o "grau de eficiência" dos algoritmos é calculado com precisão (para valores grandes dos parâmetros).  Outro tema recorrente da disciplina: explorar a estrutura recursiva dos problemas para construir algoritmos elegantes e eficientes.   Exercícios preliminares: Piso, teto, log, lg, etc.  Introdução à AA  [CLR 1.1--1.2, CLRS 2.1--2.2, AU 3.3, AU 3.6] Análise assintótica: notação O [CLR 2.1, CLRS 3.1, AU 3.4] Análise de algoritmos iterativos [CLR 1.1--1.2, CLRS 2.1--2.2, AU 3.3, AU 3.6] Mais notação O [CLR 2.1, CLRS 3.1, AU 3.5] Delimitações inferiores e notação Omega [CLR 2.1, CLRS 3.1] Recursão [CLRS 2.7 e 2.9, AU2.6] Análise de algoritmos recursivos [CLR 1.3, CLRS 2.3, AU 2.8, AU 3.9--3.10] Recorrências. Recorrências com notação O [CLR 4.1--4.2, CLRS 4.1--4.2, AU 3.9, AU 3.11] Análise do Heapsort [CLR 7, CLRS 6] Filas com prioridade [CLRS 7.5, CLRS 6.5] Uma recorrência relevante para o Quicksort Análise do Quicksort [CLR 8, CLRS 7] Tempo médio do Quicksort [CLR 8.4, CLRS 7.4] Algoritmos probabilísticos e aleatorizados [CLR 6.6, CLRS 5 e CLRS C.2--C.3] Limite inferior para o problema de ordenação [CLR 9.1, CLRS 8.1] Ordenação em tempo linear [CLR 9.2--9.3, CLRS 8.2--8.3] i-ésimo menor elemento [CLR 10, CLRS 9] Programação dinâmica: multiplicação iterada de matrizes [CLR 16.1--16.3, CLRS 15.1--15.3]. Uma demonstração java do problema da mochila [encontrei na página da disciplina CISC365 do prof. Robin Dawes]. Programação dinâmica: subseqüência comum máxima [CLR 16.4, CLRS 15.4]. Demonstração java dos problemas da subseqüência comum máxima e da subseqüência crescente máxima [encontrei na página da disciplina CISC365 do prof. Robin Dawes]. Solução branch-and-bound para o problema da subseqüência crescente máxima. Algoritmos gulosos [CLR 17.2, CLRS 16.2] Mais algoritmos gulosos: intervalos disjuntos. Uma demonstração java do problema dos intervalos disjuntos [encontrei na página da disciplina CISC365 do prof. Robin Dawes]. Estrutura de dados para conjuntos disjuntos [CLR 22.1 e 22.3, CLRS 21.1 e 21.3] Árvores geradoras de peso mínimo (Kruskal e Prim) [CLR 24, CLRS 23] Análise amortizada [CLR 18, CLRS 17] As classes P e NP de problemas. Problemas completos em NP  [CLR 36, CLRS 34]