Algoritmos Randomizados: Introdução

Transcrição

Algoritmos Randomizados:
Introdução
Celina Figueiredo
Guilherme Fonseca
Manoel Lemos
Vinícius Sá
26º Colóquio Brasileiro de Matemática
IMPA – Rio de Janeiro – Brasil
2007
Resumo
●
Definições
●
Monte Carlo
●
Variáveis Aleatórias
●
Las Vegas
●
●
Paradigmas
combinatórios
Método probabilístico
Definições
●
Algoritmo
●
Experimento aleatório (ou randômico)
●
Gerador de números aleatórios
●
Algoritmos randomizados
Algoritmos Randomizados
●
Aplicações
●
Vantagens
✔
criptografia
✔
mais rápidos
✔
programação distribuída
✔
mais simples
✔
teoria dos grafos
✔
ambos
✔
geometria computacional
✔
etc.
●
Preço
✔
análise trabalhosa
✔
incerteza
qualidade da resposta
➔ tempo de execução
➔
Monte Carlo
●
●
Fornecem a resposta
correta com
probabilidade (alta)
conhecida
Tempo de execução
determinístico
Las Vegas
●
●
A resposta dada está
sempre correta
Tempo de execução é
uma variável aleatória
Algoritmos de Monte Carlo
(p / problemas de decisão)
●
Erro bilateral
OU
●
Erro unilateral
–
baseados-no-SIM
–
baseados-no-NÃO
CN: a resposta correta é NÃO
CS: a resposta correta é SIM
AN: o algoritmo responde NÃO
AS: o algoritmo responde SIM
baseado-no-NÃO: Pr { CN | AN } = 1
Pr { AS | CS } = 1
(baseados-no-NÃO)
Pr {“erro”}
= Pr { CN , AS U
CS , AN }
= Pr { CN , AS } + Pr { CS , AN }
= Pr { CN } . Pr { AS | CN } + Pr { CS } . Pr { AN | CS }
(baseados-no-NÃO)
Pr {“erro”}
= Pr { CN , AS U
CS , AN }
= Pr { CN , AS } + Pr { CS , AN }
= Pr { CN } . Pr { AS | CN } + Pr { CS } . 0
(baseados-no-NÃO)
Pr {“erro”}
= Pr { CN , AS U
CS , AN }
= Pr { CN , AS } + Pr { CS , AN }
= Pr { CN } . Pr { AS | CN } + Pr { CS } . 0
= Pr { CN } .
ε
+ 0
(baseados-no-NÃO)
Pr {“erro”}
= Pr { CN , AS U
CS , AN }
= Pr { CN , AS } + Pr { CS , AN }
= Pr { CN } . Pr { AS | CN } + Pr { CS } . 0
= Pr { CN } .
≤ ε
ε
+ 0
(baseados-no-NÃO)
Pr {“erro”}
= Pr { CN , AS U
CS , AN }
= Pr { CN , AS } + Pr { CS , AN }
= Pr { CN } . Pr { AS | CN } + Pr { CS } . 0
= Pr { CN } .
≤ ε
ε
+ 0
Pr {“acerto”} ≥ p = 1 - ε
(baseados-no-NÃO)
●
Quando respondem NÃO, estão sempre corretos
(exibem certificado)
(baseados-no-NÃO)
Exemplo: IDENTIDADE DE POLINÔMIOS
F(x) = (x – a1) (x – a2) ... (x – ad)
d
G(x) = bdx + bd-1 x
d-1
+ ... + b1x + b0
Determinístico
Monte Carlo
1) Transforme F(x)
2) Compare os coeficientes
de F(x) e G(x)
3) Se houver diferença,
retorne NÃO
4) Senão, retorne SIM
1) Sorteie um inteiro w,
aleatoriamente, de 1 a 100d
2) Avalie F(w) e G(w)
3) Se F(w) ≠ G(w),
retorne NÃO
(baseados-no-NÃO)
F(x) = (x – a1) (x – a2) ... (x – ad)
d
G(x) = bdx + bd-1 x
Determinístico
2
O(d )
1) Transforme F(x)
de F(x) e G(x)
retorne NÃO
d-1
+ ... + b1x + b0
Monte Carlo
3) Se F(w) ≠ G(w),
retorne NÃO
(baseados-no-NÃO)
F(x) = (x – a1) (x – a2) ... (x – ad)
d
G(x) = bdx + bd-1 x
Determinístico
2
O(d )
1) Transforme F(x)
de F(x) e G(x)
retorne NÃO
d-1
+ ... + b1x + b0
Monte Carlo
O(d )
3) Se F(w) ≠ G(w),
retorne NÃO
(baseados-no-NÃO)
F(x) = (x – a1) (x – a2) ... (x – ad)
d
G(x) = bdx + bd-1 x
Pr { AN | CS } = 0
Pr { AS | CN } = ε = ?
ε ≤ d / 100d = 1/100
Pr {“acerto”} ≥ 99%
d-1
+ ... + b1x + b0
Monte Carlo
O(d )
3) Se F(w) ≠ G(w),
retorne NÃO
(baseados-no-NÃO)
Refinando a probabilidade de acerto...
●
Em uma execução do algoritmo,
Pr {“erro”} ≤ Pr { AS | CN } = ε
●
Em t execuções independentes,
Pr {“erro”} = Pr {“erro1”,“erro2”, ... ,“errot”} ≤ εt
●
Função que mapeia um experimento
aleatório em um valor numérico qualquer
X:Ω→R
A = soma dos valores
obtidos no lançamento
de dois dados
B = número de sorteios
até que se complete
determinada coluna de
uma cartela de bingo
1 , se cara
C=
0 , se coroa
●
Esperança (ou valor esperado)
média dos resultados possíveis ponderada
pelas probabilidades de ocorrência
E [A] =
2 . Pr {“A = 2”} +
+ 3 . Pr {“A = 3”} +
+ ... +
A = soma dos valores
obtidos no lançamento
de dois dados
+ 12 . Pr {“A = 12”} =
= 7
●
Esperança: E [X] = Σ ( j . Pr {“X = j”} )
●
Variância: Var [X] = E [X 2] – (E [X])2
●
Desvio padrão
●
Momentos da V. A.
V. A
.
Variáveis Aleatórias famosas
Pr { “sucesso” } = p
●
Bernoulli
X=
●
1 , se “sucesso”
0 , se “fracasso”
Binomial
X = “número de sucessos em n
experimentos independentes”
●
E [X] = p
Var [X] = p (1-p)
E [X] = n p
Var [X] = n p (1-p)
Geométrica
X = “número de experimentos até
o primeiro sucesso”
E [X] = 1 / p
Var [X] = (1-p) / p2
Desigualdades famosas
●
Desigualdade de Markov
E [X]
Pr { X ≥ a } ≤
a
●
(a > 0)
Desigualdade de Chebyshev
Pr { |X – E [ X ]| ≥ a } ≤
Var [ X ]
a
2
(a > 0)
Algoritmos de Las Vegas
●
●
Resposta
sempre correta
Tempo
computacional
é uma V. A.
Exemplo: ORDENAÇÃO
8
5
3
9
11
1
0
18
50
4
7
18
50
Algoritmo: Quick Sort
8
5
3
0
1
4
7
9
5
...
11
9
...
...
...
Exemplo: ORDENAÇÃO
Quick Sort
●
●
pivô escolhido
deterministicamente
pior caso: O(n2)
Quick Sort
Randomizado
●
●
pivô escolhido
aleatoriamente
tempo esperado
(para qualquer entrada!!):
?
Quick Sort Randomizado
Entrada: a1, a2 , a3 , ... , an
Saída: y1, y2 , y3 , ... , yn
X = “número de comparações realizadas” = ?
Bernoulli
Xj,k =
1, se é feita a comparação entre yj e yk
0, caso contrário
X = X1,2 + X1,3 + ... + Xn -1,n
E [X] = E [X1,2 + X1,3 + ... + Xn -1,n ] =
= E [X1,2 ] + E [X1,3 ] + ... + E [Xn -1,n ]
Linearidade
da Esperança:
E [f (X)] = f (E [X])
Quick Sort Randomizado
Entrada:
8
5
3
9
11
1
0
18
Saída:
0
1
3
4
5
7
8
9
yj
50
4
7
11 18
50
yk
Pr { “sucesso” } = Pr {“Xj,k= 1”} = 2 / (k - j + 1)
E [X] = Σ1≤ j < k ≤ n E [Xj,k] =
= Σ1≤ j < k ≤ n 2 / (k - j + 1) =
= O (n log n)
Tempo esperado
de um algoritmo
de Las Vegas
X
Tempo médio de
um algoritmo
determinístico
(dado um modelo
probabilístico da entrada)
Entrada:
Entrada:
M
?
G
H
Algoritmo de Las Vegas
W
G
Algoritmo determinístico
D
Monte Carlo X Las Vegas
●
Monte Carlo,
a partir de Las Vegas
1) enquanto tempo < t
2)
se Las Vegas encontra SIM,
3)
responda SIM
4)
se Las Vegas encontra NÃO,
5)
responda NÃO
6) reponda NÃO (arbitrariamente)
●
1) repita
2)
se MC-SIM encontra SIM,
3)
responda SIM
4)
se MC-NÃO encontra NÃO,
5)
responda NÃO
➔
➔
Monte Carlo baseado-no-SIM
➔
X = “tempo do Las Vegas”
➔
Pr {“erro”} = Pr {CS , AN}
= Pr {CS} . Pr { AN | CS }
≤ Pr { “X ≥ t ” }
Markov! Chebyshev!
Las Vegas,
a partir de 2 Monte Carlos
número T de iterações
V. A. geométrica!
➔
Pr {“sucesso”} = p = 1 - εSIM . εNÃO
➔
E [T] = 1 / p
Modelo de bolas e latas
1
2
3
4
...
n-1
n
O colecionador de coupons
Exemplo: IDENTIFICAÇÃO DE ROTEADORES
...
Origem
n roteadores
Destino
O Método Probabilístico
1) Método da esperança
Minha idade é X.
Experimento aleatório
Se E [ X ] = μ, então
existe elemento para o qual X ≤ μ
e existe elemento para o qual X ≥ μ
Exemplo: CORTES GRANDES EM GRAFOS
m arestas
B
A
m arestas
Corte de tamanho 4
Algoritmo randomizado
X = tamanho do corte retornado
X j = 1, aresta j pertence ao corte
0, caso contrário
(Bernoulli)
m arestas
Para cada vértice v...
coloque v em A com probabilidade ½
coloque v em B com probabilidade ½
Retorne o corte (A,B)
Pr {“sucesso”} = p = ?
X = Σj X j
E[X] = Σj E [X j ] = m . p = m / 2
2) Método da probabilidade positiva
Espaço probabilístico
Ω
Experimento aleatório
Se
Pr {“ ”} > 0
então
pertence a Ω
Algoritmo ruim
(não serve para a prova)
Algoritmo adequado
(serve para a prova)
Algoritmos Randomizados:
Introdução
Celina Figueiredo
Guilherme Fonseca
Manoel Lemos
Vinícius Sá
26º Colóquio Brasileiro de Matemática
IMPA – Rio de Janeiro – Brasil
2007

Algoritmos Randomizados: Introdução

Transcrição

Documentos relacionados

Las Vegas - CM - AIT Operadora

Las Vegas Quiz - O casino em sua casa Dixit 4

Caesars Entertainment redefiniu o horizonte icônico de Las Vegas

Blaser F3 competição

Clique aqui para fazer o do roteiro

LAS VEGAS - steinberg.com.br

Delicie-se em Las Vegas!

Silvio Santos Ilha de Páscoa Aquarela do Brasil Cidade de Deus

descobrimento do brasil

Preço por pessoa: