Algoritmos probabilistas

Las últimas prácticas de Análisis de algoritmos ( :'( ), esta vez es otro tipo de algoritmos, aquellos que emplean en azar para resolver el problema que se les asignó. A estos se les llama probabilistas y según la Wikipedia en español, hay de tres tipos; mismos tipos que nos tocó ejemplificar mediante algunos algoritmos conocidos empleando POO (lo cual es un poco difícil para ejemplos tan sencillos), son los siguientes:
Integración de Monte Carlo
Apelando al hecho de que una integral es la sumatoria de la infinidad de resultados de evaluar una función en un intervalo dado, se toman puntos de evaluación aleatorios dentro de ese intervalo dado, se evalúan y se van acumulando para luego realizarles un ajuste matemático, les diría que lo buscaran en Wikipedia, pero este documento me resultó especialmente revelador.

Para el caso de la implementación de POO lo que se consideró fue la creación de dos clases Random y Funcion, la primera para generar números aleatorios y la segunda para evaluar la función.

Aproximación a π
Para este caso se toma un cuarto de círculo de radio = 1, y se lanzan n dardos hacia él de esos n dardos supongamos que m aciertan en él entonces mediante matemágia, podemos encontrar que  π ≈ 4 * m / n

Para (mal) aplicar la POO, existe una clase que hace uso de Random, la clase definida en el ejericio anterior y de otra, llamada Aproximación en la cual se realiza la simulación de los dardos

Comprobación de primalidad (Algoritmo Monte Carlo)
Existe un test de primalidad, inventado por Fermat que nos dice que si tomamos la siguiente frómula a^(n-1) % n para cualquier número a ∈ [1,n-1] y si el resultado de eso es distinto de 1 entonces sabemos que n no es primo. Tomando una gran cantidad de números con valores aleatorios para a ∈ [1,n-1] podríamos asegurar con cierta probabilidad si un número n es primo. Si el test falla, es decir el resultado para cualquiera a es distinto de 1 podemos asegurar que n no es primo.

Resolución del problema de las N reinas (Algoritmo Las Vegas)
El ya conocidísimo problema delas N reinas también se puede resolver mediante probabilidad, es decir, tomamos la columna 1 y colocamos la primera reina, después para la segunda columna tratamos de colocar la siguiente reina en una posición elegida aleatoriamente, si se logró, continuamos con la siguiente columna, y así hasta colocar las N reinas o no poder colocar una, en ese caso falla.
Bastante simple.
Las primeras dos corresponden a la práctica 5, implementada en C++, y la segundas están implementadas en C#, con interfaz gráfica para Windows Phone 8 en XAML. El código, en analizando-algo.

¡Saludos!
@fferegrino :)

No comments:

Post a Comment

¡Hey, gracias por tu comentario! No seas anónimo, inicia sesión para que te responda más fácilmente.