Importancia de los algoritmos aleatorios

Introducción:

• La aleatorización es un concepto importante y, por lo tanto, los algoritmos de aleatorización se utilizan en una variedad de campos, como la teoría de números , la geometría computacional , la teoría de grafos y la computación distribuida.
• Las entradas para un algoritmo aleatorio son similares a las de los algoritmos deterministas, junto con una secuencia de bits aleatorios que el algoritmo puede usar para tomar decisiones aleatorias.
• En otras palabras, un algoritmo aleatorio es aquel cuyo comportamiento depende de las entradas, similar a un algoritmo determinista, y las elecciones aleatorias se realizan como parte de su lógica.
• Como resultado, el algoritmo da diferentes salidas incluso para la misma entrada.
• En otras palabras, el algoritmo exhibe aleatoriedad; por lo tanto, su tiempo de ejecución a menudo se explica en términos de una variable aleatoria.

ventajas:

• Los algoritmos aleatorios son conocidos por su simplicidad.
• Cualquier algoritmo determinista se puede convertir fácilmente en un algoritmo aleatorio. Estos algoritmos son muy simples de entender e implementar.
• Los algoritmos aleatorios son muy eficientes.
• Utilizan poco tiempo y espacio de ejecución en comparación con cualquier algoritmo determinista.
• Los algoritmos aleatorios exhiben límites asintóticos superiores en comparación con los algoritmos deterministas.
• En otras palabras, la complejidad del algoritmo de los algoritmos aleatorios es mejor que la de la mayoría de los algoritmos deterministas.
• La confiabilidad es un tema importante en muchas aplicaciones críticas, ya que no todos los algoritmos aleatorios siempre dan respuestas correctas.
• Además, es posible que muchos algoritmos aleatorios no terminen.
• Por lo tanto, la confiabilidad es una preocupación importante que debe abordarse.
• La calidad de los algoritmos aleatorios depende de la calidad del generador de números aleatorios utilizado como parte del algoritmo.
• A diferencia de otros paradigmas de diseño, un algoritmo aleatorio no utiliza un solo principio de diseño.
• En cambio, uno debería ver los algoritmos aleatorios como aquellos diseñados usando un conjunto de principios.
• En cambio, uno debería ver los algoritmos aleatorios como aquellos diseñados usando un conjunto de principios.

Algunos principios de diseño se enumeran en las siguientes subsecciones:

Concepto de Testigo :

• Este principio implica la cuestión de verificar si una entrada dada posee una propiedad X o no.
• Se establece al encontrar un objeto determinado llamado testigo o certificado.
• El testigo se identifica para probar el hecho de que la entrada tiene la propiedad deseada X.
• Al realizar menos pruebas, se puede averiguar si la propiedad estaba realmente presente.
• La presencia de un testigo es prueba fuerte de la propiedad X basada en la ausencia de testigos. Este principio se ilustra con el ejemplo de la prueba de primalidad.

Huellas dactilares :

• Por definición, una huella digital es un mensaje más corto que representa un objeto más grande.
• La toma de huellas dactilares es una técnica en la que uno hace una comparación de dos objetos grandes, A y B, solo comparando sus respectivas huellas dactilares cortas.
• Si dos huellas digitales no coinciden, entonces los objetos A y B son diferentes.
• Sin embargo, si las huellas dactilares coinciden, existe una fuerte evidencia circunstancial de que ambos objetos son iguales.

Comprobación de identidades :

• Supongamos que se da una expresión algebraica y el problema es verificar si la expresión se evalúa como cero o no.
• El principio de verificar identidades es conectar las variables aleatorias de una ecuación algebraica dada y verificar si la expresión se evalúa como cero.
• Si no es cero, entonces la expresión dada no es una identidad.
• De lo contrario, existe una fuerte evidencia circunstancial de que la expresión es idénticamente cero.

Muestreo y orden aleatorio :

• El rendimiento de un algoritmo a veces mejora al aleatorizar la distribución o el orden de entrada.
• Se puede observar que para cierto ordenamiento de la entrada, el rendimiento del algoritmo puede ser mayor o apenas aceptable.
• Aquí, la aleatorización conduce a la ordenación, partición y muestreo aleatorios.
• Además, los algoritmos aleatorios recopilan información sobre las distribuciones de entrada utilizando muestras aleatorias. Esto se ilustra a través del problema de contratación.

Frustrando al adversario :

• Un algoritmo aleatorio puede verse como un juego entre una persona y un adversario, es decir, una persona que propone un algoritmo y un adversario que intenta frustrar el algoritmo mediante el diseño de entradas adecuadas para que el algoritmo tome más tiempo.
• En otras palabras, un algoritmo aleatorio puede verse como una selección de un algoritmo de un gran conjunto de algoritmos deterministas, y esta selección puede considerarse un escenario en el que las cosas se dificultan al proporcionar una entrada aleatoria, lo que dificulta aún más la tarea.