2 provas (50%+50%)
DATA | TÍTULO | AULAS | SLIDES | VIDEOS | ASSUNTOS | EXERCÍCIOS | REF. BIB. |
---|---|---|---|---|---|---|---|
17/mai | 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. | ||||||
17/mai | Revisão de Indução | (aula) | (slides) | (a) | Provas Matemáticas. Técnicas de provas. | (exercicios) | Livros de Mat. Discreta, Wikipedia e essa figura |
(b) | Indução: definição e algoritmo. | ||||||
(c) | Indução: exemplos. | ||||||
19/mai | 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. | ||||||
24/mai | Corretude de Algoritmos Iterativos | (aula) | (slides) | (a) | Corretude iterativa: passo-a-passo. | (exercicios) | |
(b) | Exemplo: Fibonacci. | ||||||
(c) | Exemplo: multiplicação. | ||||||
26/mai | Revisão de Somatórios e Logaritmos | (aula) | (slides) | (a) | Somatórios, notação e propriedades. | (exercicios) | Wikipedia: (1) e (2) |
(b) | Propriedades e exemplos. | ||||||
(c) | Exemplos. Logaritmos e propriedades. | ||||||
26/mai | 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. | ||||||
31/mai | Notação Assintótica O (1/2) | (slides) | (a) | Definição e convenções. | (exercicios) | CLRS - 3.1 e KT - 2.2 | |
(b) | Funções constantes e fatos úteis. | ||||||
(c) | Exemplo: série harmônica. | ||||||
02/jun | Notação Assintótica O (2/2) | (slides) | (a) | Simplificando equações assintóticas. | (exercicios) | CLRS - 3.1 e KT - 2.2 | |
(b) | Exemplo: log n! | ||||||
07/jun | Notação Assintótica Ω e Θ | (slides) | (a) | Notação Ω: definição e exemplos. | (exercicios) | CLRS - 3.1 e KT - 2.2 | |
(b) | Notação Θ: definição e exemplos. | ||||||
09/jun | Notação Assintótica o e ω | (slides) | (a) | Notação o (ózinho): definição e exemplos. | (exercicios) | CLRS - 3.1 e KT - 2.2 | |
(b) | Notação ω: definição e exemplos. | ||||||
14/jun | 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. | ||||||
21/jun | Complexidade de Tempo de Algoritmos Recursivos | (aula) | (slides) | (a) | Algoritmo Intercala (Merge) | (exercicios) | CLRS - 2.3 |
(b) | MergeSort. | ||||||
23/jun | 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. | ||||||
28/jun | 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. | ||||||
30/jun | 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. | ||||||
05/jul | 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. | ||||||
07/jul | Algoritmo de Karatsuba | (slides) | (a) | Algoritmo recursivo para multiplicação. | (exercicios) | DPV - 2.1 e KT - 5.5 | |
(b) | Análise de algoritmo e o Teorema Mestre. | ||||||
(c) | O algoritmo de Karatsuba e sua análise de complexidade. | ||||||
14/jul | Algoritmo de Strassen | (slides) | (a) | Algoritmo de Strassen (parte 1). | CLRS 4.2 e DPV - 2.5 | ||
(b) | Algoritmo de Strassen (parte 2). | ||||||