CI1165 - Análise de Algoritmos

turma A

1º semestre - 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.
20/set 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.
20/set 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.
22/set 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.
27/set Corretude de Algoritmos Iterativos (aula) (slides) (a) Corretude iterativa: passo-a-passo. (exercicios)
(b) Exemplo: Fibonacci.
(c) Exemplo: multiplicação.
29/set 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.
29/set 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.
04/out 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.
06/out 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!
11/out 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.
13/out 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.
18/out 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.
25/out Complexidade de Tempo de Algoritmos Recursivos (aula) (slides) (a) Algoritmo Intercala (Merge) (exercicios) CLRS - 2.3
(b) MergeSort.
27/out 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.
01/nov 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.
03/nov 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.
08/nov 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.
10/nov 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.
15/nov Algoritmo de Strassen (slides) (a) Algoritmo de Strassen (parte 1). CLRS 4.2 e DPV - 2.5
(b) Algoritmo de Strassen (parte 2).