Algoritmo aleatorio

Un algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento. El algoritmo normalmente utiliza bits uniformemente aleatorios como entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen rendimiento en el "caso promedio" sobre todas las posibles elecciones aleatorias determinadas por los bits aleatorios; por lo tanto, el tiempo de ejecución o la salida (o ambos) son variables aleatorias.

Hay que distinguir entre algoritmos que utilizan la entrada aleatoria para que siempre terminen con la respuesta correcta, pero donde el tiempo de ejecución esperado es finito (algoritmos de Las Vegas, por ejemplo Quicksort), y algoritmos que tienen posibilidades de producir un resultado incorrecto (algoritmos de Monte Carlo, por ejemplo el algoritmo de Monte Carlo para el problema MFAS) o no producir un resultado ya sea al señalar una falla o al no terminar. En algunos casos, los algoritmos probabilísticos son el único medio práctico para resolver un problema.

En la práctica común, los algoritmos aleatorios se aproximan utilizando un generador de números pseudoaleatorios en lugar de una fuente real de bits aleatorios; dicha implementación puede desviarse del comportamiento teórico esperado y de las garantías matemáticas que pueden depender de la existencia de un generador de números aleatorios verdadero ideal.

Motivación

Como ejemplo motivador, considere el problema de encontrar una 'a' en una matriz de elementos n.

Entrada: una matriz de n≥2 elementos, en los que la mitad son 'a y la otra mitad son 'b.

Salida: busque una 'a' en la matriz.

Ofrecemos dos versiones del algoritmo, un algoritmo de Las Vegas y un algoritmo de Monte Carlo.

Algoritmo de Las Vegas:

findingA_LV()array A, n)comenzar repetición Aleatoriamente seleccionar uno elemento Fuera. de n elementos. hasta 'a' es encontradofinal

Este algoritmo tiene éxito con probabilidad 1. El número de iteraciones varía y puede ser arbitrariamente grande, pero el número esperado de iteraciones es

${displaystyle lim _{nto infty }sum - ¿Qué? {}{2}}=2}$

Puesto que es constante, el tiempo de ejecución esperado sobre muchas llamadas es ${displaystyle Theta (1)}$. (Ver Big Theta notation)

Algoritmo de Montecarlo:

findingA_MC()array A, n, k)comenzar i := 0 repetición Aleatoriamente seleccionar uno elemento Fuera. de n elementos. i := i + 1 hasta i = k o 'a' es encontradofinal

Si se encuentra una 'a', el algoritmo tiene éxito; de lo contrario, falla. Después de k iteraciones, la probabilidad de encontrar una 'a' es:

Este algoritmo no garantiza el éxito, pero el tiempo de ejecución está limitado. El número de iteraciones es siempre menor o igual a k. Tomar k para ser constante el tiempo de ejecución (esperado y absoluto) es ${displaystyle Theta (1)}$.

Los algoritmos aleatorios son particularmente útiles cuando nos enfrentamos a un "adversario" o un atacante que intenta deliberadamente introducir una mala entrada en el algoritmo (consulte el análisis competitivo y de complejidad del peor de los casos (algoritmo en línea)), como en el dilema del prisionero. Es por esta razón que la aleatoriedad es omnipresente en la criptografía. En aplicaciones criptográficas, no se pueden utilizar números pseudoaleatorios, ya que el adversario puede predecirlos, lo que hace que el algoritmo sea efectivamente determinista. Por lo tanto, se requiere una fuente de números verdaderamente aleatorios o un generador de números pseudoaleatorios criptográficamente seguro. Otro ámbito en el que la aleatoriedad es inherente es la computación cuántica.

En el ejemplo anterior, el algoritmo de Las Vegas siempre genera la respuesta correcta, pero su tiempo de ejecución es una variable aleatoria. Se garantiza que el algoritmo Monte Carlo (relacionado con el método Monte Carlo para simulación) se completará en un período de tiempo que puede estar limitado por una función del tamaño de entrada y su parámetro k, pero permite un pequeña probabilidad de error. Observe que cualquier algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo (a través de la desigualdad de Markov), haciendo que genere una respuesta arbitraria, posiblemente incorrecta, si no se completa dentro de un tiempo específico. Por el contrario, si existe un procedimiento de verificación eficiente para comprobar si una respuesta es correcta, entonces un algoritmo de Monte Carlo se puede convertir en un algoritmo de Las Vegas ejecutando el algoritmo de Monte Carlo repetidamente hasta que se obtenga una respuesta correcta.

Complejidad computacional

La teoría de la complejidad computacional modela algoritmos aleatorios como máquinas probabilísticas de Turing. Se consideran los algoritmos de Las Vegas y Monte Carlo y se estudian varias clases de complejidad. La clase de complejidad aleatoria más básica es RP, que es la clase de problemas de decisión para los cuales existe un algoritmo aleatorio eficiente (tiempo polinómico) (o máquina probabilística de Turing) que reconoce instancias NO con absoluta certeza y reconoce instancias SÍ con una probabilidad. de al menos 1/2. La clase complementaria de RP es co-RP. Se dice que las clases de problemas que tienen algoritmos (posiblemente no terminantes) con tiempo polinómico promedio de ejecución de casos cuya salida es siempre correcta están en ZPP.

La clase de problemas para los cuales se permite identificar instancias SÍ y NO con algún error se llama BPP. Esta clase actúa como el equivalente aleatorio de P, es decir, BPP representa la clase de algoritmos aleatorios eficientes.

Historia temprana

Clasificación

Quicksort fue descubierto por Tony Hoare en 1959 y publicado posteriormente en 1961. Ese mismo año, Hoare publicó el algoritmo de selección rápida, que encuentra el elemento mediano de una lista en un tiempo lineal esperado. Permaneció abierto hasta 1973 si existía un algoritmo determinista de tiempo lineal.

Teoría de números

En 1917, Henry Cabourn Pocklington introdujo un algoritmo aleatorio conocido como algoritmo de Pocklington para encontrar eficientemente números primos en módulo de raíces cuadradas. En 1970, Elwyn Berlekamp introdujo un algoritmo aleatorio para calcular eficientemente las raíces de un polinomio en un campo finito. En 1977, Robert M. Solovay y Volker Strassen descubrieron una prueba de primalidad aleatoria en tiempo polinomial (es decir, determinar la primalidad de un número). Poco después, Michael O. Rabin demostró que la prueba de primalidad de Miller de 1976 también podía convertirse en un algoritmo aleatorio de tiempo polinomial. En ese momento, no se conocían algoritmos deterministas de tiempo polinómico demostrable para las pruebas de primalidad.

Estructuras de datos

Una de las primeras estructuras de datos aleatorios es la tabla hash, que fue introducida en 1953 por Hans Peter Luhn en IBM. La tabla hash de Luhn utilizaba encadenamiento para resolver colisiones y también fue una de las primeras aplicaciones de listas enlazadas. Posteriormente, en 1954, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester y Arthur Samuel de IBM Research introdujeron el sondeo lineal, aunque Andrey Ershov tuvo la misma idea de forma independiente en 1957. En 1962, Donald Knuth realizó el primer análisis correcto del sondeo lineal., aunque el memorando que contenía su análisis no se publicó hasta mucho más tarde. El primer análisis publicado se debió a Konheim y Weiss en 1966.

Los primeros trabajos sobre tablas hash asumían el acceso a una función hash completamente aleatoria o asumían que las claves en sí eran aleatorias. En 1979, Carter y Wegman introdujeron funciones hash universales, que demostraron que podían usarse para implementar tablas hash encadenadas con un tiempo esperado constante por operación.

Los primeros trabajos sobre estructuras de datos aleatorias también se extendieron más allá de las tablas hash. En 1970, Burton Howard Bloom introdujo una estructura de datos de membresía aproximada conocida como filtro Bloom. En 1989, Raimund Seidel y Cecilia R. Aragon introdujeron un árbol de búsqueda aleatorio y equilibrado conocido como treap. Ese mismo año, William Pugh introdujo otro árbol de búsqueda aleatoria conocido como lista de omisión.

Usos implícitos en combinatoria

Antes de la popularización de los algoritmos aleatorios en informática, Paul Erdős popularizó el uso de construcciones aleatorias como técnica matemática para establecer la existencia de objetos matemáticos. Esta técnica se conoce como método probabilístico. Erdős dio su primera aplicación del método probabilístico en 1947, cuando utilizó una construcción aleatoria simple para establecer la existencia de gráficos de Ramsey. En 1959 utilizó un algoritmo aleatorio mucho más sofisticado para establecer la existencia de gráficos con gran circunferencia y número cromático.

Ejemplos

Ordenación rápida

Quicksort es un algoritmo familiar y de uso común en el que la aleatoriedad puede resultar útil. Muchas versiones deterministas de este algoritmo requieren O(n²) tiempo para ordenar n números para algunos bien definidos. clase de entradas degeneradas (como una matriz ya ordenada), con la clase específica de entradas que generan este comportamiento definida por el protocolo para la selección de pivote. Sin embargo, si el algoritmo selecciona elementos pivote de manera uniforme y aleatoria, tiene una probabilidad demostrablemente alta de terminar en un tiempo O(n log n) independientemente de las características de la entrada.

Construcciones incrementales aleatorias en geometría

En geometría computacional, una técnica estándar para construir una estructura como un casco convexo o triangulación de Delaunay es permutar aleatoriamente los puntos de entrada y luego insertarlos uno por uno en la estructura existente. La aleatorización garantiza que el número esperado de cambios en la estructura causados por una inserción sea pequeño y, por lo tanto, el tiempo de ejecución esperado del algoritmo puede limitarse desde arriba. Esta técnica se conoce como construcción incremental aleatoria.

Corte mínimo

Entrada: Un gráfico G(V,E)

Salida: Un corte que divide los vértices en L y R, con el número mínimo de aristas entre L y R.

Recuerde que la contracción de dos nodos, u y v, en un (multi)grafo produce un nuevo nodo u &# 39; con aristas que son la unión de las aristas incidentes en u o v, excepto desde cualquier arista que conecte u y v. La Figura 1 ofrece un ejemplo de contracción de los vértices A y B. Después de la contracción, el gráfico resultante puede tener bordes paralelos, pero no contiene bucles propios.

Algoritmo básico de Karger:

comenzari = 1
 repetición repeticiónTomar un borde aleatorio (u,v)
reemplazar u y v con la contracción u
 hasta sólo quedan 2 nodos
obtener el resultado de corte correspondiente Cii = i + 1
 hasta i = m
salida del corte mínimo entre C1, C2,..., Cm.
final

En cada ejecución del bucle exterior, el algoritmo repite el bucle interior hasta que sólo quedan 2 nodos, se obtiene el corte correspondiente. El tiempo de ejecución de una ejecución es ${displaystyle O(n)}$, y n denota el número de vértices. Después m tiempos de ejecución del bucle exterior, obtenemos el corte mínimo entre todos los resultados. La figura 2 da una ejemplo de una ejecución del algoritmo. Después de la ejecución, tenemos un corte del tamaño 3.

Análisis del algoritmo

La probabilidad de que el algoritmo tenga éxito es 1 - la probabilidad de que todos los intentos fallen. Por independencia, la probabilidad de que todos los intentos fallen es

$${displaystyle prod _{i=1}{m}Pr(C_{i}neq C)=prod _{i=1} {m}(1-Pr(C_{i}=C)). }$$

Por lema 1, la probabilidad de que C_i = C es la probabilidad de que ningún borde de C se selecciona durante la iteración i. Considerar el bucle interior y dejar G_j denota el gráfico después j Contracciones de borde, donde j ################################################################################################################################################################################################################################################################ n 3 - 3. G_j tiene n − j vertices. Usamos la regla de cadena de posibilidades condicionales. La probabilidad de que el borde elegido en la iteración j no está C, dado que no hay borde C ha sido elegido antes, es ${displaystyle 1-{frac {k}{fn} {fnK}} {fnK}}}} {fn}} {fnK}}}}} {fn}}}}}}}} {fn} {fn}}} {fn}}}}}}} {f}}}}}}}}}}}}}}}}$. Note que G_j todavía tiene min corte de tamaño k, así que por Lemma 2, todavía tiene al menos ${displaystyle {frac {fnh}{2}}$ bordes.

Así, ${displaystyle 1-{frac} {fnMientras) 1-{frac {2}{n-j}={frac} {n-j-2}{n-j}}$.

Entonces, según la regla de la cadena, la probabilidad de encontrar el corte mínimo C es

$${displaystyle Pr[C_{i}=C]geq left({frac {n-2}{n}right)left({frac {n-3}{n-1}right)left({frac {n-4}{n-2}right)ldots left({frac {3}{5}right)left({frac {2}{4}}right)left({frac {1}{3}right).}}}}}}}}}}right).$$

Cancelación da ${displaystyle {fn}}$. Así, la probabilidad de que el algoritmo tenga éxito es al menos ${displaystyle 1-left(1-{frac {2}{n(n-1)}right)^{m}$. Para ${displaystyle m={frac {n-1}{2}ln n}$, esto equivale a ${displaystyle 1-{frac {1}{n}}$. El algoritmo encuentra el corte min con probabilidad ${displaystyle 1-{frac {1}{n}}$, a tiempo ${displaystyle O(mn)=O(n^{3}log n)}$.

Desaleatorización

La aleatoriedad puede verse como un recurso, como el espacio y el tiempo. La desrandomización es entonces el proceso de eliminar la aleatoriedad (o utilizar la menor cantidad posible de ella). Actualmente no se sabe si todos los algoritmos se pueden desaleatorizar sin aumentar significativamente su tiempo de ejecución. Por ejemplo, en complejidad computacional, se desconoce si P = BPP, es decir, no sabemos si podemos tomar un algoritmo aleatorio arbitrario que se ejecuta en tiempo polinómico con una pequeña probabilidad de error y desaleatorizarlo para que se ejecute en tiempo polinomial sin utilizar aleatoriedad..

Existen métodos específicos que se pueden emplear para desaleatorizar algoritmos aleatorios concretos:

• el método de probabilidades condicionales, y su generalización, estimadores pesimistas
• teoría de la discrepancia (que se utiliza para desaranizar algoritmos geométricos)
• la explotación de la independencia limitada en las variables aleatorias utilizadas por el algoritmo, como la independencia de pares utilizada en la piratería universal
• el uso de gráficos de mayor tamaño (o dispersores en general) amplificación una cantidad limitada de aleatoriedad inicial (este último enfoque también se conoce como la generación de bits de seudorandismo de una fuente aleatoria, y conduce al tema relacionado de seudordomía)
• cambiar el algoritmo aleatorizado para usar una función de hash como una fuente de aleatoriedad para las tareas del algoritmo, y luego desaranizar el algoritmo mediante la ejecución de brutes todos los parámetros posibles (semillas) de la función hash. Esta técnica se utiliza generalmente para buscar exhaustivamente un espacio de muestra y hacer el algoritmo determinístico (por ejemplo, algoritmos de gráficos aleatorizados)

Donde la aleatoriedad ayuda

Cuando el modelo de computación se restringe a las máquinas de Turing, actualmente queda abierta la cuestión de si la capacidad de realizar elecciones aleatorias permite resolver algunos problemas en tiempo polinomial que no se pueden resolver en tiempo polinomial sin esta capacidad; ésta es la cuestión de si P = BPP. Sin embargo, en otros contextos, existen ejemplos específicos de problemas en los que la aleatorización produce mejoras estrictas.

• Basado en el ejemplo de motivación inicial: dada una cadena exponencialmente larga de 2^k caracteres, media b y media, una máquina de acceso al azar requiere 2^k−1 búsquedas en el peor de los casos para encontrar el índice de a; si se permite tomar decisiones aleatorias, puede resolver este problema en un número de búsquedas polinomio esperado.
• La forma natural de llevar a cabo una computación numérica en sistemas incrustados o sistemas ciberfísicos es proporcionar un resultado que aproxima al correcto con alta probabilidad (o probablemente computación aproximada (PACC)). El duro problema asociado con la evaluación de la pérdida de discrepancia entre el cálculo aproximado y el cálculo correcto se puede abordar eficazmente recurriendo a la aleatorización
• En la complejidad de la comunicación, la igualdad de dos cadenas se puede verificar a cierta confiabilidad utilizando ${displaystyle log n}$ bits de comunicación con un protocolo aleatorizado. Cualquier protocolo determinista requiere ${displaystyle Theta (n)}$ si defiendes a un fuerte oponente.
• El volumen de un cuerpo convexo puede ser estimado por un algoritmo aleatorizado a la precisión arbitraria en el tiempo polinomio. Bárány y Füredi demostraron que ningún algoritmo determinista puede hacer lo mismo. Esto es verdad incondicionalmente, es decir, sin depender de cualquier presunción teórica de complejidad, asumiendo que el cuerpo convexo puede ser preguntado sólo como una caja negra.
• Un ejemplo más complejo-teorético de un lugar donde el azar parece ayudar es la clase IP. IP consiste en todos los idiomas que pueden ser aceptados (con alta probabilidad) por una interacción polinomialmente larga entre un proverbio todopoderoso y un verificador que implementa un algoritmo BPP. IP = PSPACE. Sin embargo, si se requiere que el verificador sea determinista, entonces IP = NP.
• En una red de reacción química (un conjunto finito de reacciones como A+B → 2C + D operando en un número finito de moléculas), la capacidad de llegar a un determinado estado objetivo de un estado inicial es decidable, mientras que incluso aproximar la probabilidad de alcanzar un determinado estado objetivo (utilizando la probabilidad estándar basada en la concentración para la que la reacción ocurrirá próxima) es indecible. Más específicamente, una máquina de Turing limitada se puede simular con probabilidad arbitrariamente alta de funcionar correctamente durante todo el tiempo, sólo si se utiliza una red de reacción química aleatoria. Con una simple red de reacción química no determinista (cualquier posible reacción puede ocurrir próximamente), el poder computacional se limita a funciones recursivas primitivas.