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.
Os apontamentos este ano vão ser em tudo idênticos aos do ano passado e podem ser consultados em AED-II, 2010/2011.
| 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 | 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 |
| 11 | 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 |
| -- | -- | Análise amortizada. (Não dado nas aulas, matéria opcional.) (PDF) | cap 17 | cap 17 | cap 18 |
| 12 | 11/Abr/12 | Árvores abrangentes de custo mínimo: propriedades, algoritmo genérico. (PDF) | cap 23, 23.1 | cap 23.1 | cap 24.1 |
| 13 | 12/Abr/12 | Árvores abrangentes de custo mínimo: algoritmos de Prim e Kruskal. (PDF) | cap 23.2 | cap 23.2 | cap 24.2 |
| 14 | 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 |
| 15 | 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 |
| aula | datas | tópico |
|---|---|---|
| 01,02 | semana 1, 20/Fev/12 - 24/Fev/12 | Escalibilidade 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) |
| 10,11 | semana 7, 09/Abr/12 - 13/Abr/12 | Grafos. (PDF) |
| 12,13 | semana 8, 16/Abr/12 - 20/Abr/12 | Discussão dos trabalhos. |
Soluções de alguns exercícios do TP1 e TP2.