provas de pesos iguais
| TÍTULO | AULAS | SLIDES | VIDEOS | ASSUNTOS | EXERCÍCIOS | REF. BIB. |
|---|---|---|---|---|---|---|
| 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). | |||||