Algoritmos e Estruturas de Dados II, 2011/2012

Índice

Introduction to Algorithms no MIT OpenCourseWare

Podem ver aulas de algoritmos no MIT. Eles cobrem mais matéria do que nós, mas alguns dos tópicos são idênticos. As aulas estão espectaculares e estão disponíveis em video.

Apontamentos das aulas

Algumas das figuras e exemplos de grafos foram retirados de aulas do MIT OperCourseWare, acima referidas.

aula data tópico CLRS (3rd Ed.) CLRS (2nd Ed.) CLR (1st Ed.)
01 22/Fev/12 Apresentação da disciplina. (PDF)
Análise de algoritmos. Melhor caso, pior caso, caso médio. (PDF)
cap 1, 2.1, 2.2 cap 1, 2.1, 2.2 cap 1.1, 1.2
02 23/Fev/12 Crescimento de funções. Complexidade assimptótica. Notação O, Ω, Θ. (PDF) cap 3 cap 3 cap 2
-- 29/Fev/12 Não houve aula. Professor doente.
-- 01/Mar/12 Não houve aula. Professor doente.
03 07/Mar/12 Revisitando o Merge Sort. Divisão e Conquista. (PDF) cap 2.3 cap 2.3 cap 1.3
04 07/Mar/12 Recorrências: método iterativo e de expansão da árvore de recorrência (ver PDF da próxima aula). cap 4.4 cap 4.2 cap 4.2
05 08/Mar/12 Recorrências: Método de substituição, método de expansão da árvore de recorrência. (PDF)
Teorema Mestre. (PDF)
cap 4.3, 4.4, 4.5, 4.6 cap 4.1, 4.2, 4.3 cap 4.1, 4.2, 4.3
06 14/Mar/12 Divisão e conquista: Busca binária, quicksort, exponencial rápida, multiplicação de inteiros, algoritmo de Strassen para multiplicação de matrizes. (PDF) cap 2.3, 4.1, 4.2 cap 2.3, 28.2 cap 1.3, 31.2
07 15/Mar/12 Divisão e conquista: Par de pontos mais próximo. (PDF)
Algoritmos "greedy": selecção de actividades. (PDF)
cap 33.4
cap 16.1, 16.2, 16.3
cap 33.4
cap 16.1, 16.2, 16.3
cap 35.4
cap 17.1, 17.2, 17.3
08 21/Mar/12 Algoritmos "greedy": selecção de actividades. (continuação)
Programação dinâmica: Números de Fibonacci, coeficientes binomiais. (PDF)

cap 15

cap 15

cap 16
09 22/Mar/12 Programação dinâmica: Subsequência comum mais longa. (PDF)
cap 15

cap 15

cap 16
10 -- Análise amortizada. (PDF) cap 17 cap 17 cap 18
11 28/Mar/12 Grafos: definições básicas, representação. (PDF)
Procura em largura (BFS). (PDF)
cap 22.1, 22.2 cap 22.1, 22.2 cap 23.1, 23.2
12 29/Mar/12 Procura em profundidade (DFS). Componentes conexas. Ordenação topológica. (PDF) cap 22.3, 22.4 cap 22.3, 22.4 cap 23.3, 23.4
13 11/Abr/12 Árvores abrangentes de custo mínimo: propriedades, algoritmo genérico. (PDF) cap 23, 23.1 cap 23.1 cap 24.1
14 12/Abr/12 Árvores abrangentes de custo mínimo: algoritmos de Prim e Kruskal. (PDF) cap 23.2 cap 23.2 cap 24.2
15 18/Abr/12 Estruturas de dados para conjuntos disjuntos (Union-Find). (PDF) cap 21.1, 21.2, 21.3 cap 21.1, 21.2, 21.3 cap 22.1, 22.2, 22.3
16 19/Abr/12 Grafos: Caminho mais curto a partir de um nó. Algoritmos de Dijkstra e Bellman-Ford. (PDF) cap 24, 24.3, 24.1 cap 24, 24.3, 24.1 cap 25.1, 25.2, 25.4

Aulas/Trabalhos práticos

aula datas tópico
01,02 semana 1, 20/Fev/12 - 24/Fev/12 Escalabilidade empírica. Crescimento de funções. Complexidade assimptótica. (PDF)
-- semana 2, 27/Fev/12 - 02/Mar/12 Não houve aula. Professor doente.
03,04 semana 3, 05/Mar/12 - 09/Mar/12 Escalabilidade empírica. Revisões do método de indução matemática. Recorrências. Divisão e conquista. (PDF)
05,06 semana 4, 12/Mar/12 - 16/Mar/12 Divisão e conquista. (PDF)
07,08 semana 5, 19/Mar/12 - 23/Mar/12 Programação dinâmica. (PDF)
09,10 semana 6, 26/Mar/12 - 30/Mar/12 Programação dinâmica. (PDF)
11,12 semana 7, 09/Abr/12 - 13/Abr/12 Grafos. (PDF)
13,14 semana 8, 16/Abr/12 - 20/Abr/12 Discussão dos trabalhos.