CI1165 - Análise de Algoritmos

Profs. Vignatti (turma A) e Murilo (turma B)

3º periodo especial - 2021


Bibliografia

  1. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (CLRS)
  2. Algorithm Design, Kleinberg e Tardos (KT)
  3. Algorithms, Dasgupta, Papadimitriou e Vazirani (DPV)

Avaliação

2 provas (50%+50%)

como ir bem nesta disciplina?

Aulas Assíncronas


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).