CI337 - Algoritmos Aleatorizados

2o semestre de 2015

4a e 6a às 15:30

sala PC17


Ementa

  1. Eventos e Axiomas da Probabilidade
  2. Variáveis Aleatórias Discretas e Esperança
  3. Momentos e Desvios
  4. Limitantes de Chernoff
  5. Bolas e Cestos
  6. Grafos Aleatórios (se der tempo)

Bibliografia

  1. Probability and Computing, Mitzenmacher e Upfal (MU)
  2. Bibliografia Complementar

  3. Randomized Algorithms, Motwani e Raghavan (MR)
  4. Notes on Randomized Algorithms, James Aspnes (Asp) (link para conteúdo gratuito)
  5. Concentration of Measure for the Analysis of Randomized Algorithms, Dubhashi e Panconesi (DP)

Avaliação






O total de exercícios depende se é aluno de graduação ou pós-graduação:

IMPORTANTE: entregar os exercícios da aula em no máximo 7 dias após a aula.


Material das Aulas


DICA: Leve as notas de aula previamente impressas para a aula


# NOTAS DA AULA EXERCÍCIOS REF. BIBLIOGRÁFICA
1 Axiomas de Probabilidade (1 de 2) (exercícios) MU - 1.1 e 1.2
2 Axiomas de Probabilidade (2 de 2) (exercícios) MU - 1.1 e 1.2
3 Verificando Multiplicação de Matrizes (exercícios) MU - 1.3
4 Problema do Corte Mínimo (exercícios) MU - 1.4
5 Variáveis Aleatórias e Esperança (exercícios) MU - 2.1
6 Desig. Jensen, Variáveis Binomiais e de Bernoulli (exercícios) MU - 2.1 e 2.2
7 Esperança Condicional (exercícios) MU - 2.3
8 Distribuição Geométrica (exercícios) MU - 2.4
9 QuickSort Aleatorizado (exercícios) MU - 2.5
10 Desig. de Markov, Variância e Momentos de uma Var. Aleatória (exercícios) MU - 3.1 e 3.2
11 Variância e Momentos de uma Var. Aleatória (exercícios) MU - 3.2
12 Desigualdade de Chebyshev (exercícios) MU - 3.3
13 Algoritmo da Mediana (1 de 2) MU - 3.4
14 Algoritmo da Mediana (2 de 2) (exercícios) MU - 3.4
15 Funções Geradoras de Momento (exercícios) MU - 4.1
16 Limitantes de Chernoff (1 de 2) (exercícios) MU - 4.2
17 Limitantes de Chernoff (2 de 2) (exercícios) MU - 4.2
18 Limitantes Melhores para Casos Especiais (exercícios) MU - 4.3
19 Aplicação: Balanceamento de Conjunto MU - 4.4
20 Aplicação: Empacotamento de Itens Egoísta artigo
21 O Paradoxo do Aniversário, Bolas e Cestos (exercícios) MU - 5.1
22 Bolas e Cestos (exercícios) MU - 5.2
23 Distribuição de Poisson (1 de 2) (exercícios) MU - 5.3
24 Distribuição de Poisson (2 de 2) (exercícios) MU - 5.3
25 Aproximação de Poisson (1 de 2) MU - 5.4
26 Aproximação de Poisson (2 de 2) (exercícios) MU - 5.4
27 Aplicação: Hashing (1 de 2) (exercícios) MU - 5.5
28 Aplicação: Hashing (2 de 2) (exercícios) MU - 5.5

Horário de atendimento