Metodologa y Tecnologa de la Programacion
Ingeniera en Informatica
Curso 2008-2009
Esquemas algortmicos. Algoritmos Probabilistas
Yolanda Garca Ruiz D228
Jes
us Correas D228
ygarciar@[Link]
jcorreas@[Link]
Departamento de Sistemas Inform
aticos y Computaci
on
Universidad Complutense de Madrid
(elaborado a partir de notas de S. Estevez y R. Gonzalez del Campo)
Yolanda Garca, Jes
us Correas (DSIC - UCM)
1 / 54
Bibliografa
Importante: Estas transparencias son un material de apoyo a las
clases presenciales y no sustituyen a la bibliografa basica ni a las
propias clases presenciales para el estudio de la asignatura
Bibliografa basica:
I
[BB97]: captulo 10
Yolanda Garca, Jes
us Correas (DSIC - UCM)
2 / 54
Algoritmos Probabilistas
Caractersticas generales
Clasificacion de los algoritmos probabilistas
Algoritmos probabilistas numericos
Algoritmos de Monte Carlo
Algoritmos de Las Vegas
Yolanda Garca, Jes
us Correas (DSIC - UCM)
3 / 54
Caractersticas generales
En algunos algoritmos en los que aparece una decision, es preferible a
veces elegir aleatoriamente una de las posibles alternativas antes que
perder tiempo calculando cual de ellas es la mejor
Esta situacion se produce si el tiempo requerido para determinar la
alternativa optima es demasiado largo frente al promedio obtenido
tomando la decision al azar
Caracterstica fundamental de los algoritmos probabilistas:
Un algoritmo probabilista P puede comportarse de forma distinta
cuando se aplica dos veces sobre los mismos datos de entrada
Yolanda Garca, Jes
us Correas (DSIC - UCM)
4 / 54
Caractersticas generales (Cont.)
Estas en el puerto de la Isla del Tesoro, y sabes que el tesoro de x
lingotes de oro esta escondido en uno de dos lugares posibles: A o B,
pero no sabes en cual.
Tanto A como B estan a 5 das de viaje del puerto, y a 5 das de viaje
entre s.
Un dragon visita cada noche el tesoro y se lleva y lingotes.
En el ciber del puerto hay un ordenador que nos permitira saber
donde esta el tesoro, pero tarda 4 das en calcularlo.
Un elfo que pasa por el puerto te ofrece un trato: te da la solucion
ahora mismo si le pagas el equivalente a lo que se llevara el dragon
en 3 noches
Que puedes hacer?
Yolanda Garca, Jes
us Correas (DSIC - UCM)
5 / 54
Caractersticas generales (Cont.)
Que puedes hacer?
a) Puedes quedarte 4 das en el puerto hasta resolver el misterio, llegar al
tesoro 9 das despues, y obtener x 9y lingotes de oro.
b) Puedes aceptar el trato con el elfo, llegar al tesoro en 5 das y pagar al
elfo a la vuelta. En total, obtienes x 8y lingotes.
Parece que lo mejor es aceptar el trato...
Yolanda Garca, Jes
us Correas (DSIC - UCM)
6 / 54
Caractersticas generales (Cont.)
Que puedes hacer?
a) Puedes quedarte 4 das en el puerto hasta resolver el misterio, llegar al
tesoro 9 das despues, y obtener x 9y lingotes de oro.
b) Puedes aceptar el trato con el elfo, llegar al tesoro en 5 das 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):
I
I
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 Garca, Jes
us Correas (DSIC - UCM)
6 / 54
Caractersticas generales (Cont.)
Diferencias entre algoritmos deterministas y probabilistas:
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 mas de una solucion para unos datos dados, un algoritmo
determinista siempre encuentra la misma solucion (a no ser que se
programe para encontrar varias o todas las soluciones).
Un algoritmo probabilista puede encontrar soluciones diferentes
ejecutandose varias veces con los mismos datos
Yolanda Garca, Jes
us Correas (DSIC - UCM)
7 / 54
Caractersticas generales (Cont.)
Diferencias entre algoritmos deterministas y probabilistas (cont.):
3. A un algoritmo determinista no se le permite que calcule una
solucion incorrecta para ningun dato
Un algoritmo probabilista puede equivocarse siempre que esto ocurra con
una probabilidad peque
na para cada dato de entrada.
Repitiendo la ejecucion un n
umero suficiente de veces para el mismo dato,
puede aumentarse tanto como se quiera el grado de confianza en obtener
la solucion correcta
4. El analisis de la eficiencia de un algoritmo determinista es, a veces,
difcil
El analisis de los algoritmos probabilistas es, muy a menudo, muy difcil
Yolanda Garca, Jes
us Correas (DSIC - UCM)
8 / 54
Caractersticas generales. Certeza y probabilidad
Algunos algoritmos probabilistas dan respuestas probabilistas:
respuestas no necesariamente exactas.
Un algoritmo determinista tampoco garantiza siempre la certeza de la
solucion; durante su calculo se pueden producir fallos de hardware que
pasen inadvertidos y que lleven a una soluci
on equivocada.
A veces la probabilidad de error en la respuesta obtenida por un
algoritmo probabilista es menor que la de un fallo de hardware
mientras se calcula la respuesta mediante un algoritmo determinista.
Por tanto, puede suceder que la respuesta incierta producida por un
algoritmo probabilista sea:
I
I
Mas rapida de calcular
Mas fiable
que la respuesta exacta de un algoritmo determinista.
En muchos casos es mejor un algoritmo probabilista rapido que
de la solucion correcta con una cierta probabilidad de error
Yolanda Garca, Jes
us Correas (DSIC - UCM)
9 / 54
Caractersticas generales. Definiciones
Tiempo promedio: Es el tiempo que tarda un algoritmo cuando
todos los ejemplares de un tama
no dado son igualmente probables.
I
Inconveniente: Esta medida no es valida si los ejemplares no son
equiprobables.
Tiempo esperado: Es el tiempo promedio que tarda un algoritmo
probabilista para resolver un solo ejemplar de un tama
no dado.
I
Ventaja: No depende de la distribuci
on de probabilidades de los
distintos ejemplares del mismo tama
no.
Tiempo esperado en el caso peor: Es el tiempo esperado del peor
ejemplar de un tama
no dado.
I
NO ES el tiempo que requiere el algoritmo si se toman las peores
decisiones probabilistas.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
10 / 54
Caractersticas generales. Numeros pseudoaleatorios
Para poder tomar decisiones probabilistas, utilizaremos un generador
de n
umeros pseudoaleatorios.
Dados dos n
umeros naturales a y b tales que a < b, supondremos que
una llamada a uniforme(a,b) devuelve un n
umero real x
seleccionado aleatoriamente en el intervalo a x < b.
La distribucion de x es uniforme en [a, b), por lo que sucesivas
llamadas a uniforme(a,b) devuelven valores independientes de x.
Utilizaremos uniforme(i..j) para generar n
umeros enteros
aleatorios k tales que i k j.
Por u
ltimo, tiramoneda() devuelve cara o cruz de forma aleatoria
con una probabilidad del 50 % para cada una de ellas.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
11 / 54
Caractersticas generales. Numeros pseudoaleatorios (cont.)
En la practica no existen generadores realmente aleatorios; los
existentes son generadores pseudoaleatorios:
Son procedimientos deterministas que generan sucesiones de valores
que parecen tener las propiedades de una sucesi
on aleatoria.
Para iniciar una sucesi
on se debe proporcionar un valor inicial
denominado semilla. La misma semilla proporciona siempre la misma
sucesion.
Normalmente la semilla depende de la fecha o la hora del sistema.
Por ejemplo, en C++ se proporciona la semilla (que es funcion de la
hora del sistema) utilizando randomize()
Yolanda Garca, Jes
us Correas (DSIC - UCM)
12 / 54
Algoritmos Probabilistas
1
2
Caractersticas generales
Clasificacion de los algoritmos probabilistas
Algoritmos probabilistas numericos
Algoritmos de Monte Carlo
Algoritmos de Las Vegas
Yolanda Garca, Jes
us Correas (DSIC - UCM)
13 / 54
Clasificacion de los algoritmos probabilistas
1
Algoritmos que no garantizan la correcci
on de la solucion
I
Algoritmos numericos
F
F
F
F
Dan una soluci
on aproximada
Cuanto m
as tiempo de ejecuci
on se conceda a estos algoritmos, mejor
ser
a la aproximaci
on
Ejemplo: Con una probabilidad del 90 %, la respuesta correcta es 59 2
Son u
tiles si nos basta con una respuesta aproximada
Yolanda Garca, Jes
us Correas (DSIC - UCM)
14 / 54
Clasificacion de los algoritmos probabilistas
1
Algoritmos que no garantizan la correcci
on de la solucion
I
Algoritmos numericos
F
F
F
F
I
Dan una soluci
on aproximada
Cuanto m
as tiempo de ejecuci
on se conceda a estos algoritmos, mejor
ser
a la aproximaci
on
Ejemplo: Con una probabilidad del 90 %, la respuesta correcta es 59 2
Son u
tiles si nos basta con una respuesta aproximada
Algoritmos de Monte Carlo
F
F
F
Dan una respuesta exacta con una probabilidad muy grande. Pero
tambien puede producir respuestas incorrectas
No se puede saber si la respuesta producida es correcta o no
Se puede reducir la probabilidad de error si se alarga la ejecuci
on
Yolanda Garca, Jes
us Correas (DSIC - UCM)
14 / 54
Clasificacion de los algoritmos probabilistas
1
Algoritmos que no garantizan la correcci
on de la solucion
I
Algoritmos numericos
F
F
F
F
I
Algoritmos de Monte Carlo
F
F
F
2
Dan una soluci
on aproximada
Cuanto m
as tiempo de ejecuci
on se conceda a estos algoritmos, mejor
ser
a la aproximaci
on
Ejemplo: Con una probabilidad del 90 %, la respuesta correcta es 59 2
Son u
tiles si nos basta con una respuesta aproximada
Dan una respuesta exacta con una probabilidad muy grande. Pero
tambien puede producir respuestas incorrectas
No se puede saber si la respuesta producida es correcta o no
Se puede reducir la probabilidad de error si se alarga la ejecuci
on
Algoritmos que nunca dan una soluci
on incorrecta
I
Algoritmos de Las Vegas
F
F
Nunca dan una respuesta incorrecta
Verifican que la soluci
on encontrada sea correcta. Si no es correcta lo
admiten
Es posible volver a ejecutar el algoritmo con los mismos datos hasta
obtener la soluci
on correcta
Yolanda Garca, Jes
us Correas (DSIC - UCM)
14 / 54
Algoritmos Probabilistas
Caractersticas generales
Clasificacion de los algoritmos probabilistas
Algoritmos probabilistas numericos
I
I
La aguja de Buffon: calculo del n
umero
Integraci
on numerica
Algoritmos de Monte Carlo
Algoritmos de Las Vegas
Yolanda Garca, Jes
us Correas (DSIC - UCM)
15 / 54
La aguja de Buffon
Supongamos que se tira una aguja sobre el suelo
Dicho suelo esta hecho de planchas de madera de anchura constante.
La separacion entre las distintas planchas es 0.
La longitud de la aguja es la mitad de la anchura de las planchas
En el siglo XVIII, el conde de Buffon demostr
o que la probabilidad de
1
que la aguja caiga encima de una rendija es
As, este teorema sirve para predecir de forma aproximada cuantas
agujas caeran entre dos planchas si dejamos caer n agujas: n
Mas interesante: sirve para calcular el valor de .
Se dejan caer n agujas y se cuentan el n
umero de agujas k que han
cado entre dos planchas.
Se puede utilizar
n
k
Yolanda Garca, Jes
us Correas (DSIC - UCM)
como aproximaci
on de
16 / 54
La aguja de Buffon (Cont.)
Es u
til este metodo?
Cuanto mas precisa se quiera la aproximaci
on, mas agujas de deben
dejar caer
La convergencia es muy lenta: para obtener un valor de 0,01 con
probabilidad 0,9 se necesitan tirar 1.500.000 agujas
En la practica, este mecanismo para calcular el valor aproximado de
no es u
til, porque se pueden obtener aproximaciones de mucho
mejores utilizando algoritmos deterministas
Es posiblemente el primer algoritmo probabilista de la historia
Yolanda Garca, Jes
us Correas (DSIC - UCM)
17 / 54
Integracion numerica
Problema:
Dada una funcion f : R R+ continua y un intervalo [a, b], el area
de la superficie limitada por la curva
y = f (x), el eje x y las lneas
Calcular:
b
verticales x = a y x = b es:
+
I=
f (x) d x ,
a
donde f :R R
es continua
f
Z
I =
f (x) dx
a
I
b a
I
Sea el rectangulo de base b a y de altura ba
I/(b-a)
es
la
altura
media de f entre a y b.
a) El area del rectangulo es I
b) El area de la superficie bajo la curva tambien es I
Con a) y b) podemos concluir que el rectangulo y la curva tienen la
misma altura media
Yolanda Garca, Jes
us Correas (DSIC - UCM)
18 / 54
Integracion numerica (Cont.)
Z
Dise
nar un algoritmo probabilista para calcular I =
f (x) dx
a
Am de
Se puede hacer una estimaci
on de la altura media
la curva por
muestreo aleatorio
Una aproximacion de la integral sera en este caso I = Am (b a)
fun intMC(f, n, a, b)
suma 0
desde i 1 hasta n hacer
x uniforme(a,b)
suma suma + f(x)
fin desde
devolver (b a) (suma n)
fin fun
Esto tambien se podra haber hecho con un algoritmo determinista,
que calcule el valor de f (x) a intervalos regulares.
Sin embargo, esto no funciona en todos los casos.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
19 / 54
Algoritmos Probabilistas
Caractersticas generales
Clasificacion de los algoritmos probabilistas
Algoritmos probabilistas numericos
Algoritmos de Monte Carlo
I
I
Verificaci
on de la multiplicaci
on de matrices
Comprobaci
on de primalidad
Algoritmos de Las Vegas
Yolanda Garca, Jes
us Correas (DSIC - UCM)
20 / 54
Algoritmos de Monte Carlo
Hay problemas para los que no se conocen soluciones deterministas ni
probabilistas que den siempre una soluci
on correcta (ni siquiera
aproximada).
Los algoritmos de Monte Carlo dan a veces una solucion incorrecta, y
con una probabilidad conocida una soluci
on correcta.
Para estos algoritmos es necesaria una definici
on de correccion
probabilista:
Un algoritmo de Monte Carlo es p-correcto, con 0 < p < 1, si
devuelve una solucion correcta con probabilidad mayor o igual
que p, cualesquiera que sean los datos de entrada.
A veces, p depende del tama
no de la entrada, pero no de los datos
concretos del ejemplar.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
21 / 54
Verificacion de la multiplicacion de matrices
Dadas tres matrices n n, A, B y C . Se quiere comprobar que se
cumple C = AB.
La solucion mas sencilla consiste en realizar la multiplicacion de
matrices y comparar el resultado con C .
El inconveniente de este enfoque es el coste: la multiplicacion
tradicional esta en O(n3 ). Con Strassen, en O(n2,81 ), y con el mejor
metodo conocido hasta ahora para multiplicar matrices, en O(n2,37 ).
Vamos a estudiar un algoritmo de Monte Carlo que resuelve este
problema en O(n2 ), para una probabilidad de error dada .
Yolanda Garca, Jes
us Correas (DSIC - UCM)
22 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Supongamos que C 6= AB. Entonces, D = AB C , donde D no es
una matriz nula. Sea i la fila i-esima de D que contiene al menos un
elemento distinto de 0.
Sea S un subconjunto cualquiera de ndices de filas, S {1, . . . , n}.
Sea S (D) la suma de las filas de D cuyos ndices estan en S
0 un conjunto igual a S, excepto por el elemento i:
Sea S
S {i} si i
/S
S0 =
S \ {i} si i S
Como D no es la matriz nula, S (D) y S 0 (D) no pueden ser nulos
simultaneamente.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
23 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Podemos generar el conjunto S de forma aleatoria:
I
I
I
Para cada j entre 1 y n, decidimos al azar si j se incluye en S o no.
La probabilidad de que i este en S es de 1/2.
Por tanto, la probabilidad de que S (D) 6= 0 es como mnimo 1/2.
Por otra parte, S (D) siempre es cero si C = AB.
La solucion esta en calcular S (D) y compararlo con 0. Pero
debemos evitar calcular D, pues el coste del producto AB es
demasiado alto.
La solucion es considerar S (D) como un producto de matrices:
S (D) = XD, siendo X un vector 1 n con Xi = 1 si i S, y Xi = 0
en caso contrario.
Pero XD = X (AB C ) = XAB XC . En un tema anterior vimos
que la agrupacion apropiada de productos de matrices puede mejorar
mucho la eficiencia del producto de matrices. En concreto, (XA)B
tiene una complejidad que esta en O(n2 ).
Yolanda Garca, Jes
us Correas (DSIC - UCM)
24 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Un algoritmo que calcule esto puede ser de la forma:
fun verifmat(A, B, C, n)
desde j 1 hasta n hacer
X[j] uniforme(0..1)
fin desde
si (XA)B = XC entonces devolver cierto
si no devolver falso
fin fun
Este algoritmo devuelve cierto como respuesta correcta con una
probabilidad del 50 %.
I
No parece demasiado interesante: tirar una moneda al aire para decidir
si C = AB tambien tiene una probabilidad del 50 %...
Sin embargo, si devuelve falso, podemos asegurar que la respuesta
es correcta.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
25 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Esto nos da una pista sobre c
omo podemos tener mas certeza sobre la
respuesta afirmativa:
Podemos aplicar verifmat(A, B, C, n) varias veces sobre el
mismo caso, utilizando valores independientes para el vector X cada
vez.
Es suficiente que verifmat(A, B, C, n) devuelva falso una sola
vez para decidir que AB 6= C .
Podemos utilizar el siguiente algoritmo:
fun repetir verifmat(A, B, C, n, k)
desde i 1 hasta k hacer
si verifmat(A, B, C, n) entonces devolver falso
fin desde
devolver cierto
fin fun
Yolanda Garca, Jes
us Correas (DSIC - UCM)
26 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Vamos a analizar la probabilidad de error de este algoritmo.
Si AB = C , toda llamada a verifmat(A, B, C, n) devuelve
cierto, por lo que repetir verifmat(A, B, C, n, k)
tambien devuelve cierto
Si AB 6= C , la probabilidad de que una llamada a verifmat(A,
B, C, n) devuelva cierto incorrectamente es 1/2.
Dos llamadas independientes a verifmat(A, B, C, n) que
devuelvan cierto de forma incorrecta tienen una probabilidad conjunta
de 1/4.
En el caso general, la probabilidad de que k llamadas consecutivas a
verifmat(A, B, C, n) devuelvan cierto incorrectamente es
2k .
Dicho de otra forma, la probabilidad de que el algoritmo anterior
devuelva un resultado correcto es 1 2k : el algoritmo es
(1 2k )-correcto.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
27 / 54
Verificacion de la multiplicacion de matrices (Cont.)
Para k = 10, es 99,9 %-correcto.
Para k = 20, la probabilidad de error es menor a una entre un millon.
La complejidad de este algoritmo esta en (n2 k)
Teniendo en cuenta que se realizan 3n2 multiplicaciones escalares
para calcular XAB y XC , si k = 20 es necesario realizar 60n2
multiplicaciones.
Por tanto, este metodo es mas eficiente que el producto tradicional de
matrices si la dimensi
on de las matrices n es mayor a 60.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
28 / 54
Comprobacion de primalidad
Un problema muy relevante que se puede resolver con el metodo de
Monte Carlo es el de determinar si un n
umero es primo.
Es el algoritmo de Monte Carlo mas conocido.
Este problema es especialmente u
til para las tecnicas criptograficas,
que se basan en la factorizaci
on de n
umeros muy grandes en factores
primos.
No se conoce ning
un algoritmo determinista que resuelva este
problema en un tiempo razonable para n
umeros muy grandes (cientos
de dgitos decimales).
Yolanda Garca, Jes
us Correas (DSIC - UCM)
29 / 54
Comprobacion de primalidad (Cont.)
La verificacion probabilista de primalidad de un n
umero se basa en el
teorema menor de Fermat(1640):
Sea n un n
umero primo. Entonces an1 mod n = 1 para
cualquier entero a tal que 1 a n 1
Por ejemplo, sean n = 7 y a = 5. Entonces,
an1 = 56 = 15625 = 2232 7 + 1
Utilizaremos la versi
on contrapositiva de este teorema:
Si n y a son enteros tales que 1 a n 1 y
an1 mod n 6= 1, entonces n no es un n
umero primo.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
30 / 54
Comprobacion de primalidad (Cont.)
Aunque no lo hemos visto, existe un algoritmo basado en la tecnica
Divide y Venceras que permite realizar la exponenciacion modular
(resolver an mod z) que esta en (log n) ([BB97], p.279). Utilizando
dos propiedades elementales de aritmetica modular:
xy mod z = [(x mod z) (y mod z)] mod z
(x mod z)y mod z = x y mod z
fun expomod(a, n, z) // calcula an mod z
i n ; r 1 ; x a mod z // errata en [BB97]
mientras i > 0 hacer
si i es impar entonces r rx mod z // errata en [BB97]
x x2 mod z
i bi/2c
fin mientras
devolver r
fin fun
Vamos a utilizar este algoritmo para dar una version probabilista de la
comprobacion de primalidad
Yolanda Garca, Jes
us Correas (DSIC - UCM)
31 / 54
Comprobacion de primalidad (Cont.)
Para verificar que un n
umero n es primo, habra que comprobar que
todos los valores a entre 1 y n 1 cumplen que an1 mod n = 1.
Podramos probarlo con un solo n
umero elegido al azar entre 1 y n 1
La primera version de nuestro algoritmo probabilista es:
fun Fermat(n)
a uniforme(1..n-1)
si expomod(a,n-1,n)=1 entonces devolver cierto
devolver falso
fin fun
Yolanda Garca, Jes
us Correas (DSIC - UCM)
32 / 54
Comprobacion de primalidad (Cont.)
Para verificar que un n
umero n es primo, habra que comprobar que
todos los valores a entre 1 y n 1 cumplen que an1 mod n = 1.
Podramos probarlo con un solo n
umero elegido al azar entre 1 y n 1
La primera version de nuestro algoritmo probabilista es:
fun Fermat(n)
a uniforme(1..n-1)
si expomod(a,n-1,n)=1 entonces devolver cierto
devolver falso
fin fun
Como en el caso anterior, cuando Fermat(n) devuelva falso
estaremos seguros de que n no es primo.
Sin embargo, si Fermat(n) devuelve cierto no podemos concluir
nada ...
Yolanda Garca, Jes
us Correas (DSIC - UCM)
32 / 54
Comprobacion de primalidad (Cont.)
Ejemplos:
I
I
Por ejemplo, (1)n1 mod n = 1 para todo n 2.
Por ejemplo, (n 1)n1 mod n = 1 para todo n 3.
Dado un n
umero n no primo, los valores de a tales que
n1
a
mod n = 1 se denominan testigos falsos de primalidad
Yolanda Garca, Jes
us Correas (DSIC - UCM)
33 / 54
Comprobacion de primalidad (Cont.)
Ejemplos:
I
I
Por ejemplo, (1)n1 mod n = 1 para todo n 2.
Por ejemplo, (n 1)n1 mod n = 1 para todo n 3.
Dado un n
umero n no primo, los valores de a tales que
n1
a
mod n = 1 se denominan testigos falsos de primalidad
Modificacion del algoritmo de Fermat:
Elegir a entre 2 y n 2
Existen casos no triviales (a 6= 1, a 6= n 1) en los que falla el
algoritmo anterior. Ejemplo:
414 mod 15 = 1
sin embargo 15 no es primo.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
33 / 54
Comprobacion de primalidad (Cont.)
Afortunadamente, no existen demasiados testigos falsos: la media de
error de Fermat(n) para los impares menores a 1000 es inferior al
3,3 %.
Sin embargo, hay excepciones:
I
I
561 admite 318 testigos falsos.
A
un peor: Fermat(651693055693681) devuelve cierto con una
probabilidad mayor al 99,9965 %, pero este n
umero no es primo.
Ademas, el algoritmo anterior no es p-correcto para ning
un p > 0:
no es posible reducir la probabilidad de error repitiendo la ejecucion
del algoritmo.
Tenemos que buscar otra manera de enfrentarnos a este
problema.
Vamos a utilizar otro algoritmo basado en una extension del teorema
de Fermat.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
34 / 54
Comprobacion de primalidad (Cont.)
Necesitamos la siguiente definici
on: Sea n > 4 un entero impar, y
sean s y t enteros tales que n 1 = 2s t, con t impar. Definimos el
conjunto B(n) de la forma siguiente:
a B(n) si y solo si 2 a n 2 y ademas
I
I
at mod n = 1, o bien
i
Existe un entero i, 0 i < s tal que a2 t mod n = n 1
Por ejemplo, vamos a comprobar si a = 158 esta en B(289).
I
I
I
Podemos comprobar que s = 5 y t = 9 cumplen las propiedades
anteriores: t es impar y 25 9 = 289 1
at mod n = 1589 mod 289 = 131.
No se cumple la primera parte de la definici
on. Vamos a ver si se
cumple la segunda:
Probamos diversos valores de i, 0 < i < 5:
1
a2 t mod n = 15829 mod 289 = 110
2
a2 t mod n = 15849 mod 289 = 251
3
a2 t mod n = 15889 mod 289 = 288 = 289 1
Yolanda Garca, Jes
us Correas (DSIC - UCM)
35 / 54
Comprobacion de primalidad (Cont.)
Teorema
Consideremos un n
umero impar arbitrario n > 4.
Si n es primo, entonces B(n) = {a | 2 a n 2}.
Si n no es primo, entonces |B(n)| (n 9)/4.
a diferencia del teorema menor de Fermat,
I
Aunque pueden existir valores de a B(n) que cumplen las condiciones
anteriores y n sea compuesto,
se garantiza que la proporci
on de n
umeros entre 2 y n 2 que
est
an en B(n) es peque
na para todo n compuesto.
Calcular B(n) puede parecer complicado, pero se puede implementar
facilmente de forma eficiente
Yolanda Garca, Jes
us Correas (DSIC - UCM)
36 / 54
Comprobacion de primalidad (Cont.)
El algoritmo probabilista que permite determinar la primalidad seg
un este teorema
es el siguiente:
fun FermatB(a, n)
s 0 ; t n-1
repetir
// algoritmo de Miller-Rabin
s s+1 ; t bt/2c
fun MillerRabin(n)
hasta t mod 2 = 1
// n debe ser impar
x expomod(a, t, n)
// y mayor a 4
si x=1 x=n-1 entonces devolver cierto
a uniforme(2..n-2)
desde i 1 hasta s-1 hacer
devolver FermatB(a, n)
x x2 mod n (*)
fin fun
si x=n-1 entonces devolver cierto
fin desde
devolver falso
fin fun
(*) se puede demostrar que (x a mod n)b mod n = x ab mod n
Este algoritmo es 3/4-correcto para la comprobaci
on de primalidad.
Adem
as, garantiza que la respuesta falso es correcta. Por tanto, repitiendo el
algoritmo se puede reducir r
apidamente la probabilidad de error.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
37 / 54
Comprobacion de primalidad (Cont.)
El algoritmo que realiza sucesivas llamadas al anterior es:
fun RepetirMillerRabin(n,k) // n debe ser impar y mayor a 4
desde i 1 hasta k hacer
si MillerRabin(n) entonces devolver falso
fin desde
devolver cierto
fin fun
Este algoritmo devuelve siempre la respuesta correcta cuando n es
primo.
Cuando n no es primo, la probabilidad de que MillerRabin(n)
devuelva la respuesta incorrecta es de 1/4.
La probabilidad de que la respuesta sea incorrecta despues de repetir
la prueba k veces es 4k : RepetirMillerRabin(n,k) es
(1 4k )-correcto.
Por tanto, basta con tomar k = 10 para que la probabilidad sea
inferior a una entre un mill
on.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
38 / 54
Comprobacion de primalidad (Cont.)
Sin embargo, existe la posibilidad de que el algoritmo anterior decida
erroneamente que un n
umero es primo.
Pero cualquier entero mayor a 1 o es primo, o es compuesto, pero no
probablemente primo.
Podramos utilizar un metodo determinista mas sofisticado que
asegure si un n
umero es primo o no. Este algoritmo sera bastante
mas costoso que RepetirMillerRabin(n,150).
Pero 4150 10100 . Es bastante menos probable que
RepetirMillerRabin(n,150) falle a que se produzca un fallo
de hardware en el algoritmo determinista.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
39 / 54
Algoritmos Probabilistas
Caractersticas generales
Clasificacion de los algoritmos probabilistas
Algoritmos probabilistas numericos
Algoritmos de Monte Carlo
Algoritmos de Las Vegas
I
I
El problema de las 8 reinas
Ordenaci
on probabilista
Yolanda Garca, Jes
us Correas (DSIC - UCM)
40 / 54
Algoritmos de Las Vegas
Un algoritmo de Las Vegas NUNCA da una solucion falsa.
Toman decisiones al azar (decisiones probabilistas) para encontrar una
solucion mas rapido que un algoritmo determinista
Si no son capaces de encontrar una soluci
on, lo admiten
Clasificacion (dependiendo de si encuentran o no la solucion):
I
Los que siempre encuentran la soluci
on correcta. En este caso, es
posible que sean poco eficientes si la decisi
on probabilista no es
afortunada
Los que a veces, debido a decisiones poco afortunadas, llegan a un
callej
on sin salida y no son capaces de encontrar una soluci
on
Yolanda Garca, Jes
us Correas (DSIC - UCM)
41 / 54
Algoritmos de Las Vegas (Cont.)
Para el primer tipo: los que siempre encuentran la soluci
on correcta.
Se aplican a problemas en los que la versi
on determinista es mucho
mas rapido en el caso promedio que en el caso peor (Ej. Quicksort)
I
Coste peor (n2 ) y coste promedio O(nlogn)
Los algoritmos de las Vegas pueden reducir o eliminar las diferencias
de eficiencia para distintos datos de entrada
I
Con mucha probabilidad, los casos que requieran mucho tiempo con el
metodo determinista se resuelven ahora mucho mas deprisa
En los casos en los que el algoritmo determinista sea muy eficiente, se
resuelven ahora con mas coste
En el caso promedio, no se mejora el coste
Uniformizacion del tiempo de ejecuci
on para todas las entradas de
igual tama
no
Yolanda Garca, Jes
us Correas (DSIC - UCM)
42 / 54
Algoritmos de Las Vegas (Cont.)
Para el segundo tipo: algoritmos que a veces no dan respuesta.
Son aceptables si fallan con probabilidad baja
Si fallan se vuelven a ejecutar con los mismos datos de entrada
Se utilizan para resolver problemas para los que no se conocen
algoritmos deterministas eficientes que los resuelvan
Tiempo de ejecucion no esta acotado pero es razonable con una
elevada probabilidad.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
43 / 54
Algoritmos de Las Vegas (Cont.)
Para el segundo tipo: algoritmos que a veces no dan respuesta(Cont.).
Se presentan en forma de procedimiento con una variable exito que
toma valor cierto si se obtiene soluci
on y falso en otro caso
LV(x, solucion, exito)
donde x representa los datos de entrada
Sea p(x) la probabilidad de exito si la entrada es x.
Los algoritmos de Las Vegas exigen que p(x) > 0 para todo x
Sea la siguiente funci
on
fun repetir LV(x)
repetir
LV(x, solucion, exito)
hasta exito
devolver solucion
fin fun
Yolanda Garca, Jes
us Correas (DSIC - UCM)
44 / 54
Algoritmos de Las Vegas (Cont.)
Para el segundo tipo: algoritmos que a veces no dan respuesta(Cont.).
El n
umero de pasadas del bucle es
I
I
1
p(x)
Sea t(x) el tiempo esperado de repetir LV (x)
La primera llamada a LV tiene exito al cabo de un tiempo s(x) con
probabilidad p(x)
La primera llamada a LV fracasa al cabo de un tiempo f (x) con
probabilidad 1 p(x).
El tiempo esperado total en este caso es f (x) + t(x), porque despues
de que la llamada a LV fracase volvemos a estar en el punto de partida
(y por tanto volvemos a necesitar un tiempo t(x)).
As, t(x) = p(x)s(x) + (1 p(x))(f (x) + t(x))
Resolviendo la ecuaci
on anterior se obtiene:
t(x) = s(x) +
1p(x)
p(x) f (x)
Esta ecuacion es la clave para optimizar el rendimiento de este tipo
de algoritmos
Yolanda Garca, Jes
us Correas (DSIC - UCM)
45 / 54
Problema de las 8 reinas
El algoritmo determinista utilizando Backtracking obtiene la primera
solucion despues de visitar 114 nodos de los de los 2057 nodos del
arbol de b
usqueda
Algoritmo de Las Vegas voraz: colocar cada reina aleatoriamente en
filas sucesivas ocupandose de no poner una nueva reina en una
posicion que sea amenazada por otra reina ya situada
Como resultado:
I
El algoritmo acaba con exito si es capaz de colocar todas las reinas en
el tablero
Fracasa si no es capaz de colocar la siguiente reina
Yolanda Garca, Jes
us Correas (DSIC - UCM)
46 / 54
Problema de las 8 reinas (Cont.)
proc reinasLV(solucion[1..8], exito)
crear ok[1..8] //vector que contiene las posiciones disponibles
columnas, diagonal1, diagonal2 //columnas y diagonales amenazadas
k 1, exito cierto
mientras k 8 exito hacer
colPosibles 0 //n
umero de columnas no amenazadas por otras reinas
desde j 1 hasta 8 hacer
si j
/ columnas j-(k-1)
/ diagonal1 j+(k-1)
/ diagonal2 entonces
colPosibles colPosibles + 1
ok[colPosibles] j
fin si
fin desde
si colPosibles = 0 entonces exito falso
si no
pos ok[uniforme(1..colPosibles)]
columnas columnas {pos}
diagonal1 diagonal1 {pos (k 1)} // Diagonal descendente
diagonal2 diagonal2 {pos + (k 1)} // Diagonal ascendente
k k+1
fin si
fin mientras
fin proc
Yolanda Garca, Jes
us Correas (DSIC - UCM)
47 / 54
Problema de las 8 reinas (Cont.)
En este algoritmo se puede medir experimentalmente su complejidad
Utilizamos como medida de complejidad el n
umero de nodos
explorados
I
I
I
I
Probabilidad de exito: p 0,1293
N
umero medio de nodos que explora en caso de exito: s = 9 (incluido
el nodo inicial con 0 reinas colocadas)
N
umero esperado de nodos explorados en caso de fracaso: f 6,971
N
umero esperado de nodos visitados repitiendo hasta obtener exito:
t(x) = s(x) +
1p(x)
p(x) f
(x) ' 55, 93
Menos de la mitad del n
umero de nodos explorados con backtracking
Yolanda Garca, Jes
us Correas (DSIC - UCM)
48 / 54
Problema de las 8 reinas (Cont.)
Se puede resolver este problema combinando las dos t
ecnicas:
backtracking y Las Vegas
Se trata de poner las k-primeras reinas al azar y dejarlas fijas y con el
resto usar el algoritmo de b
usqueda con retroceso
Cuantas mas reinas pongamos al azar:
I
I
Menos tiempo se precisa para encontrar una solucion o para fallar
Mayor es la probabilidad de fallo
El procedimiento quedara as:
Yolanda Garca, Jes
us Correas (DSIC - UCM)
49 / 54
Problema de las 8 reinas (Cont.)
proc reinasLV b(solucion[1..8], reinasFijas, exito)
crear ok[1..8] //vector que contiene las posiciones disponibles
columnas, diagonal1, diagonal2 //columnas y diagonales amenazadas
k 1, exito cierto
mientras k reinasFijas and exito hacer
colPosibles 0 //n
umero de columnas no amenazadas por otras reinas
desde j 1 hasta 8 hacer
si j
/ columnas j-(k-1)
/ diagonal1 j+(k-1)
/ diagonal2 entonces
colPosibles colPosibles + 1
ok[colPosibles] j
fin si
fin desde
si colPosibles = 0 entonces exito falso
si no
pos ok[uniforme(0..colPosibles)]
columnas columnas pos
diagonal1 diagonal1 {pos (k 1)} ; diagonal2 diagonal2 {pos + (k 1)}
k k+1
fin si
fin mientras
si exito entonces backtracking(solucion, reinasFijas, exito)
fin proc
Yolanda Garca, Jes
us Correas (DSIC - UCM)
50 / 54
Problema de las 8 reinas (Cont.)
Reinas fijas
0
1
2
3
4
5
6
7
8
p
1,0000
1,0000
0,8750
0,4931
0,2618
0,1624
0,1357
0,1293
0,1293
s
114,00
39,63
22,53
13,48
10,31
9,33
9,05
9,00
9,00
f
39,67
15,10
8,79
7,29
6,98
6,97
6,97
t
114,00
39,63
28,20
29,01
35,10
46,92
53,50
55,93
55,93
0,45 ms
Caso determinista puro
0,14 ms
0,21 ms
1 ms
Caso probabilista puro
El valor optimo es colocar 2 reinas al azar
El caso ReinasFijas = 3 falla en la mitad de los casos, pero es muy
rapido tanto si tiene exito como si falla
Yolanda Garca, Jes
us Correas (DSIC - UCM)
51 / 54
Problema de las 8 reinas (Cont.)
Para un tablero de 39 39
Reinas fijas
0
29
39
p
1
0,21
0,0074
Yolanda Garca, Jes
us Correas (DSIC - UCM)
t
11402835415
500
Tiempo
41 horas
8,5 ms
150 ms
Determinista puro
Probabilista puro
52 / 54
Quicksort
El algoritmo de ordenaci
on Quicksort que vimos en la tecnica Divide y
Venceras utiliza el primer elemento del vector como pivote para dividir
el resto de la lista en dos sublistas: una con los elementos menores al
pivote, y otra con los elementos mayores al pivote.
El algoritmo determinista es muy eficiente en el caso medio: esta en
O(n log n)
Sin embargo, si el vector ya esta ordenado, esta en O(n2 )
En este caso tambien podemos aplicar la tecnica probabilista en la
eleccion del pivote: en lugar de elegir siempre el primer elemento, lo
que penaliza los vectores (casi) ordenados, se toma un elemento del
vector al azar.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
53 / 54
Quicksort
El algoritmo tiene el siguiente aspecto:
proc quicksortLV(S[i..j])
si i<j entonces
p S[uniforme(i..j)]
particion(S[i..j],p,k,l) // particion in-place
quicksortLV(S[i..k])
quicksortLV(S[l..j])
fin si
fin proc
En este caso el tiempo esperado para el caso peor esta en O(n log n),
en lugar de tener un coste cuadratico.
Yolanda Garca, Jes
us Correas (DSIC - UCM)
54 / 54
