software de sistemas

Un algoritmo probabilístico al azar o algoritmo es un algoritmo que emplea a un grado de aletoriedad, como parte de su lógica. El algoritmo utiliza normalmente al azar de manera uniforme bits como una entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen desempeño en el promedio de casos "sobre todas las opciones posibles de bits aleatorios.Formalmente, el algoritmo de rendimiento va a ser una variable aleatoria determinada por los bits aleatorios, por lo tanto el tiempo de ejecución, o la salida (o ambos) son variables aleatorias.

En ambos casos, el rendimiento y la producción aleatoria al azar, el término "algoritmo" para un procedimiento es un tanto cuestionable, ya que ya no es formalmente efectiva . Sin embargo, en algunos casos, los algoritmos probabilísticos son el único medio práctico de resolver un problema .

En la práctica común, los algoritmos aleatorios son una aproximación con un generador de números pseudo-aleatorios en lugar de una verdadera fuente de bits aleatorios, este tipo de implementación puede desviarse del comportamiento teórico esperado.

Preliminares

B´asicamente los algoritmos aleatorios tienen las siguientes propiedades:

Toman decisiones aleatorias.

Tienden a comportarse siempre como en el caso promedio, o dicho de otro modo, su

comportamiento es “independiente” de la entrada.

Los algoritmos aleatorios son especialmente ´utiles cuando el problema a resolver tiene

varias soluciones, calcular en forma determin´ıstica una soluci´on es dif´ıcil, pero verificar la

soluci´on es f´acil. Tambi´en son ´utiles para protegerse de los casos duros de un problema, por

ejemplo, antes de ordenar con QuickSort, podemos tomar la secuencia, desordenarla al azar

y luego ordenar la secuencia desordenada, con esto en promedio evitamos el peor caso de

O(n

2

).