| #
| SLIDES DA AULA
| EXERCÍCIOS
| REF. BIBLIOGRÁFICA
|
| 1 | Introdução |
(exercícios) | CLRS - 1 |
| 2 | Revisão de Indução (Armadilhas de Indução) |
(exercícios) | Livros de Matemática Discreta, Wikipedia: (1) e essa figura |
| 3 | Corretude de Algoritmos Recursivos |
(exercícios) | |
| 4 | Corretude de Algoritmos Iterativos |
(exercícios) | |
| 5 | Revisão de Somatórios e Logaritmos |
(exercícios) | Wikipedia: (1) e (2) |
| 6 | Análise de Alg. Iterativos e InsertionSort |
(exercícios) | CLRS - 2.1, 2.2 |
| 7 | Notação Assintótica - O |
(exercícios) | CLRS - 3.1 e KT - 2.2 |
| 8 | Notação Assintótica - Ω e Θ |
(exercícios) | CLRS - 3.1 e KT - 2.2 |
| 9 | Mais sobre Algoritmos Iterativos |
(exercícios) | |
| 10 | Análise de Alg. Recursivos e MergeSort |
(exercícios) | CLRS - 2.3 |
| 11 | Mais sobre Algoritmos Recursivos |
(exercícios) | CLRS - 2.3 |
| 12 | Recorrências: Provando Soluções |
(exercícios) | CLRS - 4.3 |
| 13 | Recorrências: Adivinhando Possíveis Soluções |
(exercícios) | CLRS - 4.4, 4.5 |
| 14 | PROVA 1 |
| |
| 15 | Corretude de Algoritmos Aleatorizados: Verificando Polinômios |
(exercícios) | MU - 1.1 e 1.2, KT - 13.1 |
| 16 | Analisando Algoritmos Aleatorizados: Variáveis Aleatórias e Esperança |
(exercícios) | MU - 2.1, KT - 13.3 |
| 17 | QuickSort: Melhor Caso e Pior Caso |
(exercícios) | CLRS - 7.1, 7.2, 7.4 |
| 18 | QuickSort: Versão Aleatorizada |
(exercícios) | CLRS - 7.2, 7.3, 7.4 |
| 19 | Limitante Inferior para o Problema da Ordenação |
(exercícios) | CLRS - 8.1 |
| 20 | Reduções |
(exercícios) | Man - 10.1, 10.2, 10.4 |
| 21 | Problemas de Busca, a.k.a NP - Parte 1 |
(exercícios) | DPV - 8.1 |
| 22 | Problemas de Busca, a.k.a NP - Parte 2 |
(exercícios) | DPV - 8.1 |
| 23 | Classes P, NP, NP-Completo |
(exercícios) | DPV - 8.2 |
| 24 | Reduções de Problemas Difíceis |
(exercícios) | DPV - 8.3 |
| 25 | Redução de Cook-Levin e Considerações Finais |
(exercícios) | DPV - 8.3 |
| 26 | PROVA 2 |
| |
