| Introdução |
|
(slides) |
(a) |
Motivação. Formas simplistas de análise. |
(exercicios) |
CLRS - Cap. 1 |
| (b) |
Análise simples do SelectionSort. |
| (c) |
Limitações de análise experimental. Problemas Computacionais. Computação ≠ tecnologia. |
| (d) |
Abordagem de pior caso. Tamanho de instâncias. Modelos Computacionais. |
| | | | | | |
| Corretude de Algoritmos Recursivos |
(aula) |
(slides) |
(a) |
Visão Geral. Testes experimentais X prova de corretude. Corretude recursiva: ideia. |
(exercicios) |
|
| (b) |
Exemplo: Fibonacci. |
| (c) |
Exemplo: máximo de vetor. |
| (d) |
Exemplo: multiplicação. |
| | | | | | |
| Corretude de Algoritmos Iterativos |
(aula) |
(slides) |
(a) |
Corretude iterativa: passo-a-passo. |
(exercicios) |
|
| (b) |
Exemplo: Fibonacci. |
| (c) |
Exemplo: multiplicação. |
| | | | | | |
| Complexidade de Tempo (Ingênua) de Algoritmo Iterativos |
(aula) |
(slides) |
(a) |
InsertionSort e complexidade de tempo. |
(exercicios) |
CLRS - 2.1 e 2.2 |
| (b) |
InsertionSort: contagem das instruções básicas. |
| (c) |
InsertionSort: melhor caso. |
| (d) |
InsertionSort: pior caso. |
| (e) |
Complexidade assintótica: intuição. |
| | | | | | |
| Notação Assintótica (1/3) |
(aula) |
(slides) |
|
|
(exercicios) |
CLRS - 3.1 e KT - 2.2 |
| | | | | | |
| Notação Assintótica (2/3) |
(aula) |
(slides) |
|
|
(exercicios) |
CLRS - 3.1 e KT - 2.2 |
| | | | | | |
| Notação Assintótica (3/3) |
(aula) |
(slides) |
|
|
(exercicios) |
CLRS - 3.1 e KT - 2.2 |
| | | | | | |
| Complexidade de Tempo de Algoritmos Iterativos |
(aula) |
(slides) |
(a) |
Tempo de Execução: definição. Análise justa (apertada). |
(exercicios) |
|
| (b) |
Regras de simplificação. Truques. Observações e pegadinhas. |
| | | | | | |
| Complexidade de Tempo de Algoritmos Recursivos |
(aula) |
(slides) |
(a) |
Algoritmo Intercala (Merge) |
(exercicios) |
CLRS - 2.3 |
| (b) |
MergeSort. |
| | | | | | |
| Algoritmos Recursivos e Relações de Recorrência |
(aula) |
(slides) |
(a) |
Extraindo recorrências: passo-a-passo. |
(exercicios) |
CLRS - 2.3 |
| (b) |
Extraindo recorrências: exemplos. |
| (c) |
Multiplicação: extraindo, "resolvendo" e provando a recorrência. |
| | | | | | |
| Recorrências: Provando Soluções |
(aula) |
(slides) |
(a) |
Visão geral. Exemplo de prova. |
(exercicios) |
CLRS - 4.3 |
| (b) |
Base da indução e notação assintótica. |
| (c) |
Encontrando as constantes. Limitantes folgados e possíveis erros. |
| (d) |
Chutando soluções. Sutilezas da prova por indução. |
| | | | | | |
| Resolvendo Recorrências: Método da Iteração |
(aula) |
(slides) |
(a) |
Método da Iteração. Solução de recorrências exatas X assintóticas. |
(exercicios) |
CLRS - 4.4 |
| (b) |
Método da Iteração: exemplo. |
| (c) |
Método da Iteração: exemplo. |
| (d) |
Removendo pisos e tetos. Provando o "chute" encontrado. |
| | | | | | |
| Resolvendo Recorrências: Método da Árvore de Recorrência |
(aula) |
(slides) |
(a) |
Ideia do método. Exemplo de aplicação. |
(exercicios) |
CLRS - 4.5 |
| (b) |
Provando a solução. Recorrências e notação assintótica. |
| | | | | | |
| Divisão e Conquista: Algoritmo de Karatsuba e Teorema Mestre |
(aula) |
(slides) |
|
|
(exercicios) |
DPV - 2.1 e KT - 5.5 |
| | | | | | |
| Algoritmos Aleatorizados: Corretude |
(aula) |
(slides) |
(a) |
Problema: equivalência de polinômios. |
(exercicios) |
MU - 1.1 e 1.2, KT - 13.1 |
| (b) |
Equivalência de polinômios: erro e análise informal. |
| (c) |
Axiomas de Probabilidade. |
| (d) |
Limitante da União, Princípio da Inclusão-Exclusão, Independência. |
| (e) |
Algoritmo VP: diminuindo a probabilidade de erro. |
| (f) |
Gerador de Congruência Linear. |
| | | | | | |
| Algoritmos Aleatorizados: Complexidade de Tempo |
(aula) |
(slides) |
(a) |
Variáveis Aleatórias. |
(exercicios) |
MU - 2.1, KT - 13.3 |
| (b) |
Esperança, Linearidade da esperança. |
| (c) |
Exemplo: esperando o primeiro sucesso. |
| (d) |
Exemplo: adivinhando cartas. |
| (e) |
Exemplo: colecionador de cupons. |
| (f) |
Tempo de execução de algoritmos aleatorizados. |
| | | | | | |
| QuickSort: Melhor e Pior Caso |
(aula) |
(slides) |
(a) |
QuickSort: algoritmo. |
(exercicios) |
CLRS - 7.1, 7.2, 7.4 |
| (b) |
QuickSort: análise. |
| | | | | | |
| QuickSort: Versão Aleatorizada |
(aula) |
(slides) |
(a) |
Caso Médio e Aleatorizado. QuickSort Aleatorizado. |
(exercicios) |
CLRS - 7.2, 7.3, 7.4 |
| (b) |
Análise (pt. 1). |
| (c) |
Análise (pt. 2). |
| | | | | | |