Método de Monte Carlo

Keywords: Método de Monte Carlo, Matemática

Em matemática, algoritmos Monte Carlo são algoritmos aleatórios que não garantem encontrar a solução do problema. Existem três classes de algoritmos Monte Carlo: Erro-Unilateral, Erro-Bilateral e Erro-Não-Limitado. Para detalhes, sugere-se a leitura de (HROMKOVIC,2001).

Conteúdo

1 Monte Carlo de Erro-Unilateral

2 Monte Carlo de Erro-Bilateral

3 Monte Carlo de Erro-Não-Limitado

4 Referências

Monte Carlo de Erro-Unilateral

Seja P um problema e A um algoritmo aleatório, A é um algoritmo Monte Carlo de Erro-Unilateral que resolve P se

i) para toda configuração x que é solução de P, $prob(A(x = SIM )) \geq \frac{1}{2}$ , e

ii) para toda configuração x que não é solução de P, prob(A(x) = NÃO ) = 1

Ou seja, sempre que a resposta é NÃO, o algoritmo garante a certeza da resposta. Contudo, se a resposta for SIM, o algoritmo não garante que a resposta está correta.

Monte Carlo de Erro-Bilateral

Um algoritmo aleatório A é um algoritmo de Monte Carlo de Erro-Bilateral que computa o problema F se existe um número real $ε$ , tal que para toda instância x de F

$prob(A(x) = F(x)) \geq \frac{1}{2} + \epsilon$

Monte Carlo de Erro-Não-Limitado

Os algoritmos Monte Carlo de Erro-Não-Limitado são comumente chamados de Algoritmos Monte Carlo. Um algoritmo aleatório A é um algoritmo de Monte Carlo se para qualquer entrada x do problema F

$prob(A(x) = F(x)) > \frac{1}{2}$

Referências

HROMKOVIC, J. Algorithms for Hard Problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. [S.l.]: Springer-Verlag London Berlin Heidelberg New York, 2001.