Algoritmos Probalisticos

Algoritmo probabilista
Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se pueden obtener distintassoluciones y, en algunos casos, soluciones erróneas.
Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir:
* Algoritmos numéricos, que proporcionan una solución aproximada del problema.
* Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas (con probabilidad baja).
* Algoritmos de Las Vegas, que nunca danuna respuesta incorrecta: o bien dan la respuesta correcta o informan del fallo.
Consideraciones
Se puede optar por la elección aleatoria si se tiene un problema cuya elección óptima es demasiado costosa frente a la decisión aleatoria. Un algoritmo probabilista puede comportarse de distinta forma aplicando la misma entrada.
* A un algoritmo determinista nunca se le permite que no termine:hacer una división por 0, entrar en un bucle infinito, etc.
* Si existe más de una solución para unos datos dados, un algoritmo determinista siempre encuentra la misma solución (a no ser que se programe para encontrar varias o todas).
* Un algoritmo probabilista puede encontrar soluciones diferentes ejecutándose varias veces con los mismos datos.
* A un algoritmo determinista no se lepermite que calcule una solución incorrecta para ningún dato.
* Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada.
* Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta.
* El análisis de la eficiencia deun algoritmo determinista es, en determinadas ocasiones, difícil.
* El análisis de los algoritmos probabilistas es, a menudo, muy difícil.
Algoritmos numéricos
La solución obtenida es siempre aproximada pero su precisión esperada mejora aumentando el tiempo de ejecución. Normalmente, el error es inversamente proporcional a la raíz cuadrada del esfuerzo invertido en el cálculo.
Ejemplo: Laaguja de Buffon
Teorema de Buffon: si se tira una aguja de longitud μ a un suelo hecho con tiras de madera de anchura w (w>=μ), la probabilidad de que la aguja toque más de una tira de madera es p=2μ/wp.
Aplicación:
* Si μ=w/2, entonces p=1/p.
* Si se tira la aguja un número de veces n suficientemente grande y se cuenta el número k de veces que la aguja toca más de una tira de madera,se puede estimar el valor de p: k ~ n/p → p ~ n/k
* Es (probablemente) el primer algoritmo probabilista de la historia.
¿Es útil este método?
* ¿Cómo de rápida es la convergencia? → ¿cuántas veces hay que tirar la aguja?
Muy lenta: n=1500000 para obtener un valor de p±0’01 con probabilidad 0’9.
Algoritmos de Montecarlo
Artículo principal: Método de Monte Carlo
Hay problemas para losque no se conocen soluciones deterministas ni probabilistas que den siempre una solución correcta(ni siquiera una solución aproximada).
Algoritmo de Montecarlo:
* A veces da una solución incorrecta.
* Con una alta probabilidad encuentra una solución correcta sea cual sea la entrada.
Definición: Sea p un número real tal que 0.5<p<1.Un algoritmo de Montecarlo es p–correcto si:
*Devuelve una solución correcta con probabilidad mayor o igual que p, cualesquiera que sean los datos de entrada.
* A veces, p dependerá del tamaño de la entrada, pero nunca de los datos de la entrada en sí.
Un ejemplo de algoritmo de Montecarlo (el más conocido): decidir si un número impar es primo o compuesto.
* Ningún algoritmo determinista conocido puede responder en un tiempo...