CI337 - Algoritmos Aleatorizados

2o semestre de 2018

2a e 4a às 13:30

sala PA-05


Como Se Dar Bem Nesta Disciplina

Ementa

  1. Eventos e Axiomas da Probabilidade
  2. Variáveis Aleatórias Discretas e Esperança
  3. Desigualdades de Cauda
  4. Grafos Aleatórios
  5. Método Probabilístico

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






Os exercícios se referem à 1a Edição do livro MU

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!).


Material das Aulas


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


# NOTAS DA AULA EXERCÍCIOS REF. BIBLIOGRÁFICA CONTEÚDO ADICIONAL
1 Axiomas de Probabilidade (1 de 2) (exercícios) MU - 1.1 e 1.2 Ilustração do Princípio da Inclusão-Exclusão
2 Axiomas de Probabilidade (2 de 2) (exercícios) MU - 1.1 e 1.2 Pensando sobre intersecção entre eventos
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 (exercícios) 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 Intuição sobre covariância
13 Desigualdade de Chebyshev (exercícios) MU - 3.3
14 Desigualdade de Chebyshev: Aplicações (exercícios) MU - 3.3
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 sem exercícios MU - 4.4
20 Grafos Aleatórios: Modelos de Erdös-Renyi (exercícios) MU - 5.6
21 Grafos Aleatórios: Distribuição de Graus Configurável (exercícios) MU - 5.6
22 O Método Probabilístico (exercícios) MU - 6.1 e 6.2
23 Desaleatorização (exercícios) MU - 6.3
24 Amostre e Modifique (exercícios) MU - 6.4
25 Método do Segundo Momento (exercícios) MU - 6.5
26 Desigualdade da Esperança Condicional (exercícios) MU - 6.6

Horário de atendimento