La vereda de la puerta de atrás

Last.fm

sábado, junio 17, 2006

Algoritmos probabilistas

El lunes tengo el examen final de Metodología y Teoría de la Programación (MTPeinas para los amigos), y aquí estoy, a las 4.30 de un viernes, estudiando algoritmos probabilistas. Para los que no sepais lo que es, una explicación rápida: son algoritmos que buscan la solución a un problema al azar. Los hay de dos tipos, los que pueden dar una solución incorrecta (algoritmos de Montecarlo) y los que no dan soluciones incorrectas, sino que como mucho, no dan solución (algoritmos de Las Vegas).
Y no me estaba enterando de nada hasta que he visto un ejemplo, el algoritmo de Freivalds, para comprobar si tres matrices A,B,C son de la forma C = AB. El ejemplo este no viene al caso, pero si una de sus características. Copio literal de los apuntes:

La clave:
- Siempre que Freivalds(A,B,C) devuelve falso, podemos estar seguros de que AB!=C.
- Sólo cuando devuelve verdad, no sabemos la respuesta.

Después de leer esto he visto la luz, y he comprendido cómo funcionan los algoritmos probabilistas, más que nada porque llevo usándolos desde que entré en la universidad, y no porque los estudie, sino porque su uso es muy común. He aquí un ejemplo que os resultará familiar:

Algoritmo del aprobado del examen:
- Siempre que salgas de un examen y Aprobado(examen) devuelva falso, podemos estar seguros de que has cateado
- Sólo cuando devuelve aprobado, no sabemos la respuesta.

En fin, que voy a seguir desvariando delante de los apuntes otro rato.

Un saludo

1 comentario:

Anónimo dijo...

¡Animo y a por ese MTP, que los probabilistas están tiraos!
Chav