CI1165 - Análise de Algoritmos

turma A

1º semestre - 2022


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)
  4. Probability and Computing, Mitzenmacher e Upfal (MU)

Avaliação

2 provas (50%+50%)

como ir bem nesta disciplina?

Material Extra

Aulas


DATA TÍTULO AULAS SLIDES VIDEOS ASSUNTOS EXERCÍCIOS REF. BIB.
09/jun 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.
13/jun 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.
20/jun Corretude de Algoritmos Iterativos (aula) (slides) (a) Corretude iterativa: passo-a-passo. (exercicios)
(b) Exemplo: Fibonacci.
(c) Exemplo: multiplicação.
21/jun 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.
27/jun 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.
28/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!
04/jul 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.
04/jul 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.
05/jul 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.
11/jul Complexidade de Tempo de Algoritmos Recursivos (aula) (slides) (a) Algoritmo Intercala (Merge) (exercicios) CLRS - 2.3
(b) MergeSort.
12/jul 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.
18/jul 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.
19/jul 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.
01/ago 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.
02/ago Divisão e Conquista: Algoritmo de Karatsuba e Teorema Mestre (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.
08/ago Divisão e Conquista: Algoritmo de Strassen (slides) (a) Algoritmo de Strassen (parte 1). CLRS 4.2 e DPV - 2.5
(b) Algoritmo de Strassen (parte 2).
09/ago Algoritmos Aleatorizados: Corretude (aula) Axiomas de Probabilidade. Algoritmo para Verificar igualdade entre Polinômios. (exercicios) MU - 1.1 e 1.2, KT - 13.1
16/ago Algoritmos Aleatorizados: Complexidade de Tempo (aula) Variáveis Aleatórias. Esperança. Complexidade de Tempo Esperada. (exercicios) MU - 2.1, KT - 13.3
18/ago QuickSort: Melhor Caso e Pior Caso (aula) (exercicios) CLRS - 7.1, 7.2, 7.4
23/ago QuickSort: Versão Aleatorizada (aula) (exercicios) CLRS - 7.2, 7.3, 7.4
25/ago BucketSort (aula) (exercicios) CLRS 4.2 e DPV - 2.5
30/ago Seleção Aleatorizada (aula) (exercicios) CLRS 4.2 e DPV - 2.5
01/set Tabelas Hash: Caso Esperado (aula) (exercicios) CLRS 4.2 e DPV - 2.5
06/set Árvores Binárias Construídas Aleatoriamente (aula) (exercicios) CLRS 4.2 e DPV - 2.5