De Wikipedia sobre algoritmos aleatorios
Hay que distinguir entre algoritmos que usan la entrada aleatoria para reducir el tiempo de ejecución esperado o el uso de memoria, pero siempre terminan con un resultado correcto en una cantidad limitada de tiempo, y algoritmos probabilísticos , que, dependiendo de la entrada aleatoria, tienen una posibilidad de producir un resultado incorrecto (algoritmos de Monte Carlo) o no producir un resultado (algoritmos de Las Vegas), ya sea señalando una falla o no terminando.
- Me preguntaba cómo el primer tipo de " algoritmos utiliza la entrada aleatoria para reducir el tiempo de ejecución esperado o el uso de memoria, pero siempre termina con un resultado correcto en una cantidad de tiempo limitada".
- ¿Qué diferencias hay entre este y los algoritmos de Las Vegas que pueden no producir un resultado?
- Si entiendo correctamente, los algoritmos probabilísticos y los algoritmos aleatorios no son el mismo concepto. Los algoritmos probabilísticos son solo un tipo de algoritmos aleatorios, y el otro tipo son los que usan la entrada aleatoria para reducir el tiempo de ejecución esperado o el uso de memoria, pero siempre terminan con un resultado correcto en un período de tiempo limitado.
Los dos términos algoritmos aleatorios y algoritmos probabilísticos se utilizan en dos contextos diferentes. Los algoritmos aleatorios son algoritmos que utilizan la aleatoriedad, en contraste con los algoritmos deterministas que no lo hacen. Los algoritmos probabilísticos , por ejemplo, los algoritmos probabilísticos para la prueba de primalidad, son algoritmos que usan aleatoriedad y podrían cometer un error con alguna (con suerte) pequeña probabilidad.
Debe hacerse una distinción importante entre los algoritmos de Monte Carlo y los algoritmos de Las Vegas . Los algoritmos de Las Vegas son algoritmos aleatorios que siempre devuelven la respuesta correcta, pero su tiempo de ejecución depende del lanzamiento de la moneda. Un ejemplo son los algoritmos de factorización de enteros: siempre devuelven los factores correctos, pero su tiempo de ejecución depende de la aleatoriedad. Al establecer el tiempo de ejecución de un algoritmo de Las Vegas (digamos un algoritmo de factorización), en realidad establecemos el tiempo de ejecución esperado ; Si no tenemos suerte, el algoritmo podría funcionar por más tiempo.
Los algoritmos de Monte Carlo, por otro lado, son algoritmos aleatorios cuyo tiempo de ejecución se establece con anticipación. Tales algoritmos pueden cometer un error, pero generalmente la probabilidad de error es muy baja. Un buen ejemplo es la prueba de primalidad probabilística. Estos algoritmos son muy rápidos pero podrían cometer un error. Sin embargo, la probabilidad de error es lenta y baja que en la práctica, nunca cometen un error.
Todos los algoritmos de Las Vegas se pueden convertir a un algoritmo de Monte Carlo al detener la ejecución después de un tiempo suficientemente largo, por lo que los algoritmos de Las Vegas son, en cierto sentido, "mejores" que los algoritmos de Monte Carlo.
fuente