CI337 - Algoritmos Aleatorizados

1o semestre de 2017

2a e 4a às 17:30

salas PA05 (2a) e PC17 (4a)


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

  2. Randomized Algorithms, Motwani e Raghavan (MR)
  3. Notes on Randomized Algorithms, James Aspnes (Asp) (link para conteúdo gratuito)
  4. 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 (prazo gerenciado pelo Moodle, não aceito atrasos!).


Notas

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 Desigualdade de Jensen MU - 2.1
7 Variáveis Binomiais e de Bernoulli, Esperança Condicional (exercícios) MU - 2.2 e 2.3
8 Esperança Condicional: Aplicação (exercícios) MU - 2.3
9 Distribuição Geométrica (exercícios) MU - 2.4
10 QuickSort Aleatorizado (exercícios) MU - 2.5
11 Desig. de Markov, Variância e Momentos de uma Var. Aleatória (exercícios) MU - 3.1 e 3.2
12 Variância e Momentos de uma Var. Aleatória (exercícios) MU - 3.2
13 Desigualdade de Chebyshev (exercícios) MU - 3.3
14 Algoritmo do k-ésimo Menor (1 de 2) MU - 3.4
15 Algoritmo do k-ésimo Menor (2 de 2) MU - 3.4
16 Funções Geradoras de Momento (exercícios) MU - 4.1
17 Limitantes de Chernoff (1 de 2) (exercícios) MU - 4.2
18 Limitantes de Chernoff (2 de 2) (exercícios) MU - 4.2
19 Limitantes Melhores para Casos Especiais (exercícios) MU - 4.3
20 Aplicação: Balanceamento de Conjunto MU - 4.4
21 Aplicação: Empacotamento de Itens Egoísta artigo
22 O Paradoxo do Aniversário, Bolas e Cestos (exercícios) MU - 5.1
23 Bolas e Cestos (exercícios) MU - 5.2
24 Distribuição de Poisson (1 de 2) (exercícios) MU - 5.3
25 Distribuição de Poisson (2 de 2) (exercícios) MU - 5.3
26 Aproximação de Poisson (1 de 2) MU - 5.4
27 Aproximação de Poisson (2 de 2) (exercícios) MU - 5.4
28 Aplicação: Hashing (1 de 2) MU - 5.5
29 Aplicação: Hashing (2 de 2) MU - 5.5
30 Grafos Aleatórios (exercícios) MU - 5.6

Horário de atendimento