Algoritmos Randomizados: Introdução
Transcrição
Algoritmos Randomizados: Introduçã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 Algoritmos de Monte Carlo 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 Algoritmos de Monte Carlo (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 } Algoritmos de Monte Carlo (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 } = Pr { CN } . Pr { AS | CN } + Pr { CS } . 0 Algoritmos de Monte Carlo (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 } = Pr { CN } . Pr { AS | CN } + Pr { CS } . 0 = Pr { CN } . ε + 0 Algoritmos de Monte Carlo (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 } = Pr { CN } . Pr { AS | CN } + Pr { CS } . 0 = Pr { CN } . ≤ ε ε + 0 Algoritmos de Monte Carlo (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 } = Pr { CN } . Pr { AS | CN } + Pr { CS } . 0 = Pr { CN } . ≤ ε ε + 0 Pr {“acerto”} ≥ p = 1 - ε Algoritmos de Monte Carlo (baseados-no-NÃO) ● Quando respondem NÃO, estão sempre corretos (exibem certificado) Algoritmos de Monte Carlo (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 4) Senão, retorne SIM Algoritmos de Monte Carlo (baseados-no-NÃO) Exemplo: IDENTIDADE DE POLINÔMIOS F(x) = (x – a1) (x – a2) ... (x – ad) d G(x) = bdx + bd-1 x Determinístico 2 O(d ) 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 d-1 + ... + b1x + b0 Monte Carlo 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 4) Senão, retorne SIM Algoritmos de Monte Carlo (baseados-no-NÃO) Exemplo: IDENTIDADE DE POLINÔMIOS F(x) = (x – a1) (x – a2) ... (x – ad) d G(x) = bdx + bd-1 x Determinístico 2 O(d ) 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 d-1 + ... + b1x + b0 Monte Carlo O(d ) 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 4) Senão, retorne SIM Algoritmos de Monte Carlo (baseados-no-NÃO) Exemplo: IDENTIDADE DE POLINÔMIOS 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 ) 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 4) Senão, retorne SIM Algoritmos de Monte Carlo (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 Variáveis Aleatórias ● 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 Variáveis Aleatórias ● 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 Variáveis Aleatórias ● 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. Algoritmos de Las Vegas 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 ... ... ... Algoritmos de Las Vegas Exemplo: ORDENAÇÃO Quick Sort ● ● pivô escolhido deterministicamente pior caso: O(n2) Quick Sort Randomizado ● ● pivô escolhido aleatoriamente tempo esperado (para qualquer entrada!!): ? Algoritmos de Las Vegas 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]) Algoritmos de Las Vegas 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) Algoritmos de Las Vegas 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. O Método Probabilístico 1) Método da esperança Experimento aleatório Se E [ X ] = μ, então existe elemento para o qual X ≤ μ e existe elemento para o qual X ≥ μ O Método Probabilístico 1) Método da esperança Exemplo: CORTES GRANDES EM GRAFOS m arestas O Método Probabilístico 1) Método da esperança Exemplo: CORTES GRANDES EM GRAFOS B A m arestas Corte de tamanho 4 O Método Probabilístico 1) Método da esperança Exemplo: CORTES GRANDES EM GRAFOS 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 O Método Probabilístico 2) Método da probabilidade positiva O Método Probabilístico 2) Método da probabilidade positiva Espaço probabilístico Ω Experimento aleatório Se Pr {“ ”} > 0 então pertence a Ω O Método Probabilístico 2) Método da probabilidade positiva 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