08Probabilistas

Metodolog´ıa y Tecnolog´ıa de la Programaci´on
Ingenier´ıa en Inform´atica
Curso 2008-2009
Esquemas algor´ıtmicos. Algoritmos Probabilistas
Yolanda Garc´ıa Ruiz D228
Jes´
us Correas D228

ygarciar@fdi.ucm.es
jcorreas@fdi.ucm.es

Departamento de Sistemas Inform´
aticos y Computaci´
on
Universidad Complutense de Madrid
(elaborado a partir de notas de S. Est´evez y R. Gonz´alez del Campo)
YolandaGarc´ıa, Jes´
us Correas (DSIC - UCM)

1 / 54

Bibliograf´ıa

Importante: Estas transparencias son un material de apoyo a las
clases presenciales y no sustituyen a la bibliograf´ıa b´asica ni a las
propias clases presenciales para el estudio de la asignatura
Bibliograf´ıa b´asica:
[BB97]: cap´ıtulo 10

Yolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

2 / 54

Algoritmos Probabilistas

1Caracter´ısticas generales

2

Clasificaci´on de los algoritmos probabilistas

3

Algoritmos probabilistas num´ericos

4

Algoritmos de Monte Carlo

5

Algoritmos de Las Vegas

Yolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

3 / 54

Caracter´ısticas generales

En algunos algoritmos en los que aparece una decisi´on, es preferible a
veces elegir aleatoriamente una de las posibles alternativas antes que
perdertiempo calculando cu´al de ellas es la mejor
Esta situaci´on se produce si el tiempo requerido para determinar la
alternativa ´optima es demasiado largo frente al promedio obtenido
tomando la decisi´on al azar
Caracter´ıstica fundamental de los algoritmos probabilistas:
Un algoritmo probabilista P puede comportarse de forma distinta
cuando se aplica dos veces sobre los mismos datos de entradaYolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

4 / 54

Caracter´ısticas generales (Cont.)
Est´as en el puerto de la Isla del Tesoro, y sabes que el tesoro de x
lingotes de oro est´a escondido en uno de dos lugares posibles: A o B,
pero no sabes en cu´al.
Tanto A como B est´an a 5 d´ıas de viaje del puerto, y a 5 d´ıas de viaje
entre s´ı.
Un drag´on visita cada noche el tesoro y se lleva y lingotes.
Enel ciber del puerto hay un ordenador que nos permitir´a saber
d´onde est´a el tesoro, pero tarda 4 d´ıas en calcularlo.
Un elfo que pasa por el puerto te ofrece un trato: te da la soluci´on
ahora mismo si le pagas el equivalente a lo que se llevar´ıa el drag´on
en 3 noches
¿Qu´e puedes hacer?

Yolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

5 / 54

Caracter´ısticas generales (Cont.)
¿Qu´e puedeshacer?
a) Puedes quedarte 4 d´ıas en el puerto hasta resolver el misterio, llegar al
tesoro 9 d´ıas despu´es, y obtener x − 9y lingotes de oro.
b) Puedes aceptar el trato con el elfo, llegar al tesoro en 5 d´ıas y pagar al
elfo a la vuelta. En total, obtienes x − 8y lingotes.

Parece que lo mejor es aceptar el trato...

Yolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

6 / 54

Caracter´ısticasgenerales (Cont.)
¿Qu´e puedes hacer?
a) Puedes quedarte 4 d´ıas en el puerto hasta resolver el misterio, llegar al
tesoro 9 d´ıas despu´es, y obtener x − 9y lingotes de oro.
b) Puedes aceptar el trato con el elfo, llegar al tesoro en 5 d´ıas y pagar al
elfo a la vuelta. En total, obtienes x − 8y lingotes.

Parece que lo mejor es aceptar el trato...
...pero hay una soluci´
on mejor: elegir al azar d´onde ir primero (A o
B):
Si aciertas con el tesoro a la primera, obtienes x − 5y lingotes
Si no aciertas, te conformas con x − 10y , pero al menos ha sido
emocionante

El beneficio esperado medio es x − 7, 5y , mejor que cualquiera de las
opciones anteriores

Yolanda Garc´ıa, Jes´
us Correas (DSIC - UCM)

6 / 54

Caracter´ısticas generales (Cont.)
Diferencias entre algoritmos deterministas yprobabilistas:

1. A un algoritmo determinista nunca se le permite que no termine.
A un algoritmo probabilista se le puede permitir siempre que eso ocurra
con una probabilidad muy peque˜
na para datos cualesquiera. Si ocurre,
se aborta el algoritmo y se repite su ejecuci´
on con los mismos datos y
as´ı tendremos una nueva oportunidad de ´exito.

2. Si existe m´as de una soluci´on para unos datos...