Algoritmos

Algoritmos probabilistas
v v v

Introducción Clasificación de los algoritmos probabilistas Algoritmos numéricos
– La aguja de Buffon – Integración probabilista

2 9 13
14 16

v

Algoritmos de Monte Carlo
– Verificación de un producto matricial – Comprobación de primalidad

21
23 33

v

Algoritmos de Las Vegas
– Ordenación probabilista – Factorización de enteros

50
61 65J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 1

Algoritmos probabilistas: Introducción
v

Una historia sobre un tesoro, un dragón, un computador, un elfo y un doblón.
– En A o B hay un tesoro de x lingotes de oro pero no sé si está en A o B. – Un dragón visita cada noche el tesoro llevándose y lingotes. – Sé que si permanezco 4 días más en O con micomputador resolveré el misterio. – Un elfo me ofrece un trato: A Me da la solución ahora si le pago el equivalente a la cantidad que se llevaría el dragón en 3 noches. 5 días ¿Qué debo hacer? O ?

5 días

B

5 días

J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 2

Algoritmos probabilistas: Introducción
– Si me quedo 4 días más en O hasta resolver el misterio,podré llegar al tesoro en 9 días, y obtener x-9y lingotes. – Si acepto el trato con el elfo, llego al tesoro en 5 días, encuentro allí x-5y lingotes de los cuales debo pagar 3y al elfo, y obtengo x-8y lingotes. Es mejor aceptar el trato pero… … ¡hay una solución mejor! ¿Cuál?

J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 3

Algoritmos probabilistas:Introducción
– ¡Usar el doblón que me queda en el bolsillo! – Lo lanzo al aire para decidir a qué lugar voy primero (A o B).
u

Si acierto a ir en primer lugar al sitio adecuado, obtengo x-5y lingotes. Si no acierto, voy al otro sitio después y me conformo con x-10y lingotes. El beneficio esperado medio es x-7’5y.

u

J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 4Algoritmos probabilistas: Introducción
v

¿Qué hemos aprendido?
– En algunos algoritmos en los que aparece una decisión, es preferible a veces elegir aleatoriamente antes que perder tiempo calculando qué alternativa es la mejor. – Esto ocurre si el tiempo requerido para determinar la elección óptima es demasiado frente al promedio obtenido tomando la decisión al azar.

vCaracterística fundamental de un algoritmo probabilista:
el mismo algoritmo puede comportarse de distinta forma aplicado a los mismos datos

J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 5

Algoritmos probabilistas: Introducción
v

Más diferencias entre los algoritmos deterministas y probabilistas:
– A un algoritmo determinista nunca se le permite que no termine:hacer una división por 0, entrar en un bucle infinito, etc. – A un algoritmo probabilista se le puede permitir siempre que eso ocurra con una probabiliad muy pequeña para datos cualesquiera. u Si ocurre, se aborta el algoritmo y se repite su ejecución con los mismos datos.

– Si existe más de una solución para unos datos dados, un algoritmo determinista siempre encuentra la misma solución (a no serque se programe para encontrar varias o todas). – Un algoritmo probabilista puede encontrar soluciones diferentes ejecutándose varias veces con los mismos datos.

J. Campos - C.P.S.

Esquemas algorítmicos - Algoritmos probabilistas

Pág. 6

Algoritmos probabilistas: Introducción
v

Más diferencias:
– A un algoritmo determinista no se le permite que calcule una solución incorrecta paraningún dato. – Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada. u Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta.

– El análisis de la eficiencia de un algoritmo determinista es, a veces, difícil. –...