Método de Monte Carlo

Origem: Wikipédia, a enciclopédia livre.

Aplicação do método de Monte Carlo para determinar a área de um lago.

Este artigo precisa ser wikificado.

Por favor formate este artigo de acordo com as diretrizes estabelecidas no livro de estilo. Remova este aviso somente depois de todo o texto estar wikificado.

Foi proposta a fusão deste artigo com: Método Monte Carlo.

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

[editar] 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.

[editar] 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$

[editar] 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}$

[editar] 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.

Retirado de "http://pt.wikipedia.org../../../m/%C3%A9/t/M%C3%A9todo_de_Monte_Carlo_0390.html"

Categorias: !Artigos precisando de ligações internas | !Artigos a sofrerem fusão | Algoritmos | Estatística