stringtranslate.com

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 aleatorios uniformes como entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen rendimiento en el "caso promedio" sobre todas las posibles opciones aleatorias determinadas por los bits aleatorios; por lo tanto, el tiempo de ejecución o la salida (o ambos) son variables aleatorias.

Existe una distinción entre algoritmos que utilizan la entrada aleatoria de modo que siempre terminan con la respuesta correcta, pero donde el tiempo de ejecución esperado es finito ( algoritmos de Las Vegas , por ejemplo Quicksort [1] ), y algoritmos que tienen una probabilidad de producir un resultado incorrecto ( algoritmos de Monte Carlo , por ejemplo el algoritmo de Monte Carlo para el problema MFAS [2] ) o no producen un resultado ya sea señalando un fallo o no terminando. En algunos casos, los algoritmos probabilísticos son el único medio práctico para resolver un problema. [3]

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 n elementos.

Entrada : Una matriz de n ≥2 elementos, en la 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 ) begin repeat Selecciona aleatoriamente un elemento de n elementos hasta que se encuentre ' a' end               

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

Dado que es constante, el tiempo de ejecución esperado a lo largo de muchas llamadas es . (Ver notación Big Theta )

Algoritmo de Monte Carlo:

findingA_MC ( array A , n , k ) begin i := 0 repeat Selecciona aleatoriamente un elemento de n elementos . i : = i + 1 hasta que se encuentre i = k o 'a' end                            

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 siempre es menor o igual a k. Si se toma k como constante, el tiempo de ejecución (esperado y absoluto) es .

Los algoritmos aleatorios son particularmente útiles cuando nos enfrentamos a un "adversario" o atacante malicioso que intenta deliberadamente introducir una entrada incorrecta en el algoritmo (véase complejidad del peor caso y análisis competitivo (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 las 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 . Otra área en la 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 de Monte Carlo (relacionado con el método de Monte Carlo para simulación) se completará en un tiempo que puede estar limitado por una función del tamaño de entrada y su parámetro k , pero permite una 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 ), al hacer que genere una respuesta arbitraria, posiblemente incorrecta, si no se completa dentro de un tiempo especificado. Por el contrario, si existe un procedimiento de verificación eficiente para verificar si una respuesta es correcta, entonces un algoritmo de Monte Carlo se puede convertir en un algoritmo de Las Vegas al ejecutar 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 de Turing probabilísticas . Se consideran tanto los algoritmos de Las Vegas como los de 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 que existe un algoritmo aleatorio eficiente (de tiempo polinomial) (o máquina de Turing probabilística) que reconoce instancias NO con absoluta certeza y reconoce instancias SÍ con una probabilidad de al menos 1/2. La clase complementaria para RP es co-RP. Las clases de problemas que tienen algoritmos (posiblemente no terminantes) con tiempo de ejecución de caso promedio de tiempo polinomial cuya salida siempre es correcta se dice que están en ZPP .

La clase de problemas en los que se permite identificar con algún error tanto las instancias SÍ como las NO se denomina 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 posteriormente publicado en 1961. [4] Ese mismo año, Hoare publicó el algoritmo quickselect , [5] que encuentra el elemento mediano de una lista en tiempo lineal esperado. Hasta 1973 no se sabía si existía un algoritmo determinista de tiempo lineal. [6]

Teoría de números

En 1917, Henry Cabourn Pocklington introdujo un algoritmo aleatorio conocido como algoritmo de Pocklington para hallar de manera eficiente raíces cuadradas módulo números primos. [7] En 1970, Elwyn Berlekamp introdujo un algoritmo aleatorio para calcular de manera eficiente las raíces de un polinomio sobre un cuerpo finito. [8] 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 en tiempo polinomial. En ese momento, no se conocían algoritmos deterministas en tiempo polinomial demostrable para 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 . [9] La tabla hash de Luhn utilizó el encadenamiento para resolver colisiones y también fue una de las primeras aplicaciones de listas enlazadas . [9] Posteriormente, en 1954, Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester y Arthur Samuel de IBM Research introdujeron el sondeo lineal , [9] aunque Andrey Ershov tuvo la misma idea de forma independiente en 1957. [9] En 1962, Donald Knuth realizó el primer análisis correcto del sondeo lineal, [9] aunque el memorando que contenía su análisis no se publicó hasta mucho después. [10] El primer análisis publicado se debió a Konheim y Weiss en 1966. [11]

Los primeros trabajos sobre tablas hash asumían el acceso a una función hash completamente aleatoria o asumían que las claves mismas eran aleatorias. [9] En 1979, Carter y Wegman introdujeron funciones hash universales , [12] 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 aleatorizadas también se extendieron más allá de las tablas hash. En 1970, Burton Howard Bloom introdujo una estructura de datos de pertenencia aproximada conocida como filtro Bloom . [13] En 1989, Raimund Seidel y Cecilia R. Aragon introdujeron un árbol de búsqueda aleatorio equilibrado conocido como treap . [14] En el mismo año, William Pugh introdujo otro árbol de búsqueda aleatorio conocido como lista de omisión . [15]

Usos implícitos en combinatoria

Antes de la popularización de los algoritmos aleatorios en la informática, Paul Erdős popularizó el uso de construcciones aleatorias como una técnica matemática para establecer la existencia de objetos matemáticos. Esta técnica se ha conocido como el método probabilístico . [16] 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 grafos de Ramsey. [17] Utilizó un algoritmo aleatorio mucho más sofisticado en 1959 para establecer la existencia de grafos con circunferencia y número cromático altos. [18] [16]

Ejemplos

Ordenación rápida

Quicksort es un algoritmo conocido y de uso común en el que la aleatoriedad puede ser útil. Muchas versiones deterministas de este algoritmo requieren un tiempo O ( n 2 ) para ordenar n números para alguna clase bien definida 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 pivotes. Sin embargo, si el algoritmo selecciona elementos pivotes 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 una envoltura convexa o una 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 se puede limitar desde arriba. Esta técnica se conoce como construcción incremental aleatoria. [19]

Corte mínimo

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

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

Recordemos que la contracción de dos nodos, u y v , en un (multi-)grafo produce un nuevo nodo u ' con aristas que son la unión de las aristas incidentes en u o v , excepto de cualquier arista que conecte u y v . La figura 1 da un ejemplo de contracción de los vértices A y B . Después de la contracción, el grafo resultante puede tener aristas paralelas, pero no contiene bucles propios.

Figura 2: Ejecución exitosa del algoritmo de Karger en un gráfico de 10 vértices. El corte mínimo tiene un tamaño de 3 y se indica mediante los colores de los vértices.
Figura 1: Contracción del vértice A y B

Algoritmo básico de Karger [20] :

comenzar yo = 1 repetir  repetir Tome un borde aleatorio (u,v) ∈ E en G Reemplace u y v con la contracción u' hasta que solo queden 2 nodos obtener el resultado de corte correspondiente C i yo = yo + 1 hasta que i = m salida del corte mínimo entre C 1 , C 2 , ..., C m . fin

En cada ejecución del bucle externo, el algoritmo repite el bucle interno hasta que solo quedan 2 nodos y se obtiene el corte correspondiente. El tiempo de ejecución de una ejecución es , y n denota el número de vértices. Después de m ejecuciones del bucle externo, obtenemos el corte mínimo entre todos los resultados. La figura 2 muestra un ejemplo de una ejecución del algoritmo. Después de la ejecución, obtenemos un corte de tamaño 3.

Lema 1  —  Sea k el tamaño de corte mínimo y sea C = { e 1 , e 2 , ..., e k } el corte mínimo. Si, durante la iteración i , no se selecciona ninguna arista eC para la contracción, entonces C i = C .

Prueba

Si G no está conexo, entonces G puede dividirse en L y R sin ninguna arista entre ellos. Por lo tanto, el corte mínimo en un grafo desconectado es 0. Ahora, supongamos que G está conexo. Sea V = LR la partición de V inducida por C  : C = { { u , v } ∈ E  : uL , vR } (bien definido ya que G está conexo). Consideremos una arista { u , v } de C . Inicialmente, u , v son vértices distintos. Mientras escojamos una arista ⁠ ⁠ , u y v no se fusionan. Por lo tanto, al final del algoritmo, tenemos dos nodos compuestos que cubren todo el grafo, uno que consiste en los vértices de L y el otro que consiste en los vértices de R . Como en la figura 2, el tamaño del corte mínimo es 1 y C = {( A , B )}. Si no seleccionamos ( A , B ) para la contracción, podemos obtener el corte mínimo.

Lema 2  —  Si G es un multigrafo con p vértices y cuyo corte mínimo tiene tamaño k , entonces G tiene al menos pk /2 aristas.

Prueba

Como el corte mínimo es k , cada vértice v debe satisfacer el grado ( v ) ≥ k . Por lo tanto, la suma de los grados es al menos pk . Pero es bien sabido que la suma de los grados de los vértices es igual a 2| E |. El lema es el siguiente.

Análisis del algoritmo

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

Por el lema 1, la probabilidad de que C i = C es la probabilidad de que no se seleccione ninguna arista de C durante la iteración i . Considere el bucle interno y sea G j el grafo después de j contracciones de aristas, donde j ∈ {0, 1, …, n − 3} . G j tiene nj vértices. Usamos la regla de la cadena de posibilidades condicionales . La probabilidad de que la arista elegida en la iteración j no esté en C , dado que no se ha elegido ninguna arista de C antes, es . Nótese que G j todavía tiene min corte de tamaño k , por lo que por el Lema 2, todavía tiene al menos aristas.

De este modo, .

Entonces, por la regla de la cadena, la probabilidad de encontrar el corte mínimo C es

La cancelación da . Por lo tanto, la probabilidad de que el algoritmo tenga éxito es al menos . Para , esto es equivalente a . El algoritmo encuentra el corte mínimo con probabilidad , en el tiempo .

Desaleatorización

La aleatoriedad puede considerarse un recurso, como el espacio y el tiempo. La desaleatoriedad es entonces el proceso de eliminar la aleatoriedad (o utilizar la menor cantidad posible de ella). Actualmente no se sabe [ ¿hasta ahora? ] si todos los algoritmos pueden desaleatorizarse 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 polinomial 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 pueden emplearse para desaleatorizar algoritmos aleatorios particulares:

Donde la aleatoriedad ayuda

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

Véase también

Notas

  1. ^ Hoare, CAR (julio de 1961). "Algoritmo 64: Quicksort". Commun. ACM . 4 (7): 321–. doi :10.1145/366622.366644. ISSN  0001-0782.
  2. ^ Kudelić, Robert (1 de abril de 2016). "Algoritmo aleatorio de Montecarlo para el problema de arcos de retroalimentación mínima". Applied Soft Computing . 41 : 235–246. doi :10.1016/j.asoc.2015.12.018.
  3. ^ "Al probar la primalidad de números muy grandes elegidos al azar, la probabilidad de tropezar con un valor que engañe a la prueba de Fermat es menor que la probabilidad de que la radiación cósmica haga que la computadora cometa un error al ejecutar un algoritmo 'correcto'. Considerar que un algoritmo es inadecuado por la primera razón pero no por la segunda ilustra la diferencia entre las matemáticas y la ingeniería". Hal Abelson y Gerald J. Sussman (1996). Estructura e interpretación de programas informáticos . MIT Press , sección 1.2.
  4. ^ Hoare, CAR (julio de 1961). "Algoritmo 64: Quicksort". Comunicaciones de la ACM . 4 (7): 321. doi :10.1145/366622.366644. ISSN  0001-0782.
  5. ^ Hoare, CAR (julio de 1961). "Algoritmo 65: hallazgo". Comunicaciones de la ACM . 4 (7): 321–322. doi :10.1145/366622.366647. ISSN  0001-0782.
  6. ^ Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (agosto de 1973). "Límites de tiempo para la selección". Revista de Ciencias de la Computación y de Sistemas . 7 (4): 448–461. doi :10.1016/S0022-0000(73)80033-9.
  7. ^ Williams, HC ; Shallit, JO (1994), "Factorización de números enteros antes de las computadoras", en Gautschi, Walter (ed.), Matemáticas de la computación 1943-1993: medio siglo de matemáticas computacionales; Documentos del Simposio sobre análisis numérico y el Minisimposio sobre teoría computacional de números celebrados en Vancouver, Columbia Británica, del 9 al 13 de agosto de 1993 , Actas de simposios sobre matemáticas aplicadas, vol. 48, Amer. Math. Soc., Providence, RI, págs. 481-531, doi :10.1090/psapm/048/1314885, ISBN 978-0-8218-0291-5, Sr.  1314885; ver pág. 504, "Quizás Pocklington también merece crédito como el inventor del algoritmo aleatorio".
  8. ^ Berlekamp, ​​ER (1971). "Factorización de polinomios sobre grandes cuerpos finitos". Actas del segundo simposio de la ACM sobre manipulación simbólica y algebraica - SYMSAC '71 . Los Ángeles, California, Estados Unidos: ACM Press. p. 223. doi :10.1145/800204.806290. ISBN 9781450377867.S2CID6464612  .​
  9. ^ abcdef Knuth, Donald E. (1998). El arte de la programación informática, volumen 3: (2.ª ed.) Ordenación y búsqueda. Estados Unidos: Addison Wesley Longman Publishing Co., Inc., págs. 536–549. ISBN 978-0-201-89685-5.
  10. ^ Knuth, Donald (1963), Notas sobre el direccionamiento "abierto" , archivado desde el original el 3 de marzo de 2016
  11. ^ Konheim, Alan G.; Weiss, Benjamin (noviembre de 1966). "Una disciplina de ocupación y aplicaciones". Revista SIAM de Matemáticas Aplicadas . 14 (6): 1266–1274. doi :10.1137/0114101. ISSN  0036-1399.
  12. ^ Carter, J. Lawrence; Wegman, Mark N. (1 de abril de 1979). "Clases universales de funciones hash". Revista de Ciencias de la Computación y de Sistemas . 18 (2): 143–154. doi : 10.1016/0022-0000(79)90044-8 . ISSN  0022-0000.
  13. ^ Bloom, Burton H. (julio de 1970). "Compensaciones espacio/tiempo en la codificación hash con errores permitidos". Comunicaciones de la ACM . 13 (7): 422–426. doi : 10.1145/362686.362692 . ISSN  0001-0782. S2CID  7931252.
  14. ^ Aragon, CR; Seidel, RG (octubre de 1989). "Árboles de búsqueda aleatorios". 30.º Simposio anual sobre fundamentos de la informática . pp. 540–545. doi :10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1.
  15. ^ Pugh, William (abril de 1989). Mantenimiento concurrente de listas de omisión (PS, PDF) (informe técnico). Departamento de Ciencias de la Computación, Universidad de Maryland. CS-TR-2222.
  16. ^ ab Alon, Noga (2016). El método probabilístico. Joel H. Spencer (cuarta edición). Hoboken, Nueva Jersey. ISBN 978-1-119-06195-3.OCLC 910535517  .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
  17. ^ P. Erdős: Algunas observaciones sobre la teoría de grafos, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR 8,479d; Zentralblatt 32,192.
  18. ^ Erdös, P. (1959). "Teoría de grafos y probabilidad". Revista canadiense de matemáticas . 11 : 34–38. doi : 10.4153/CJM-1959-003-9 . ISSN  0008-414X. S2CID  122784453.
  19. ^ Seidel R. Análisis hacia atrás de algoritmos geométricos aleatorios.
  20. ^ Karger, David R. (1999). "Muestreo aleatorio en problemas de diseño de corte, flujo y red". Matemáticas de la investigación de operaciones . 24 (2): 383–413. CiteSeerX 10.1.1.215.794 . doi :10.1287/moor.24.2.383. 
  21. ^ Alippi, Cesare (2014), Inteligencia para sistemas integrados , Springer, ISBN 978-3-319-05278-6.
  22. ^ Kushilevitz, Eyal; Nisan, Noam (2006), Complejidad de la comunicación , Cambridge University Press, ISBN 9780521029834. Para el límite inferior determinista, véase la pág. 11; para el límite superior aleatorio logarítmico, véanse las págs. 31-32.
  23. ^ Dyer, M.; Frieze, A.; Kannan, R. (1991), "Un algoritmo aleatorio de tiempo polinomial para aproximar el volumen de cuerpos convexos" (PDF) , Journal of the ACM , 38 (1): 1–17, doi :10.1145/102782.102783, S2CID  13268711
  24. ^ Füredi, Z. ; Bárány, I. (1986), "Calcular el volumen es difícil", Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, 28-30 de mayo de 1986) (PDF) , Nueva York, NY: ACM, pp. 442-447, CiteSeerX 10.1.1.726.9448 , doi :10.1145/12130.12176, ISBN  0-89791-193-8, Número de identificación del sujeto  17867291
  25. ^ Shamir, A. (1992), "IP = PSPACE", Revista de la ACM , 39 (4): 869–877, doi : 10.1145/146585.146609 , S2CID  315182
  26. ^ Cook, Matthew ; Soloveichik, David; Winfree, Erik ; Bruck, Jehoshua (2009), "Programabilidad de redes de reacciones químicas", en Condon, Anne ; Harel, David ; Kok, Joost N.; Salomaa, Arto ; Winfree, Erik (eds.), Bioprocesos algorítmicos (PDF) , Natural Computing Series, Springer-Verlag, págs. 543–584, doi :10.1007/978-3-540-88869-7_27, ISBN 978-3-540-88868-0.

Referencias