PDF de programación - Algoritmos Probabilistas

ALGORITMOS PROBABILISTAS

NUMÉRICOS
SHERWOOD
LAS VEGAS

MONTE CARLO

 

INTRODUCCIÓN

• Algoritmo probabilista: Deja al azar la 

toma de algunas decisiones.
– Cuando la decisión óptima llevaría mucho 

tiempo.

– Problemas con múltiples soluciones correctas.

• Ejemplos:

– Encontrar el k­ésimo menor elemento de un 

vector de n elementos

– Problema de las ocho reinas.
– Encontrar un factor de un número compuesto

 

ALGORITMOS PROBABILISTAS

• Supondremos un generador de números 

aleatorios de coste unitario

uniforme (a,b) < b con a, b   de R
 uniforme (i..j) £
   j con i, j   de Z

– a £
– i £
– uniforme (x) de X conjunto finito no vacío

• En la práctica generadores seudoaleatorios  a 

partir de una semilla.

 

CLASIFICACIÓN  DE ALGORITMOS 

PROBABILISTAS

• Numéricos: Solución aproximada a problemas numéricos 
para  los  que  es  imposible  dar  una  respuesta  exacta.  Su 
precisión  es  mayor  cuanto  más  tiempo  se  le  dedique  al 
algoritmo.

• Monte  Carlo:  Dan  una  respuesta  concreta  pero  ésta  no 

tiene por qué ser correcta.

• Las Vegas: Su  respuesta  es siempre correcta pero puede 

no encontrarla. 

• Sherwood: Dan siempre respuesta y ésta es correcta. 
 

ALGORTIMOS PROBABILISTAS

NUMÉRICOS

Aproximad
amente....

 

ALGORTIMOS PROBABILISTAS NUMÉRICOS

• Estimación aproximada de P
• Tiramos n dardos sobre cuadrado y 

:

contamos el número k de los que caen 
en un círculo inscrito en el cuadrado.

• ¿Cuál es la proporción media de 
dardos en el interior del círculo?:
r2/4r2 = P
• ¿Cómo se puede estimar P ?: P

/4

@

4k/n

 

P
ALGORTIMOS PROBABILISTAS NUMÉRICOS

Estimación de p

Función dardos(n)

 0

k ‹
para i ‹ 1 hasta n hacer
x ‹
y ‹
si x2 +y2  <=1 entonces k‹
devolver 4k / n

 uniforme(0,1)
 uniforme(0,1)

k+1

• ¿Qué valor se estimaría si se 

hiciera?
x ‹
y ‹

uniforme(0,1)
 x

 

INTEGRACIÓN NUMÉRICA

f: [0,1]fi
 [0,1] es una función continua entonces el área de la 
superficie delimitada por la  curva y = f(x),  por el eje x,  por eje 
y,  y por la derecha x=1 viene dada por:

1

f x dx

( )

•

•

0

1

1(4

0

x 2/12
)

dx

0

función curva(n)
k ‹
para i ‹ 1 hasta n hacer
x‹
y ‹
si  y <= f(x) entonces k‹
devolver k/n

 uniforme(0,1)
uniforme(0,1)

 k+1

• Estimar p
             

 

  es equivalente a evaluar

-
INTEGRACIÓN NUMÉRICA

función curva(f,n,a,b)
suma ‹
para i ‹ 1 hasta n hacer
x ‹ uniforme(a,b)
suma ‹
devolver (b­a) ·

 suma + f(x)

0

 (suma/n)

función trapecio(f,n,a,b)
    función trapecio(f,n,a,b)

{se supone n>=2}
{se supone n>=2}
delta ‹
  ((bb ­ ­aa)/()/(nn­1)­1)
delta 
suma  ‹
 (f(a) + f(b))/2
suma
 (f(a) + f(b))/2
parapara  xx‹
  aa + 
 + delta
hacer
b ­ delta  hacer
suma + 
f(x)
 + f(x)
suma
 delta
 delta

hasta  b ­ delta
hasta
suma    ‹
suma
 suma ·
devolver suma 
devolver

delta  pasopaso  delta
delta  

•

 

‹
‹
‹
‹
·
CONTEO PROBABILISTA

• Algoritmos probabilistas para estimar un valor 
entero.    Ej:  Calcular  la  cardinalidad  de  un 
conjunto X finito.

• Sea  X  un  conjunto  de  n  elementos  en  el  cual 
muestreamos con repetición de manera uniforme 
e  independiente.  La  esperanza  matemática  del 
la  primera 
numero  de  muestras  antes  de 
repetición, cuando n es grande  tiende a k= b
n 
siendo b =

1,253.

p

/2 »

 

CONTEO PROBABILISTA

•Función contar( X: conjunto)

 0
0
 uniforme(X)

k‹
S‹
a‹
repetir
k+1
k ‹
S ¨ {a}
S ‹
a ‹
 uniforme(X)
hasta a ˛
 S
devolver 2k2/p

• Tiempo  y  espacio  de  orden  n  ,  si  las  operaciones  sobre  el  conjunto  son 

unitarias. Este espacio puede ser prohibitivo si n es grande.

 

ALGORITMOS PROBABILISTAS

Algoritmos de Sherwood

Todos 
somos 
iguales....

 

ALGORITMOS DE SHERWOOD

• Sherwood:  Dan  siempre  respuesta  y  es  correcta.  Hace  uso  del  azar 
para eliminar la diferencia entre buenos y malos ejemplares que se da 
en  algoritmos  deterministas.  El  caso  peor  depende  del  azar,  no  del 
ejemplar del problema.

• Análisis  en  media  de  un  algoritmo  determinista(A),  si 

la 

 t(x)  (Xn conjunto de ejemplares de tamaño n)

probabilidad de cada entrada es la misma sería:
tp (n) = 1/ #Xn  
si no
tp(n) = 
puede haber un ejemplar x tal que t(x) sea mucho mayor que tp(n)

p(x) t(x)

 

ALGORITMOS DE SHERWOOD 

• Ejemplo Quicksort.

• Podemos crear un algoritmo probabilista  de forma que:  

tB(x)» tpA(n) + s(n) 

para todo ejemplar x, donde tB(x) es la esperanza matemática del 
tiempo requerido por el algoritmo B sobre el ejemplar x y s(n) es 
el  coste  de  uniformizar.  Puede  haber  ejecuciones  en  las  que  el 
tiempo sea peor, pero no depende de la entrada.

tpB(n) = 1/Xn 

tB(x) »

tpA(n) +s(n)

•

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO 

función seleccionar (T[1..n],k)

si no si k> v entonces
vector V[1..n­v]
V ‹

los elementos de T 

mayores que p

devolver seleccionar (V,k­v)

si no

devolver p

 un elemento de T[1..n]

si n es pequeño estonces
ordenar T en orden creciente
devolver T[k]
si no p‹
u ‹
v ‹
si k < =u entonces
vector U[1..u]
U‹

[1..n] T[i] < p}
[1..n] T[i] <= p}

 los elementos de T 

#{ i ˛
#{i ˛

menores que p

devolver seleccionar(U,k)

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO

¿Cuál es el mejor pivote?

•
• El  mejor  pivote  sería  la  mediana.  Si  pudiéramos  obtenerla  con  un 
coste  constante,  tendríamos  un  algoritmo  que  ejecuta  una  llamada 
recursiva y los vectores U y V tendrían como mucho º n/2ß .
 Suponiendo un cálculo mágico de la mediana encuentra el k­ésimo 
menor elemento en un tiempo lineal  tm(n) ˛
O(n) +max{tm(i) / i<= 
n/2}.
¿Pero, como calculamos la mediana?

•

•

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO

• Si  la  mediana  no  la  podemos  obtener  en  un  tiempo  constante, 
podemos  sacrificar  la  eficiencia  en  el  peor  caso  a  cambio  de  una 
buena  eficiencia  en  media  y  escoger  simplemente  p=T[1].  Si 
hacemos  esto  tenemos  un  tiempo  medio  lineal,  pero  un  caso  peor 
cuadrático.

• Puedo  buscar  una  aproximación  a  la  mediana,  mediante 

 
pseudomediana, que divide el vector en subvectores de 5 elementos 
y calcula la mediana exacta de estos subvectores, haciendo luego una 
aproximación  a  la  mediana  del  vector  inicial.  Garantizamos  así  el 
tiempo  lineal,  pero  debemos  gastar  tiempo  en  la  elección  del 
pivote.

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO

permutación de los n elementos. 

• La diferencia entre los casos peor y medio no está en el valor de los 
elementos, sino en su orden. Podemos expresar el tiempo en función 
de n y de una s
tp(n 
pseudomediana
ts(n s ), tiempo empleado por el algoritmo simplificado

•
• Normalmente  tp(n  s )  es  mayor  que  ts(n  s ),  pero  puede  haber  una 

tiempo  empleado  por  el  algoritmo  que  emplea 

la 

permutación desastrosa. 
¿qué  podríamos  hacer  para  que  el  tiempo  no  dependiera  de  la 
permutación?

s ) 

•

•

• Solución: Algoritmo de Sherwood

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO

• Funcion seleccionRB(T[1..n], k)

{calcula el k­esimo menor elemento de T}
{se supone que 1<=k<=n}
i ‹ 1; j‹ n
mientras i<j hacer
m ‹ T[uniforme(i..j)]
particionar(T,i,j,m,u,v)
si k <u entonces j‹
 u­1
si no si k>v entonces i ‹
si no i,j‹
 k
devolver T[i]

v+1

 

ENCONTRAR EL K­ÉSIMO MENOR  ELEMENTO

• La esperanza matemática del tiempo de este algoritmo es 

lineal independientemente del ejemplar.

• Siempre es posible que una ejecución emplee un tiempo 
cuadratico pero la probabilidad de que ocurra es menor
cuanto mayor es n.

• Algoritmo de Sherwood eficiente cualquiera que sea el 

ejemplar considerado.

 

CONTEO PROBABILISTA (BIS)

• Problema:  Determinar  el  número  de  palabras  diferentes 

en una cinta.

• Solución  a)  Ordenar  las  palabras  de  la  cinta,  y  después 
recorrer secuencialmente la cinta para contar las palabras 
distintas. Esto sería del orden de q
 (N lgN )  siendo N el 
número total de palabras de la cinta.

• Solución  b)    Utilizar 

técnicas  de  direccionamiento 
disperso (Hashing),  de esta forma recorreríamos la cinta 
una sola vez, tendríamos en media un orden O(n), pero en 
el caso peor  W

 (Nn).

 

 CONTEO PROBABILISTA (BIS) 

• M cota superior de n.

• ALGORITMO

• U conjunto de secuencias consideradas palabras.

• m parámetro ligeramente superior a log M

h:  U  fi
 {0,1}m  función  Hashing  capaz  de 
transformar  una  cadena  de  U  en  una  cadena 
binaria de longitud m 

 p (y,b) con b ˛
k+1 si ningún bit de y es igual a b

 {0,1} es el i menor / y[i]=b o 

•

•

 

{ inicialización }
cadena de (m +1) bits a cero
y ‹
{recorrido secuencial de la cinta }
para cada palabra x de la cinta hacer
i ‹
p
y[i] ‹
{primera estimación sobre lg n}
devolver p (y,0)

(h(x),1)
 1

ALGORITMOS DE LAS VEGAS
!Los siento!
!Prueba otra 

vez!

El problema de las 8 reinas

 

Algoritmos de Las Vegas

• A veces no dan la respuesta
• Se emplean para resolver problemas para los que no se 

conoce ningún algoritmo determinista eficiente.

• Se  corre  el  riesgo  de  tomar  decisiones  que  impidan 

llegar a la solución.

• Permiten,  a  veces  una  eficiencia  mayor  para  todos  los 
ejemplares. La esperanza matemática del  tiempo  debe 
ser  buena  para  todo  ejemplar  y  la  probabilidad  de  un 
tiempo excesivo despreciable.

• Se puede repetir el algoritmo hasta obtener una solución. 
La probabilidad de éxito es mayor cuanto de más tiempo 
se dispone

 

Algoritmos de Las Vegas

• Algoritmo LV(x,var y,var éxito)  
• éxito : cierto si solución, sino falso
• x : ejemplar a resolver
• y :  solución al ejemplar x

función obstinada(x)

repetir

LV(x,y,exito)

hasta éxito
devolver y  

 

Algoritmos de Las Vegas

• p(x) ­ probabilidad de éxito para la entrada x (> que 0)
• s(x) ­ esperanza matemática del tiempo si éxito
• e(x) ­ esperanza matemática del tiempo si fallo

Esperanza matemática del tiempo requerido por  
obstinado:

t(x)=p(x)s(x) + (1­p(x)) (e(x) + t(x))  
t(x) = s(x) + (1­p(x))