Algoritmo aleatorio

Algoritmo que emplea un grado de aleatoriedad como parte de su lógica o procedimiento.

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 ^[1] ), 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 ^[2] ) 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. ^[3]

En la práctica común, los algoritmos aleatorios se aproximan utilizando un generador de números pseudoaleatorios en lugar de una fuente verdadera 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 los que la mitad son ' a ' y la otra mitad son ' b '.

Salida : busque una ' a ' en la matriz.

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

Algoritmo de Las Vegas:

encontrandoA_LV ( matriz A , n ) comenzar repetir Seleccione aleatoriamente un elemento entre n elementos .​ hasta que se encuentre 'a '               

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 _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

Como es constante, el tiempo de ejecución esperado para muchas llamadas es . (Ver notación Big Theta ) ${\displaystyle \Theta (1)}$

Algoritmo de Montecarlo:

encontrandoA_MC ( matriz A , n , k ) comenzar i : = 0 repetir Seleccione aleatoriamente un elemento entre n elementos . i := i + 1 hasta que se encuentre i = k o 'a '                            

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:

${\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}$

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

Los algoritmos aleatorios son particularmente útiles cuando se enfrenta a un "adversario" malicioso 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 . 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 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 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 ), 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. ^[4] En el mismo año, Hoare publicó el algoritmo de selección rápida , ^[5] que encuentra el elemento mediano de una lista en el tiempo esperado lineal. Permaneció abierto hasta 1973 si existía un algoritmo determinista de tiempo lineal. ^[6]

Teoría de los 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 . ^[7] En 1970, Elwyn Berlekamp introdujo un algoritmo aleatorio para calcular eficientemente las raíces de un polinomio en un campo finito. ^[8] En 1977, Robert M. Solovay y Volker Strassen descubrieron una prueba de primalidad aleatoria de 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ía ningún algoritmo determinista de tiempo polinomial 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 . ^[9] La tabla hash de Luhn utilizaba 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 independientemente tuvo la misma idea 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 más tarde. ^[10] El primer análisis publicado se debió a Konheim y Weiss en 1966. ^[11]

Los primeros trabajos sobre tablas hash asumieron el acceso a una función hash completamente aleatoria o asumieron que las claves en sí 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 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 . ^[13] En 1989, Raimund Seidel y Cecilia R. Aragon introdujeron un árbol de búsqueda equilibrado aleatorio conocido como treap . ^[14] Ese mismo año, William Pugh introdujo otro árbol de búsqueda aleatoria conocido como lista de omisión . ^[15]

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 . ^[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 gráficos de Ramsey. ^[17] 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. ^{[18] [16]}

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 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 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 O ( n  log  n ) tiempo, 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. ^[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 número mínimo de aristas entre L y R.

Recuerde que la contracción de dos nodos, u y v , en un (multi)gráfico produce un nuevo nodo u ' 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 da 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.

Figura 2: Ejecución exitosa del algoritmo de Karger en un gráfico de 10 vértices. El corte mínimo tiene talla 3 y está indicado por los colores de los vértices.

Figura 1: Contracción de los vértices A y B

Algoritmo básico de Karger ^{[20] :}

comenzar yo = 1 repetir  repetir Tome una arista aleatoria (u,v) ∈ E en G reemplaza 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 genera el corte mínimo entre C 1 , C 2 , ..., C m .fin

En cada ejecución del bucle exterior, el algoritmo repite el bucle interior hasta que solo queden 2 nodos, 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, generamos el corte mínimo entre todos los resultados. La figura 2 ofrece un ejemplo de una ejecución del algoritmo. Después de la ejecución, obtenemos un corte de tamaño 3. ${\displaystyle O(n)}$

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

Prueba

Si G no está conectado, entonces G se puede dividir en L y R sin ningún borde entre ellos. Entonces el corte mínimo en un gráfico desconectado es 0. Ahora, supongamos que G es conexo. Sea V = L ∪ R la partición de V inducida por C  : C = { { u , v } ∈ E  : u ∈ L , v ∈ R } (bien definido ya que G es conexo). Considere una arista { u , v } de C. Inicialmente, u , v son vértices distintos. Mientras elijamos una arista , u y v no se fusionan. ${\displaystyle f\neq e}$Así, al final del algoritmo, tenemos dos nodos compuestos que cubren todo el gráfico, uno formado por los vértices de L y el otro por 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

Debido a que el corte mínimo es k , cada vértice v debe satisfacer el grado ( v ) ≥ k . Por 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 2| mi |. El lema sigue.

Análisis de 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)).}$$

Según el lema 1, la probabilidad de que C _i = C es la probabilidad de que no se seleccione ningún borde de C durante la iteración i . Considere el bucle interno y sea G _j el gráfico después de j contracciones de borde, donde j ∈ {0, 1,…, n − 3} . G _j tiene n − j 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 . Tenga en cuenta que G _j todavía tiene un corte mínimo de tamaño k , por lo que según el Lema 2, todavía tiene al menos aristas. ${\displaystyle 1-{\frac {k}{|E(G_{j})|}}}$ ${\displaystyle {\frac {(n-j)k}{2}}}$

De este modo, . ${\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 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).}$$

La cancelación da . Por 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 . ${\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}$ ${\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}$ ${\displaystyle m={\frac {n(n-1)}{2}}\ln n}$ ${\displaystyle 1-{\frac {1}{n}}}$ ${\displaystyle 1-{\frac {1}{n}}}$ ${\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 conoce ^{[ a partir de? ]} 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 polinomial con una pequeña probabilidad de error y desaleatorizarlo para que se ejecute en tiempo polinomial sin usar aleatoriedad. .

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

• el método de probabilidades condicionales y su generalización, estimadores pesimistas
• teoría de la discrepancia (que se utiliza para desaleatorizar algoritmos geométricos)
• la explotación de la independencia limitada en las variables aleatorias utilizadas por el algoritmo, como la independencia por pares utilizada en el hash universal
• el uso de gráficos expansores (o dispersores en general) para amplificar una cantidad limitada de aleatoriedad inicial (este último enfoque también se conoce como generación de bits pseudoaleatorios a partir de una fuente aleatoria y conduce al tema relacionado de la aleatoriedad)
• cambiar el algoritmo aleatorio para usar una función hash como fuente de aleatoriedad para las tareas del algoritmo y luego desaleatorizar el algoritmo mediante fuerza bruta para todos los parámetros posibles (semillas) de la función hash. Esta técnica se utiliza generalmente para buscar exhaustivamente un espacio muestral y hacer que el algoritmo sea determinista (por ejemplo, algoritmos de gráficos aleatorios).

Donde ayuda la aleatoriedad

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 motivador inicial: dada una cadena exponencialmente larga de 2 ^k caracteres, la mitad de a y la mitad de b, una máquina de acceso aleatorio requiere 2 ^{k −1} búsquedas en el peor de los casos para encontrar el índice de a ; si se permite realizar elecciones aleatorias, se puede resolver este problema en un número polinómico esperado de búsquedas.
• La forma natural de realizar un cálculo numérico en sistemas integrados o sistemas ciberfísicos es proporcionar un resultado que se aproxima al correcto con alta probabilidad (o Computación Probablemente Aproximadamente Correcta (PACC)). El difícil problema asociado con la evaluación de la pérdida por discrepancia entre el cálculo aproximado y el correcto puede abordarse eficazmente recurriendo a la aleatorización ^[21]
• En la complejidad de la comunicación , la igualdad de dos cadenas se puede verificar con cierta confiabilidad utilizando bits de comunicación con un protocolo aleatorio. Cualquier protocolo determinista requiere bits para defenderse de un oponente fuerte. ^[22] ${\displaystyle \log n}$ ${\displaystyle \Theta (n)}$
• El volumen de un cuerpo convexo se puede estimar mediante un algoritmo aleatorio con precisión arbitraria en tiempo polinómico. ^[23] Bárány y Füredi demostraron que ningún algoritmo determinista puede hacer lo mismo. ^[24] Esto es cierto incondicionalmente, es decir, sin depender de ningún supuesto de teoría de la complejidad, asumiendo que el cuerpo convexo sólo puede consultarse como una caja negra.
• Un ejemplo más teórico de la complejidad de un lugar donde la aleatoriedad parece ayudar es la clase IP . IP consta de todos los lenguajes que pueden ser aceptados (con alta probabilidad) mediante una interacción polinómicamente larga entre un probador todopoderoso y un verificador que implementa un algoritmo BPP. IP = ESPACIO . ^[25] Sin embargo, si se requiere que el verificador sea determinista, entonces IP = NP .
• En una red de reacciones químicas (un conjunto finito de reacciones como A+B → 2C + D que operan en un número finito de moléculas), la capacidad de alcanzar un estado objetivo determinado desde un estado inicial es decidible, aunque incluso se aproxima a la probabilidad de alcanzar un estado objetivo determinado (utilizando la probabilidad estándar basada en la concentración para determinar cuál será la siguiente reacción) es indecidible. Más específicamente, se puede simular una máquina de Turing limitada con una probabilidad arbitrariamente alta de funcionar correctamente en todo momento, sólo si se utiliza una red de reacción química aleatoria. Con una red de reacción química simple no determinista (cualquier reacción posible puede ocurrir a continuación), el poder computacional se limita a funciones recursivas primitivas . ^[26]

Ver también

• Análisis probabilístico de algoritmos.
• Algoritmo de ciudad atlántica
• Algoritmo de Montecarlo
• Algoritmo de Las Vegas
• bogosort
• Principio de decisión diferida
• Algoritmos aleatorios como juegos de suma cero
• Hoja de ruta probabilística
• HyperLogLog
• boceto de conteo mínimo
• algoritmo de conteo aproximado
• algoritmo de karger

Notas

1. Hoare, CAR (julio de 1961). "Algoritmo 64: clasificación rápida". Comunitario. ACM . 4 (7): 321–. doi :10.1145/366622.366644. ISSN  0001-0782.
2. Kudelić, Robert (1 de abril de 2016). "Algoritmo aleatorio de Monte-Carlo para un problema de conjunto de arco de retroalimentación mínima". Computación blanda aplicada . 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 posibilidad de tropezar con un valor que engañe la prueba de Fermat es menor que la posibilidad 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 matemáticas e 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: clasificación rápida". Comunicaciones de la ACM . 4 (7): 321. doi : 10.1145/366622.366644. ISSN  0001-0782.
5. Hoare, CAR (julio de 1961). "Algoritmo 65: buscar". 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). "Plazos 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), "Factoring integers before computer", en Gautschi, Walter (ed.), Mathematics of Computation 1943–1993: medio siglo de matemáticas computacionales; Artículos del Simposio sobre análisis numérico y el minisimposio sobre teoría computacional de números celebrado en Vancouver, Columbia Británica, del 9 al 13 de agosto de 1993 , Actas de simposios en matemáticas aplicadas, vol. 48, americano. Matemáticas. Soc., Providence, RI, págs. 481–531, doi :10.1090/psapm/048/1314885, ISBN 978-0-8218-0291-5, señor  1314885; ver pág. 504, "Quizás Pocklington también merezca crédito como inventor del algoritmo aleatorio".
8. Berlekamp, ​​ER (1971). "Factorizar polinomios en grandes campos finitos". Actas del segundo simposio de ACM sobre manipulación simbólica y algebraica - SYMSAC '71 . Los Ángeles, California, Estados Unidos: ACM Press. pag. 223. doi : 10.1145/800204.806290. ISBN 9781450377867. S2CID  6464612.
9. Knuth, Donald E. (1998). El arte de la programación informática, volumen 3: (2ª ed.) clasificació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ática Aplicada . 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 de espacio/tiempo en 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. Aragón, CR; Seidel, RG (octubre de 1989). "Árboles de búsqueda aleatoria". 30º Simposio Anual sobre Fundamentos de la Informática . págs. 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) (Reporte técnico). Departamento de Ciencias de la Computación, U. Maryland. CS-TR-2222.
16. Alon, Noga (2016). El método probabilístico. Joel H. Spencer (Cuarta ed.). Hoboken, Nueva Jersey. ISBN 978-1-119-06195-3. OCLC  910535517.{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )
17. P. Erdős: Algunas observaciones sobre la teoría de grafos, Bull. América. Matemáticas. 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 red, flujo y corte". 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 conocer el límite inferior determinista, consulte la pág. 11; para el límite superior aleatorio logarítmico, consulte las páginas 31 y 32.
23. Tintorero, M.; Friso, A.; Kannan, R. (1991), "Un algoritmo aleatorio de tiempo polinómico 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. 18º Simposio ACM sobre Teoría de la Computación (Berkeley, California, 28 al 30 de mayo de 1986) (PDF) , Nueva York, NY: ACM, págs. 442–447, CiteSeerX 10.1.1.726.9448 , doi :10.1145/12130.12176, ISBN  0-89791-193-8, S2CID  17867291
25. Shamir, A. (1992), "IP = PSPACE", Revista de la ACM , 39 (4): 869–877, doi : 10.1145/146585.146609 , S2CID  315182
26. Cocinero, Mateo ; 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

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 1990. ISBN 0-262-03293-7 . Capítulo 5: Análisis probabilístico y algoritmos aleatorios, págs. 91-122. 
• Dirk Draheim. "Semántica del cálculo Lambda tipificado probabilístico (semántica de cadena de Markov, comportamiento de terminación y semántica denotacional)". Saltador, 2017.
• Jon Kleinberg y Éva Tardos . Diseño de algoritmos . Capítulo 13: "Algoritmos aleatorios".
• Fallis, D. (2000). "La fiabilidad de los algoritmos aleatorios". La Revista Británica de Filosofía de la Ciencia . 51 (2): 255–271. doi :10.1093/bjps/51.2.255.
• M. Mitzenmacher y E. Upfal . Probabilidad y Computación: Algoritmos Aleatorios y Análisis Probabilístico . Cambridge University Press, Nueva York (NY), 2005.
• Rajeev Motwani y P. Raghavan. Algoritmos aleatorios . Cambridge University Press, Nueva York (NY), 1995.
• Rajeev Motwani y P. Raghavan. Algoritmos aleatorios. Una encuesta sobre algoritmos aleatorios.
• Christos Papadimitriou (1993), Complejidad computacional (1ª ed.), Addison Wesley, ISBN 978-0-201-53082-7Capítulo 11: Cálculo aleatorio, págs. 241–278.
• Rabin, Michael O. (1980). "Algoritmo probabilístico para probar la primalidad". Revista de teoría de números . 12 : 128-138. doi : 10.1016/0022-314X(80)90084-0 .
• AA Tsay, WS Lovejoy, David R. Karger, Muestreo aleatorio en problemas de diseño de red, flujo y corte , Matemáticas de la investigación de operaciones, 24(2):383–413, 1999.
• "Algoritmos aleatorios para informática científica" (RASC), OSTI.GOV (10 de julio de 2021).