CI165-A - Análise de Algoritmos

2o semestre de 2014

2a e 4a as 17:30

sala PA 01


Ementa

  1. Conceitos básicos de análise de algoritmos.
  2. Corretude de Algoritmos
  3. Análise de Algoritmos Iterativos e Recursivos
  4. Notação Assintótica
  5. Relações de Recorrência
  6. Algoritmos Aleatorizados e Análise Probabilística.
  7. Reduções
  8. NP-Completude.

Bibliografia

  1. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (CLRS)
  2. Bibliografia Complementar

  3. Algorithm Design, Kleinberg e Tardos (KT)
  4. Algorithms, Dasgupta, Papadimitriou e Vazirani (DPV)
  5. Probability and Computing, Mitzenmacher e Upfal (MU)
  6. Introduction to algorithms : a creative approach, U. Manber (Man)

Avaliação

Sao 2 provas (P1, P2) com mesmo peso e conteúdo cumulativo e uma prova final (PF) sobre toda a matéria.


Nas provas, é permitido UM ÚNICO TIPO DE CONSULTA: uma folha A4, escrita A MÃO, frente e verso.

Notas

Calendário

Material das Aulas

# SLIDES DA AULA EXERCÍCIOS REF. BIBLIOGRÁFICA
1 Introdução (exercícios) CLRS - 1
2 Revisão de Somatórios e Logaritmos (exercícios) Wikipedia: (1) e (2)
3 Revisão de Indução e Apêndice (exercícios) Livros de Matemática Discreta, Wikipedia: (1) e essa figura
4 Corretude de Algoritmos Recursivos (exercícios)
5 Corretude de Algoritmos Iterativos (exercícios)
6 Análise de Alg. Iterativos e InsertionSort (exercícios) CLRS - 2.1, 2.2
7 Notação Assintótica - O (exercícios) CLRS - 3.1 e KT - 2.2
8 Notação Assintótica - Ω e Θ (exercícios) CLRS - 3.1 e KT - 2.2
9 Mais sobre Algoritmos Iterativos (exercícios)
10 Análise de Alg. Recursivos e MergeSort (exercícios) CLRS - 2.3
11 Mais sobre Algoritmos Recursivos (exercícios) CLRS - 2.3
12 Recorrências: Provando Soluções (exercícios) CLRS - 4.3
13 Recorrências: Adivinhando Possíveis Soluções (exercícios) CLRS - 4.4, 4.5
14 PROVA 1
15 Corretude de Algoritmos Aleatorizados: Verificando Polinômios (exercícios) MU - 1.1 e 1.2, KT - 13.1
16 Corretude de Algoritmos Aleatorizados: Corte Mínimo Global (exercícios) MU - 1.4, KT - 13.2
17 Analisando Algoritmos Aleatorizados: Variáveis Aleatórias e Esperança (exercícios) MU - 2.1, KT - 13.3
18 QuickSort: Melhor Caso e Pior Caso (exercícios) CLRS - 7.1, 7.2, 7.4
19 QuickSort: Versão Aleatorizada (exercícios) CLRS - 7.2, 7.3, 7.4
20 Limitante Inferior para o Problema da Ordenação (exercícios) CLRS - 8.1
21 Reduções (exercícios) Man - 10.1, 10.2, 10.4
22 Problemas de Busca, a.k.a NP - Parte 1 (exercícios) DPV - 8.1
23 Problemas de Busca, a.k.a NP - Parte 2 (exercícios) DPV - 8.1
24 Classes P, NP, NP-Completo (exercícios) DPV - 8.2
25 Reduções de Problemas Difíceis (exercícios) DPV - 8.3
26 Redução de Cook-Levin e Considerações Finais (exercícios) DPV - 8.3
27 Aula de Exercícios
28 PROVA 2

Horário de atendimento