Algoritmos probabilísticos:

 

Pueden comportarse(resultado y tiempo) diferente en varias llamadas para una misma instancia.
Puede ciclarse, división entre cero, etc. porque nada mas se reinicia esperando que ahora salga bien. Puede tener varias respuestas correctas.

Mayor ventaja de darle un toque aleatorio a un determinístico con buen average a pesar de su mal worst case es: hacerlo menos vulnerable a una distribución de probabilidad inesperada de las instancias
que debe resolver.

Monte Carlo:

Dan respuesta que puede ser acertada con una probabilidad alta o puede ser errónea. No se puede saber si la respuesta es correcta, pero se puede disminuir la probabilidad de error arbitrariamente dándole más tiempo. No puede haber una instancia para la cual la probabilidad de error sea alta.

Se puede verificar que la respuesta sea correcta, y si es incorrecta decir que lo es.

 

Las Vegas:

Su respuesta siempre es correcta, se sigue llamando el algoritmo hasta que de respuesta correcta.
Pueden ser más eficientes que los deterministas en tiempo esperado. A veces puede tomar tiempo excesivo si tenemos mala suerte. Por ejemplo encontrar la mediana. 

 

Tiempo:

El tiempo esperado se determina para cada instancia: el tiempo medio que toma resolver la misma instancia una y otra vez.
Peor caso: el caso que toma la peor instancia posible de un tamaño dado.  Las Vegas 

 

Generación pseudo aleatoria:

Buffon aguja:

Siglo 18, Georges Louis Leclerc, probabilidad de tirar una aguja (que mide la mitad del ancho de las tablas) y que quede sobre las rayas de unión es de 1/pi. Para n agujas n/pi.
Para obtener un decimal más de precisión se debe de tener un n 100 veces más grande. 

Dos parámetros:
-La confianza p y la precisión E. El algoritmo cuenta k , la cantidad de agujas que cayeron en las rayas y dice el intervalo de pi. 

Integración numérica:

Área bajo la curva de una función. Un I que es la integral de b a a de la función es el área bajo la curva. Rectángulo de ancho b-a y altura I/(b-a)

Cuenta probabilística: 

En un registro binario de n bits, se puede contar hasta 2^n-1 con número entero seguidos, pero más si se saltan valores intermedios. 

 

Monte Carlo: 

Dado un p entre 0 y 1. Un algoritmo es p-correcto si su probabilidad es de al menos p, para cualquier instancia (a veces puede depender del tamaño de la instancia pero no de ella en sí).

Se puede reducir la probabilidad de error sacrificando un poco de tiempo de ejecución (amplificar la ventaja estocástica).

 

Verificar la multiplicación de matrices:

Se dice que A*B = C. Normalmente sería n^3, o n^2.37 con Strassen. Se puede hacer en n^2 con un E, como máxima probabilidad de error. 

Freivalds. 

 

Amplificación de la ventaja estocástica:

Los algoritmos vistos son sesgados, al menos una respuesta obtenida es correcta.  Gracias a esto podemos reducir la probabilidad de error arbitrariamente repitiendo el algoritmo
varias veces.

 

Las Vegas:

Nunca retornan una respuesta incorrecta. 

1. Usan aleatoriedad para guiarse a la respuesta correcta, aunque ocurran situaciones unfortunate, aunque si eso pasa toma mas tiempo (eg quicksort, con el random pueden eliminar la diferencia entre buenas y malas instancias, nos salvan de los casos catastróficos que crean los determinísticos.). Las que en determinístico duraban mucho ya no duran tanto, pero las rápidas se vuelven más lentas. Hacen efecto Robin Hood, roban tiempo de las rápidas para hacer mejor las más lentas. 

2. Pueden tener turnos erróneos, que los llevan a puntos muertos, que no logran encontrar solución en ese turno. Se dan cuenta y admiten que fallaron. Ocurren con muy poca probabilidad, por lo que se puede llamar de nuevo el algoritmo para que esta vez lo haga bien. Tiene que tener un buen tiempo para cada instancia. Cuando puede fallar se debe representar como procedimiento NO como función. Se repite hasta que haya éxito. 

 

-8 reinas:

Es greedy probabilístico, pone reinas en posiciones aleatorias hasta encontrar solución.

-Selección y ordenamiento: