Algoritmo de Monte Carlo - Monte Carlo algorithm
En informática , un algoritmo de Monte Carlo es un algoritmo aleatorio cuya salida puede ser incorrecta con una cierta probabilidad (normalmente pequeña) . Dos ejemplos de tales algoritmos son el algoritmo de Karger-Stein y el algoritmo de Monte Carlo para un conjunto de arco de retroalimentación mínimo .
El nombre se refiere al gran casino del Principado de Mónaco en Montecarlo , conocido en todo el mundo como un icono del juego. El término "Monte Carlo" fue introducido por primera vez en 1947 por Nicholas Metropolis .
Los algoritmos de Las Vegas son un dual de los algoritmos de Monte Carlo que nunca devuelven una respuesta incorrecta; sin embargo, pueden tomar decisiones aleatorias como parte de su trabajo. Como resultado, el tiempo necesario puede variar entre ejecuciones incluso con la misma entrada.
Si existe un procedimiento para verificar si la respuesta dada por un algoritmo de Monte Carlo es correcta, y la probabilidad de una respuesta correcta está limitada por encima de cero, entonces, con una probabilidad uno, ejecutando el algoritmo repetidamente mientras se prueban las respuestas, eventualmente dará una respuesta correcta. Si este proceso es un algoritmo de Las Vegas depende de si se considera que detener con probabilidad uno satisface la definición.
Error unilateral frente a error bilateral
Mientras que siempre se espera que la respuesta devuelta por un algoritmo determinista sea correcta, este no es el caso de los algoritmos de Monte Carlo. Para problemas de decisión , estos algoritmos generalmente se clasifican como sesgados falsos o sesgados verdaderos . Un algoritmo de Monte Carlo con sesgo falso siempre es correcto cuando devuelve falso ; un algoritmo sesgado verdadero siempre es correcto cuando devuelve verdadero . Si bien esto describe algoritmos con errores unilaterales , es posible que otros no tengan sesgo; se dice que estos tienen errores de dos caras . La respuesta que brinden ( verdadera o falsa ) será incorrecta o correcta, con cierta probabilidad limitada.
Por ejemplo, la prueba de primalidad de Solovay-Strassen se utiliza para determinar si un número dado es un número primo . Siempre responde verdadero para las entradas de números primos; para entradas compuestas, responde falso con probabilidad al menos 1 ⁄ 2 y verdadero con probabilidad menor que 1 ⁄ 2 . Por lo tanto, es seguro que las respuestas falsas del algoritmo sean correctas, mientras que las respuestas verdaderas siguen siendo inciertas; esto se dice que es un 1 / 2 algoritmo de falsos sesgado -correct .
Amplificación
Para un algoritmo de Monte Carlo con errores unilaterales, la probabilidad de falla puede reducirse (y la probabilidad de éxito amplificarse) ejecutando el algoritmo k veces. Considere de nuevo el algoritmo de Solovay-Strassen, que es 1 ⁄ 2 -correcto de falso sesgo . Se puede ejecutar este algoritmo varias veces devolviendo una respuesta falsa si llega a una respuesta falsa dentro de k iteraciones y, de lo contrario, devolviendo verdadero . Por lo tanto, si el número es primo, la respuesta siempre es correcta, y si el número es compuesto, la respuesta es correcta con una probabilidad de al menos 1− (1− 1 ⁄ 2 ) k = 1−2 −k .
Para los algoritmos de decisión de Monte Carlo con error de dos caras, la probabilidad de falla se puede reducir nuevamente ejecutando el algoritmo k veces y devolviendo la función mayoritaria de las respuestas.
Clases de complejidad
La clase de complejidad BPP describe problemas de decisión que pueden resolverse mediante algoritmos de Monte Carlo en tiempo polinómico con una probabilidad acotada de errores de dos caras, y la clase de complejidad RP describe problemas que pueden resolverse mediante un algoritmo de Monte Carlo con una probabilidad acotada de uno. -sided de error: si la respuesta correcta es falsa , el algoritmo siempre lo dice, pero puede responder falsa incorrectamente para algunos casos en los que la respuesta correcta es cierto . Por el contrario, la clase de complejidad ZPP describe problemas que se pueden resolver mediante algoritmos polinomiales de tiempo esperado de Las Vegas. ZPP ⊆ RP ⊆ BPP , pero no se sabe si alguna de estas clases de complejidad es distinta entre sí; es decir, los algoritmos de Monte Carlo pueden tener más poder computacional que los algoritmos de Las Vegas, pero esto no ha sido probado. Otra clase de complejidad, PP , describe problemas de decisión con un algoritmo de Monte Carlo de tiempo polinomial que es más preciso que lanzar una moneda al aire, pero donde la probabilidad de error no necesariamente puede limitarse a 1 ⁄ 2 .
Aplicaciones en teoría computacional de números
Bien conocidos algoritmos de Monte Carlo incluyen la prueba Solovay-Strassen primalidad, el test de primalidad Baillie-PSW , el test de primalidad Miller-Rabin , y cierta rápido variantes del algoritmo Schreier-Sims en la teoría de grupos computacional .
Ver también
- Métodos de Monte Carlo , algoritmos utilizados en simulación física y estadística computacional basados en la toma de muestras aleatorias.
- Algoritmo de Atlantic City
- Algoritmo de Las Vegas
Referencias
Citas
Fuentes
- Motwani, Rajeev ; Raghavan, Prabhakar (1995). Algoritmos aleatorios . Nueva York : Cambridge University Press. ISBN 0-521-47465-5.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 5. Análisis probabilístico y algoritmos aleatorios". Introducción a los algoritmos (2ª ed.). Boston : MIT Press y McGraw-Hill. ISBN 0-262-53196-8.
- Berman, Kenneth A .; Paul, Jerome L. (2005). "Capítulo 24. Algoritmos probabilísticos y aleatorios". Algoritmos: secuencial, paralelo y distribuido . Boston : Curso de tecnología. ISBN 0-534-42057-5.