Hispanopedia Wiki
Articulo de referencia

Algoritmo aleatorio

Un algoritmo aleatorio es aquel que emplea cierto grado de aleatoriedad como parte de su lógica o procedimiento. Generalmente, utiliza bits aleatorios uniformes como entrada aux...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo aleatorio es aquel que emplea cierto grado de aleatoriedad como parte de su lógica o procedimiento. Generalmente, utiliza bits aleatorios uniformes como entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen rendimiento en el "caso promedio" entre todas las posibles combinaciones de valores aleatorios determinadas por dichos bits; por lo tanto, el tiempo de ejecución, el resultado (o ambos) son variables aleatorias.

Existe una distinción entre los 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 los algoritmos que tienen la posibilidad de producir un resultado incorrecto ( algoritmos de Monte Carlo , por ejemplo el algoritmo de Monte Carlo para el problema MFAS [ 2 ] ) o que 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 habitual, 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, consideremos el problema de encontrar una ' a ' en un arreglo de n elementos.

Entrada : Un array de n ≥2 elementos, en el que la mitad son ' a ' y la otra mitad son ' b '.

Salida : Encuentra una ' a ' en el array.

Presentamos 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 Seleccionar aleatoriamente un elemento de entre n elementos . hasta que se encuentre 'a' end

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

límitenorte→∞∑i=1nortei2i=2{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}

Dado que es constante, el tiempo de ejecución esperado en muchas llamadas esΘ(1){\displaystyle \Theta (1)}(Véase la notación Big Theta )

Algoritmo de Monte Carlo:

findingA_MC ( array A , n , k ) begin i := 0 repeat Seleccionar aleatoriamente un elemento de entre n elementos . i := i + 1 hasta que i = k o se encuentre '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:

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

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

Los algoritmos aleatorios son particularmente útiles cuando se enfrenta a un "adversario" o atacante malicioso que intenta deliberadamente introducir una entrada incorrecta en el algoritmo (véase complejidad en el peor de los casos 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 criptografía . En aplicaciones criptográficas, no se pueden usar 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 arroja la respuesta correcta, pero su tiempo de ejecución es una variable aleatoria. El algoritmo de Monte Carlo (relacionado con el método de Monte Carlo para simulación) garantiza su finalización en un tiempo acotado por una función del tamaño de la entrada y su parámetro k , pero permite una pequeña probabilidad de error . Cabe destacar que cualquier algoritmo de Las Vegas puede convertirse en un algoritmo de Monte Carlo (mediante la desigualdad de Markov ), haciendo que arroje 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 comprobar si una respuesta es correcta, un algoritmo de Monte Carlo puede convertirse en un algoritmo de Las Vegas ejecutándolo repetidamente hasta obtener una respuesta correcta.

Complejidad computacional

La teoría de la complejidad computacional modela los 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 de RP es co-RP. Se dice que las clases de problemas que tienen algoritmos (posiblemente no terminantes) con un tiempo de ejecución promedio de caso polinomial cuya salida es siempre correcta están en ZPP .

La clase de problemas en los que se permite identificar con cierto margen de 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

El algoritmo Quicksort fue descubierto por Tony Hoare en 1959 y publicado posteriormente 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. Permaneció abierto hasta 1973 la cuestión de 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 el algoritmo de Pocklington para encontrar eficientemente raíces cuadradas módulo números primos. [ 7 ] En 1970, Elwyn Berlekamp introdujo un algoritmo aleatorio para calcular eficientemente 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 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ían algoritmos deterministas de tiempo polinomial demostrable para pruebas de primalidad.

Estructuras de datos

Una de las primeras estructuras de datos aleatorias es la tabla hash , introducida en 1953 por Hans Peter Luhn en IBM . [ 9 ] La tabla hash de Luhn utilizaba encadenamiento para resolver colisiones y fue también 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 memorándum 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 aleatorias 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 de 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 aleatorio conocido como lista de saltos . [ 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 técnica matemática para establecer la existencia de objetos matemáticos. Esta técnica se conoce como el método probabilístico . [ 16 ] Erdős realizó 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 ] En 1959, utilizó un algoritmo aleatorio más sofisticado para establecer la existencia de grafos con gran circunferencia y número cromático. [ 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 de O ( n² ) para ordenar n números para una clase bien definida de entradas degeneradas (como un arreglo ya ordenado), y la clase específica de entradas que genera este comportamiento está definida por el protocolo de selección de pivote. Sin embargo, si el algoritmo selecciona los elementos pivote de forma uniforme y aleatoria, tiene una probabilidad demostrablemente alta de finalizar en un tiempo de 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 consiste en permutar aleatoriamente los puntos de entrada e insertarlos uno a 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, por lo que el tiempo de ejecución esperado del algoritmo puede acotarse superiormente. Esta técnica se conoce como construcción incremental aleatoria . [ 19 ]

Corte mínimo

Entrada : Un grafo 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.

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 las que conectan u y v . La Figura 1 muestra un ejemplo de contracción de los vértices A y B. Tras la contracción, el grafo resultante puede tener aristas paralelas, pero no contiene bucles.

Figura 2: Ejecución exitosa del algoritmo de Karger en un grafo de 10 vértices. El corte mínimo tiene un tamaño de 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 i = 1 repetir repetir Toma una arista aleatoria (u,v) ∈ E en G Reemplazar u y v con la contracción u' hasta que solo queden 2 nodos obtener el resultado de corte correspondiente C i i = i + 1 hasta que i = m Devuelve el 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, obteniéndose así el corte correspondiente. El tiempo de ejecución de una ejecución esO(norte){\displaystyle O(n)}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. Tras la ejecución, obtenemos un corte de tamaño 3.

Lema 1 — Sea k el tamaño mínimo de corte, y sea C = { e 1 , e 2 , ..., 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 puede particionarse 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á conectado. Sea V = L ∪ R la partición de V inducida por C  : C = { { u , v } ∈ E  : u ∈ L , v ∈ R } (bien definida ya que G está conectado). Consideremos una arista { u , v } de C . Inicialmente, u , v son vértices distintos. Siempre que elijamos una arista ⁠F≠mi{\displaystyle f\neq e}⁠ , u y v no se fusionan.Por lo tanto, al final del algoritmo, tenemos dos nodos compuestos que cubren todo el grafo, uno formado por los vértices deLy el otro formado por los vértices deR.Como en la figura 2, el tamaño del corte mínimo es 1, yC= {(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

Dado que el corte mínimo es k , cada vértice v debe satisfacer degree( 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 se deduce de lo siguiente.

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 ∏i=1metroPr(doi≠do)=∏i=1metro(1−Pr(doi=do)).{\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 ninguna arista de C durante la iteración i . Consideremos 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 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, es1−k|mi(GRAMOj)|{\displaystyle 1-{\frac {k}{|E(G_{j})|}}}. Nótese que G j todavía tiene corte mínimo de tamaño k , por lo que según el Lema 2, todavía tiene al menos(norte−j)k2{\displaystyle {\frac {(nj)k}{2}}}bordes.

De este modo,1−k|mi(GRAMOj)|≥1−2norte−j=norte−j−2norte−j{\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{nj}}={\frac {nj-2}{nj}}}.

Por lo tanto, según la regla de la cadena, la probabilidad de encontrar el corte mínimo C es Pr[doi=do]≥(norte−2norte)(norte−3norte−1)(norte−4norte−2)…(35)(24)(13).{\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 daPr[doi=do]≥2norte(norte−1){\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}Por lo tanto, la probabilidad de que el algoritmo tenga éxito es al menos1−(1−2norte(norte−1))metro{\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}. Parametro=norte(norte−1)2ln⁡norte{\displaystyle m={\frac {n(n-1)}{2}}\ln n}, esto es equivalente a1−1norte{\displaystyle 1-{\frac {1}{n}}}El algoritmo encuentra el corte mínimo con probabilidad1−1norte{\displaystyle 1-{\frac {1}{n}}}, a tiempoO(metronorte)=O(norte3registro⁡norte){\displaystyle O(mn)=O(n^{3}\log n)}.

Desaleatorización

La aleatoriedad puede considerarse un recurso, como el espacio y el tiempo. La desaleatorización es entonces el proceso de eliminar la aleatoriedad (o usar la menor cantidad posible). [ 21 ] [ 22 ] Actualmente se desconoce si todos los algoritmos pueden desaleatorizarse sin aumentar significativamente su tiempo de ejecución. [ 23 ] Por ejemplo, en complejidad computacional , se desconoce si P = BPP , [ 23 ] 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 pueden emplearse para eliminar la aleatoriedad de determinados algoritmos aleatorios:

Donde la aleatoriedad ayuda

Cuando el modelo de computación se restringe a las máquinas de Turing , actualmente se debate si la capacidad de realizar elecciones aleatorias permite resolver en tiempo polinomial algunos problemas que no podrían resolverse en ese tiempo sin dicha capacidad; esta es la cuestión de si P = BPP. Sin embargo, en otros contextos, existen ejemplos específicos de problemas donde la aleatorización produce mejoras significativas.

  • Basándonos en el ejemplo inicial que nos motivó: dada una cadena exponencialmente larga de 2k caracteres , la mitad a y la mitad b, una máquina de acceso aleatorio requiere 2k -1 búsquedas en el peor de los casos para encontrar el índice de una a ; si se le permite hacer elecciones aleatorias, puede resolver este problema en un número polinomial esperado de búsquedas.
  • La forma natural de realizar un cálculo numérico en sistemas embebidos o sistemas ciberfísicos es proporcionar un resultado que se aproxime al correcto con alta probabilidad (o Cálculo Probablemente Aproximadamente Correcto (CPAC)). El problema complejo 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 [ 25 ].
  • En la complejidad de la comunicación , la igualdad de dos cadenas se puede verificar con cierta fiabilidad utilizandoregistro⁡norte{\displaystyle \log n}bits de comunicación con un protocolo aleatorio. Cualquier protocolo determinista requiereΘ(norte){\displaystyle \Theta (n)}bits si se defiende contra un oponente fuerte. [ 26 ]
  • El volumen de un cuerpo convexo puede estimarse mediante un algoritmo aleatorio con precisión arbitraria en tiempo polinomial. [ 27 ] Bárány y Füredi demostraron que ningún algoritmo determinista puede hacer lo mismo. [ 28 ] Esto es cierto incondicionalmente, es decir, sin depender de ninguna suposición teórica de complejidad, asumiendo que el cuerpo convexo solo puede consultarse como una caja negra.
  • Un ejemplo más teórico de complejidad de un lugar donde la aleatoriedad parece ayudar es la clase IP . IP consiste en todos los lenguajes que pueden ser aceptados (con alta probabilidad) por una interacción polinomialmente larga entre un probador todopoderoso y un verificador que implementa un algoritmo BPP. IP = PSPACE . [ 29 ] 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 sobre un número finito de moléculas), la capacidad de alcanzar un estado objetivo determinado desde un estado inicial es decidible, mientras que incluso aproximar la probabilidad de alcanzar un estado objetivo determinado (utilizando la probabilidad estándar basada en la concentración para determinar qué reacción ocurrirá a continuación) es indecidible. Más específicamente, una máquina de Turing limitada puede simularse con una probabilidad arbitrariamente alta de funcionar correctamente en todo momento, solo si se utiliza una red de reacciones químicas aleatoria. Con una red de reacciones químicas no determinista simple (cualquier reacción posible puede ocurrir a continuación), la capacidad computacional se limita a funciones recursivas primitivas . [ 30 ]

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 (2016-04-01). "Algoritmo aleatorio de Monte Carlo para el problema del conjunto 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 encontrar un valor que engañe la prueba de Fermat es menor que la probabilidad de que la radiación cósmica provoque 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. Archivado el 3 de septiembre de 2006 en Wayback Machine .
  4. ↑ Hoare, CAR (julio de 1961). "Algoritmo 64: Quicksort" . Communications of the ACM . 4 (7): 321. doi : 10.1145/366622.366644 . ISSN 0001-0782 . 
  5. ↑ Hoare, CAR (julio de 1961). "Algoritmo 65: find" . Communications of the 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" . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 .
  7. ↑ Williams, HC ; Shallit, JO (1994), "Factoring integers before computers", en Gautschi, Walter (ed.), Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 , Proceedings of Symposia in Applied Mathematics, vol. 48, Amer. Math. Soc., Providence, RI, pp. 481–531 , doi : 10.1090/psapm/048/1314885 , ISBN   978-0-8218-0291-5, MR 1314885 ; véase pág. 504, "Quizás Pocklington también merezca reconocimiento como inventor del algoritmo aleatorio".
  8. ↑ Berlekamp, ​​ER (1971). "Factoring polynomials over large finite fields" . Actas del segundo simposio de la ACM sobre manipulación simbólica y algebraica - SYMSAC '71 . Los Ángeles, California, Estados Unidos: ACM Press. pág. 223. doi : 10.1145/800204.806290 . ISBN  9781450377867. S2CID 6464612 . 
  9. 1 2 3 4 5 6 Knuth, Donald E. (1998). El arte de la programación informática, volumen 3: (2.ª ed.) clasificación y búsqueda . EE. UU.: 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 del original el 3 de marzo de 2016
  11. ↑ Konheim, Alan G.; Weiss, Benjamin (noviembre de 1966). "Una disciplina de ocupación y aplicaciones" . SIAM Journal on Applied Mathematics . 14 (6): 1266– 1274. doi : 10.1137/0114101 . ISSN 0036-1399 . 
  12. ↑ Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). "Clases universales de funciones hash" . Journal of Computer and System Sciences . 18 (2): 143– 154. doi : 10.1016/0022-0000(79)90044-8 . ISSN 0022-0000 . 
  13. ↑ Bloom, Burton H. (julio de 1970). "Compromisos espacio-temporales en la codificación hash con errores permisibles" . Communications of the 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 . 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 salto (PS, PDF) (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Maryland. CS-TR-2222.
  16. 1 2 Alon, Noga ; Spencer, Joel H. (2016). El método probabilístico (Cuarta ed.). Hoboken, Nueva Jersey: Wiley. ISBN  978-1-119-06195-3OCLC 910535517​​ 
  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). "Graph Theory and Probability" . Canadian Journal of Mathematics . 11 : 34–38 . doi : 10.4153/CJM-1959-003-9 . ISSN 0008-414X . S2CID 122784453 .  
  19. ↑ Seidel R. Análisis inverso de algoritmos geométricos aleatorios .
  20. ↑ Karger, David R. (1999). "Muestreo aleatorio en problemas de diseño de cortes, flujos y redes". Matemáticas de la investigación operativa . 24 (2): 383– 413. CiteSeerX 10.1.1.215.794 . doi : 10.1287/moor.24.2.383 . 
  21. ↑ "6.046J Lección 22: Desaleatorización | Diseño y análisis de algoritmos | Ingeniería eléctrica e informática" . MIT OpenCourseWare . Consultado el 27 de diciembre de 2024 .
  22. ↑ Luby, Michael; Wigderson, Avi (julio de 1995). Independencia por pares y desaleatorización (Informe). EE. UU.: Universidad de California en Berkeley.
  23. 1 2 "Apuntes de clase, Capítulo 3. Técnicas básicas de desaleatorización" . people.seas.harvard.edu . Consultado el 27 de diciembre de 2024 .
  24. ↑ Chazelle, B.; Friedman, J. (1990-09-01). "Una visión determinista del muestreo aleatorio y su uso en geometría" . Combinatorica . 10 (3): 229– 249. doi : 10.1007/BF02122778 . ISSN 1439-6912 . 
  25. ↑ Alippi, Cesare (2014), Inteligencia para sistemas embebidos , Springer, ISBN 978-3-319-05278-6.
  26. ↑ Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity , Cambridge University Press, ISBN 9780521029834Para el límite inferior determinista, véase la página  11; para el límite superior aleatorio logarítmico, véanse las páginas  31-32.
  27. ↑ 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 
  28. ↑ Füredi, Z. ; Bárány, I. (1986), "Computing the volume is difficult", 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, S2CID 17867291 
  29. ↑ Shamir, A. (1992), "IP = PSPACE", Journal of the ACM , 39 (4): 869– 877, doi : 10.1145/146585.146609 , S2CID 315182 
  30. ↑ 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) , Serie de computación natural, Springer-Verlag, pp. 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-7Capítulo 5: Análisis probabilístico y algoritmos aleatorios, págs.  91–122.
  • Dirk Draheim. « Semántica del cálculo lambda tipado probabilístico (semántica de cadenas de Markov, comportamiento de terminación y semántica denotacional) » . Springer, 2017.
  • Jon Kleinberg y Éva Tardos . Diseño de algoritmos . Capítulo 13: "Algoritmos aleatorios".
  • Fallis, D. (2000). "La fiabilidad de los algoritmos aleatorios". The British Journal for the Philosophy of Science . 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 . Un estudio sobre algoritmos aleatorios.
  • Christos Papadimitriou (1993), Complejidad computacional (1.ª  ed.), Addison Wesley, ISBN 978-0-201-53082-7Capítulo 11: Computación aleatoria, págs.  241–278.
  • Rabin, Michael O. (1980). "Algoritmo probabilístico para probar la primalidad" . Journal of Number Theory . 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 cortes, flujos y redes , Matemáticas de la investigación operativa, 24(2):383–413, 1999.
  • "Algoritmos aleatorios para la computación científica" (RASC), OSTI.GOV (10 de julio de 2021).
Obtenido de " https://en.wikipedia.org/w/index.php?title=Randomized_algorithm&oldid=1351521127 "
Lecturas relacionadas
6 articulos
AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...AleatoriedadAleatoriedadEn el uso común, la aleatoriedad es la falta aparente o real de un patrón definido o de previsibilidad en la información. [1] [2] Una secuencia ale...Distribución uniforme discretaDistribución uniforme discretaEn teoría de probabilidad y estadística , la distribución uniforme discreta es una distribución de probabilidad simétrica en la que cada uno de un ...{\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}Algoritmo de Las VegasEn informática , un algoritmo de Las Vegas es un algoritmo aleatorio que siempre da resultados correctos ; es decir, siempre produce el resultado c...Ordenación rápidaOrdenación rápidaQuicksort es un algoritmo de ordenamiento eficiente y de uso general . Quicksort fue desarrollado por el informático británico Tony Hoare en 1959 [...Algoritmo de Monte CarloAlgoritmo de Monte CarloEn informática , un algoritmo de Monte Carlo es un algoritmo aleatorio cuyo resultado puede ser incorrecto con una probabilidad determinada (normal...