Algoritmos aleatorios | Conjunto 2 (Clasificación y Aplicaciones)

Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto.

Algoritmos aleatorios | Conjunto 1 (Introducción y Análisis)

Clasificación

Los algoritmos aleatorios se clasifican en dos categorías.

Las Vegas: estos algoritmos siempre producen un resultado correcto u óptimo. La complejidad temporal de estos algoritmos se basa en un valor aleatorio y la complejidad temporal se evalúa como valor esperado. Por ejemplo, Randomized QuickSort siempre ordena una array de entrada y la complejidad de tiempo esperada en el peor de los casos de QuickSort es O(nLogn) .

Monte Carlo: Produce un resultado correcto u óptimo con cierta probabilidad. Estos algoritmos tienen un tiempo de ejecución determinista y generalmente es más fácil encontrar la complejidad del tiempo en el peor de los casos. Por ejemplo , esta implementación del algoritmo de Karger produce un corte mínimo con una probabilidad mayor o igual a 1/n ² (n es el número de vértices) y tiene una complejidad de tiempo en el peor de los casos como O(E). Otro ejemplo es el método de Fermet para pruebas de primalidad .

Ejemplo para entender la clasificación:

Consider a binary array where exactly half elements are 0
and half are 1. The task is to find index of any 1.  

Un algoritmo de Las Vegas para esta tarea es seguir eligiendo un elemento aleatorio hasta que encontremos un 1. Un algoritmo de Monte Carlo para lo mismo es seguir eligiendo un elemento aleatorio hasta que encontremos 1 o hayamos probado los tiempos máximos permitidos, digamos k.
El algoritmo de Las Vegas siempre encuentra un índice de 1, pero la complejidad del tiempo se determina como valor esperado. El número esperado de intentos antes del éxito es 2, por lo tanto, la complejidad de tiempo esperada es O(1).
El Algoritmo de Monte Carlo encuentra un 1 con probabilidad [1 – (1/2) ^k ]. La complejidad temporal de Monte Carlo es O(k) que es determinista

Aplicaciones y alcance:

• Considere una herramienta que básicamente clasifica. Deje que la herramienta sea utilizada por muchos usuarios y hay pocos usuarios que siempre usan la herramienta para una array ya ordenada. Si la herramienta utiliza QuickSort simple (no aleatorio), esos pocos usuarios siempre se enfrentarán a la peor situación posible. Por otro lado, si la herramienta usa Randomized QuickSort, entonces no hay ningún usuario que siempre obtenga el peor de los casos. Todo el mundo obtiene el tiempo O(n Log n) esperado.
• Los algoritmos aleatorios tienen grandes aplicaciones en criptografía.
• Equilibrio de carga .
• Aplicaciones de la teoría de números: pruebas de primalidad
• Estructuras de datos: hash, ordenación, búsqueda, estadística de pedidos y geometría computacional.
• Identidades algebraicas: Verificación de identidad polinomial y matricial . Sistemas de prueba interactivos.
• Programación matemática: Algoritmos más rápidos para programación lineal, Redondeo de soluciones de programas lineales a soluciones de programas enteros
• Algoritmos gráficos: árboles de expansión mínimos, caminos más cortos, cortes mínimos .
• Conteo y enumeración: Estructuras combinatorias de conteo permanente de arrays.
• Computación paralela y distribuida: Consenso distribuido para evitar interbloqueos.
• Pruebas probabilísticas de existencia: muestran que un objeto combinatorio surge con una probabilidad distinta de cero entre los objetos extraídos de un espacio de probabilidad adecuado.
• Desaleatorización: primero diseñe un algoritmo aleatorio y luego argumente que se puede desaleatorizar para producir un algoritmo determinista.

Fuentes:
http://theory.stanford.edu/people/pragh/amstalk.pdf
https://en.wikipedia.org/wiki/Randomized_algorithm

Este artículo es una contribución de Ashish Sharma . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.