En informática , la detección de ciclos o la búsqueda de ciclos es el problema algorítmico de encontrar un ciclo en una secuencia de valores de función iterados .
Para cualquier función f que mapea un conjunto finito S consigo mismo, y cualquier valor inicial x 0 en S , la secuencia de valores de función iterados
eventualmente debe usar el mismo valor dos veces: debe haber algún par de índices distintos i y j tales que x i = x j . Una vez que esto sucede, la secuencia debe continuar periódicamente , mediante la repetición de la misma secuencia de valores de x i a x j - 1 . La detección de ciclos es el problema de encontrar i y j , dados f y x 0 .
Se conocen varios algoritmos para encontrar ciclos de forma rápida y con poca memoria. Robert W. Floyd 's tortuga y algoritmo de liebre mueve dos punteros a diferentes velocidades a través de la secuencia de valores hasta que ambos punto a valores iguales. Alternativamente, el algoritmo de Brent se basa en la idea de búsqueda exponencial . Tanto los algoritmos de Floyd como los de Brent usan solo un número constante de celdas de memoria y toman una cantidad de evaluaciones de funciones que es proporcional a la distancia desde el inicio de la secuencia hasta la primera repetición. Varios otros algoritmos intercambian grandes cantidades de memoria por menos evaluaciones de funciones.
Las aplicaciones de detección de ciclos incluyen probar la calidad de generadores de números pseudoaleatorios y funciones hash criptográficas , algoritmos de teoría numérica computacional , detección de bucles infinitos en programas de computadora y configuraciones periódicas en autómatas celulares , análisis automatizado de formas de estructuras de datos de listas vinculadas y detección de interbloqueos. para la gestión de transacciones en DBMS .
Ejemplo
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/d/d7/Functional_graph.svg/330px-Functional_graph.svg.png)
La figura muestra una función f que mapea el conjunto S = {0,1,2,3,4,5,6,7,8 } a sí mismo. Si se parte de x 0 = 2 y se aplica repetidamente f , se ve la secuencia de valores
- 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....
El ciclo en esta secuencia de valores es 6, 3, 1 .
Definiciones
Deje S ser cualquier conjunto finito, f ser cualquier función de S a sí mismo, y x 0 ser cualquier elemento de S . Para cualquier i > 0 , sea x i = f ( x i - 1 ) . Sea μ el índice más pequeño tal que el valor x μ reaparezca infinitamente a menudo dentro de la secuencia de valores x i , y sea λ (la longitud del bucle) el número entero positivo más pequeño tal que x μ = x λ + μ . El problema de detección de ciclos es la tarea de encontrar λ y μ . [1]
Uno puede ver el mismo problema graficando teóricamente , construyendo un grafo funcional (es decir, un grafo dirigido en el que cada vértice tiene un solo borde saliente) cuyos vértices son los elementos de S y cuyos bordes mapean un elemento a el valor de la función correspondiente, como se muestra en la figura. El conjunto de vértices alcanzables desde el vértice inicial x 0 forma un subgrafo con una forma que se asemeja a la letra griega rho ( ρ ): una ruta de longitud μ desde x 0 hasta un ciclo de λ vértices. [2]
Representación informática
Generalmente, f no se especificará como una tabla de valores, como se muestra en la figura anterior. Más bien, un algoritmo de detección de ciclo se puede dar acceso ni a la secuencia de valores x i , o a una subrutina para el cálculo de f . La tarea consiste en encontrar λ y μ mientras examina la menor cantidad de valores de la secuencia o realiza la menor cantidad posible de llamadas a subrutinas. Por lo general, también es importante la complejidad espacial de un algoritmo para el problema de detección de ciclos: deseamos resolver el problema utilizando una cantidad de memoria significativamente menor de la que se necesitaría para almacenar la secuencia completa.
En algunas aplicaciones, y en particular en el algoritmo rho de Pollard para la factorización de enteros , el algoritmo tiene un acceso mucho más limitado a S y a f . En el algoritmo rho de Pollard, por ejemplo, S es el conjunto de números enteros módulo un factor primo desconocido del número a factorizar, por lo que incluso el tamaño de S es desconocido para el algoritmo. Para permitir el uso de algoritmos de detección de ciclos con un conocimiento tan limitado, se pueden diseñar en base a las siguientes capacidades. Inicialmente, se supone que el algoritmo tiene en su memoria un objeto que representa un puntero al valor inicial x 0 . En cualquier paso, puede realizar una de estas tres acciones: puede copiar cualquier puntero que tenga a otro objeto en la memoria, puede aplicar fy reemplazar cualquiera de sus punteros por un puntero al siguiente objeto en la secuencia, o puede aplicar una subrutina para determinar si dos de sus punteros representan valores iguales en la secuencia. La acción de prueba de igualdad puede involucrar algún cálculo no trivial: por ejemplo, en el algoritmo rho de Pollard, se implementa probando si la diferencia entre dos valores almacenados tiene un máximo común divisor no trivial con el número a factorizar. [2] En este contexto, por analogía con el modelo de cálculo de la máquina de puntero , un algoritmo que solo usa copia de puntero, avance dentro de la secuencia y pruebas de igualdad puede denominarse algoritmo de puntero.
Algoritmos
Si la entrada se da como una subrutina para calcular f , el problema de detección de ciclos puede resolverse trivialmente usando solo aplicaciones de función λ + μ , simplemente calculando la secuencia de valores x i y usando una estructura de datos como una tabla hash para almacenar estos valores y compruebe si ya se ha almacenado cada valor posterior. Sin embargo, la complejidad espacial de este algoritmo es proporcional a λ + μ , innecesariamente grande. Además, implementar este método como un algoritmo de puntero requeriría aplicar la prueba de igualdad a cada par de valores, lo que da como resultado un tiempo cuadrático en general. Por lo tanto, la investigación en esta área se ha concentrado en dos objetivos: utilizar menos espacio que este algoritmo ingenuo y encontrar algoritmos de puntero que utilicen menos pruebas de igualdad.
La liebre y la tortuga de Floyd
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/5f/Tortoise_and_hare_algorithm.svg/280px-Tortoise_and_hare_algorithm.svg.png)
El algoritmo de búsqueda de ciclos de Floyd es un algoritmo de puntero que usa solo dos punteros, que se mueven a través de la secuencia a diferentes velocidades. También se le llama el "algoritmo de la liebre y la tortuga", en alusión a la fábula de Esopo de La liebre y la tortuga .
El algoritmo lleva el nombre de Robert W. Floyd , a quien Donald Knuth le atribuyó su invención . [3] [4] Sin embargo, el algoritmo no aparece en el trabajo publicado de Floyd, y esto puede ser una atribución errónea: Floyd describe algoritmos para enumerar todos los ciclos simples en un gráfico dirigido en un artículo de 1967, [5] pero este artículo no Describa el problema de búsqueda de ciclos en gráficos funcionales que es el tema de este artículo. De hecho, la declaración de Knuth (en 1969), atribuyéndola a Floyd, sin citarla, es la primera aparición conocida impresa y, por lo tanto, puede ser un teorema popular , no atribuible a un solo individuo. [6]
La información clave del algoritmo es la siguiente. Si hay un ciclo, entonces, para cualquier número entero i ≥ μ y k ≥ 0 , x i = x i + kλ , donde λ es la longitud del bucle que se va a encontrar y μ es el índice del primer elemento del ciclo. . Con base en esto, se puede demostrar que i = kλ ≥ μ para algunos k si y solo si x i = x 2 i . Por lo tanto, el algoritmo solo necesita verificar los valores repetidos de esta forma especial, uno dos veces más lejos del comienzo de la secuencia que el otro, para encontrar un período ν de una repetición que sea un múltiplo de λ . Una vez que se encuentra ν , el algoritmo recorre la secuencia desde su inicio para encontrar el primer valor repetido x μ en la secuencia, utilizando el hecho de que λ divide a ν y, por lo tanto, x μ = x μ + v . Finalmente, una vez que se conoce el valor de μ , es trivial encontrar la longitud λ del ciclo de repetición más corto, buscando la primera posición μ + λ para la cual x μ + λ = x μ .
Por tanto, el algoritmo mantiene dos punteros en la secuencia dada, uno (la tortuga) en x i , y el otro (la liebre) en x 2 i . En cada paso del algoritmo, aumenta i en uno, moviendo la tortuga un paso hacia adelante y la liebre dos pasos hacia adelante en la secuencia, y luego compara los valores de secuencia en estos dos punteros. El valor más pequeño de i > 0 para el cual la tortuga y la liebre apuntan a valores iguales es el valor deseado ν .
El siguiente código de Python muestra cómo se puede implementar esta idea como un algoritmo.
def floyd ( f , x0 ): # Fase principal del algoritmo: encontrar una repetición x_i = x_2i. # La liebre se mueve dos veces más rápido que la tortuga y # la distancia entre ellas aumenta en 1 en cada paso. # Eventualmente ambos estarán dentro del ciclo y luego, # en algún momento, la distancia entre ellos será # divisible por el período λ. tortuga = f ( x0 ) # f (x0) es el elemento / nodo junto a x0. liebre = f ( f ( x0 )) mientras tortuga ! = liebre : tortuga = f ( tortuga ) liebre = f ( f ( liebre )) # En este punto, la posición de la tortuga, ν, que también es # igual a la distancia entre la liebre y la tortuga, es divisible por # el período λ. Así que la liebre que se mueve en círculo un paso a la vez, # y la tortuga (restablecer a x0) que se mueve hacia el círculo, # se cruzarán al comienzo del círculo. Debido a que la # distancia entre ellos es constante en 2ν, un múltiplo de λ, # estarán de acuerdo tan pronto como la tortuga alcance el índice μ. # Encuentre la posición μ de la primera repetición. mu = 0 tortuga = x0 mientras tortuga ! = liebre : tortuga = f ( tortuga ) liebre = f ( liebre ) # Liebre y tortuga se mueven a la misma velocidad mu + = 1 # Encuentre la duración del ciclo más corto comenzando por x_μ # La liebre se mueve un paso a la vez mientras la tortuga está quieta. # lam se incrementa hasta que se encuentra λ. lam = 1 liebre = f ( tortuga ) mientras que tortuga ! = liebre : liebre = f ( liebre ) lam + = 1 volver lam , mu
Este código solo accede a la secuencia almacenando y copiando punteros, evaluaciones de funciones y pruebas de igualdad; por lo tanto, califica como un algoritmo de puntero. El algoritmo utiliza operaciones O ( λ + μ ) de estos tipos y O (1) espacio de almacenamiento. [7]
Algoritmo de Brent
Richard P. Brent describió un algoritmo alternativo de detección de ciclos que, como el algoritmo de la tortuga y la liebre, requiere solo dos punteros en la secuencia. [8] Sin embargo, se basa en un principio diferente: buscar la potencia más pequeña de dos 2 i que sea mayor que λ y μ . Para i = 0, 1, 2, ... , el algoritmo compara x 2 i −1 con cada valor de secuencia subsiguiente hasta la siguiente potencia de dos, deteniéndose cuando encuentra una coincidencia. Tiene dos ventajas en comparación con el algoritmo de la tortuga y la liebre: encuentra la longitud correcta λ del ciclo directamente, en lugar de tener que buscarla en una etapa posterior, y sus pasos implican solo una evaluación de f en lugar de tres. [9]
El siguiente código de Python muestra cómo funciona esta técnica con más detalle.
def brent ( f , x0 ): # fase principal: buscar potencias sucesivas de dos potencia = lam = 1 tortuga = x0 liebre = f ( x0 ) # f (x0) es el elemento / nodo junto a x0. while tortuga ! = liebre : if power == lam : # es hora de iniciar una nueva potencia de dos? tortuga = poder de la liebre * = 2 lam = 0 liebre = f ( liebre ) lam + = 1 # Encuentra la posición de la primera repetición de la longitud λ tortuga = liebre = x0 para i en rango ( lam ): # rango (lam) produce una lista con los valores 0, 1, ..., lam-1 liebre = f ( liebre ) # La distancia entre la liebre y la tortuga ahora es λ. # Luego, la liebre y la tortuga se mueven a la misma velocidad hasta que se ponen de acuerdo mu = 0 mientras tortuga ! = Liebre : tortuga = f ( tortuga ) liebre = f ( liebre ) mu + = 1 volver lam , mu
Al igual que el algoritmo de la tortuga y la liebre, este es un algoritmo de puntero que utiliza pruebas de O ( λ + μ ) y evaluaciones de funciones y espacio de almacenamiento O (1) . No es difícil demostrar que el número de evaluaciones de funciones nunca puede ser mayor que el del algoritmo de Floyd. Brent afirma que, en promedio, su algoritmo de búsqueda de ciclos se ejecuta alrededor de un 36% más rápido que el de Floyd y que acelera el algoritmo rho de Pollard en alrededor de un 24%. También realiza un análisis de caso promedio para una versión aleatoria del algoritmo en el que la secuencia de índices trazada por el más lento de los dos punteros no son las potencias de dos en sí mismas, sino un múltiplo aleatorio de las potencias de dos. Aunque su principal aplicación prevista fue en algoritmos de factorización de enteros, Brent también analiza aplicaciones para probar generadores de números pseudoaleatorios. [8]
Algoritmo de Gosper
El algoritmo de RW Gosper [10] [11] encuentra el período, y el límite superior e inferior del punto de partida, y , del primer ciclo. La diferencia entre el límite superior e inferior es del mismo orden que el período, por ejemplo..
La característica principal del algoritmo de Gosper es que nunca retrocede para reevaluar la función del generador y es económico tanto en el espacio como en el tiempo. Podría describirse aproximadamente como una versión paralela del algoritmo de Brent. Mientras que el algoritmo de Brent aumenta gradualmente la brecha entre la tortuga y la liebre, el algoritmo de Gosper usa varias tortugas (se guardan varios valores anteriores), que están espaciados aproximadamente exponencialmente. De acuerdo con la nota en el ítem 132 de HAKMEM , este algoritmo detectará la repetición antes de la tercera aparición de cualquier valor, por ejemplo. el ciclo se repetirá como máximo dos veces. Esta nota también establece que es suficiente almacenarvalores previos; sin embargo, la implementación proporcionada [10] almacenavalores. Por ejemplo: los valores de la función son enteros de 32 bits, y se sabe a priori que la segunda iteración del ciclo termina después de como máximo 2 32 evaluaciones de función desde el principio, a saber.. Entonces basta con almacenar 33 enteros de 32 bits.
Sobre la -a evaluación de la función del generador, el algoritmo compara el valor generado con valores previos; observa eso sube al menos a y como mucho . Por lo tanto, la complejidad temporal de este algoritmo es. Ya que almacena valores, su complejidad espacial es . Esto es bajo el supuesto habitual, presente a lo largo de este artículo, de que el tamaño de los valores de la función es constante. Sin este supuesto, la complejidad del espacio es ya que necesitamos al menos valores distintos y, por lo tanto, el tamaño de cada valor es .
Compensaciones entre el tiempo y el espacio
Varios autores han estudiado técnicas para la detección de ciclos que utilizan más memoria que los métodos de Floyd y Brent, pero detectan ciclos más rápidamente. En general, estos métodos almacenan varios valores de secuencia calculados previamente y prueban si cada nuevo valor es igual a uno de los valores calculados previamente. Para hacerlo rápidamente, generalmente usan una tabla hash o una estructura de datos similar para almacenar los valores calculados previamente y, por lo tanto, no son algoritmos de puntero: en particular, generalmente no se pueden aplicar al algoritmo rho de Pollard. Donde estos métodos difieren es en cómo determinan qué valores almacenar. Siguiendo a Nivasch, [12] examinamos estas técnicas brevemente.
- Brent [8] ya describe variaciones de su técnica en las que los índices de valores de secuencia guardados son potencias de un número R distinto de dos. Al elegir R para que sea un número cercano a uno y almacenar los valores de secuencia en índices que están cerca de una secuencia de potencias consecutivas de R , un algoritmo de detección de ciclos puede usar una serie de evaluaciones de funciones que se encuentran dentro de un factor arbitrariamente pequeño del óptimo. λ + μ . [13] [14]
- Sedgewick, Szymanski y Yao [15] proporcionan un método que utiliza celdas de memoria M y requiere, en el peor de los casos, soloevaluaciones de funciones, para alguna constante c , que muestran que es óptima. La técnica implica mantener un parámetro numérico d , almacenar en una tabla solo aquellas posiciones en la secuencia que son múltiplos de d , y borrar la tabla y duplicar d siempre que se hayan almacenado demasiados valores.
- Varios autores han descrito métodos de puntos distinguidos que almacenan valores de función en una tabla basados en un criterio que involucra los valores, en lugar de (como en el método de Sedgewick et al.) Basados en sus posiciones. Por ejemplo, se pueden almacenar valores iguales a cero módulo, algún valor d . [16] [17] Más simplemente, Nivasch [12] acredita a DP Woodruff la sugerencia de almacenar una muestra aleatoria de valores vistos anteriormente, haciendo una elección aleatoria apropiada en cada paso para que la muestra permanezca aleatoria.
- Nivasch [12] describe un algoritmo que no usa una cantidad fija de memoria, pero para el cual la cantidad esperada de memoria usada (bajo el supuesto de que la función de entrada es aleatoria) es logarítmica en la longitud de la secuencia. Un artículo se almacena en la tabla de memoria, con esta técnica, cuando ningún artículo posterior tiene un valor menor. Como muestra Nivasch, los elementos con esta técnica se pueden mantener usando una estructura de datos de pila , y cada valor de secuencia sucesiva necesita compararse solo con la parte superior de la pila. El algoritmo termina cuando se encuentra el elemento de secuencia repetida con el valor más pequeño. Ejecutar el mismo algoritmo con múltiples pilas, usando permutaciones aleatorias de los valores para reordenar los valores dentro de cada pila, permite una compensación de tiempo-espacio similar a los algoritmos anteriores. Sin embargo, incluso la versión de este algoritmo con una sola pila no es un algoritmo de puntero, debido a las comparaciones necesarias para determinar cuál de los dos valores es menor.
Cualquier algoritmo de detección de ciclo que almacene como máximo M valores de la secuencia de entrada debe realizar al menosevaluaciones de funciones. [18] [19]
Aplicaciones
La detección de ciclos se ha utilizado en muchas aplicaciones.
- Determinar la duración del ciclo de un generador de números pseudoaleatorios es una medida de su fuerza. Ésta es la aplicación citada por Knuth al describir el método de Floyd. [3] Brent [8] describe los resultados de probar un generador congruencial lineal de esta manera; su período resultó ser significativamente menor que el anunciado. Para generadores más complejos, la secuencia de valores en la que se encuentra el ciclo puede no representar la salida del generador, sino su estado interno.
- Varios algoritmos teóricos de números se basan en la detección de ciclos, incluido el algoritmo rho de Pollard para la factorización de enteros [20] y su algoritmo canguro relacionado para el problema del logaritmo discreto . [21]
- En aplicaciones criptográficas , la capacidad de encontrar dos valores distintos x μ −- 1 y x λ + μ −- 1 mapeados por alguna función criptográfica ƒ al mismo valor x μ puede indicar una debilidad en ƒ. Por ejemplo, Quisquater y Delescaille [17] aplican algoritmos de detección de ciclos en la búsqueda de un mensaje y un par de claves estándar de cifrado de datos que asignan ese mensaje al mismo valor cifrado; Kaliski , Rivest y Sherman [22] también utilizan algoritmos de detección de ciclos para atacar DES. La técnica también se puede utilizar para encontrar una colisión en una función hash criptográfica . [23]
- La detección de ciclos puede ser útil como una forma de descubrir bucles infinitos en ciertos tipos de programas de computadora . [24]
- Las configuraciones periódicas en las simulaciones de autómatas celulares se pueden encontrar aplicando algoritmos de detección de ciclos a la secuencia de estados de los autómatas. [12]
- El análisis de formas de estructuras de datos de listas vinculadas es una técnica para verificar la exactitud de un algoritmo que utiliza esas estructuras. Si un nodo en la lista apunta incorrectamente a un nodo anterior en la misma lista, la estructura formará un ciclo que puede ser detectado por estos algoritmos. [25] En Common Lisp , la impresora de expresión S , bajo el control de la
*print-circle*
variable, detecta la estructura de lista circular y la imprime de forma compacta. - Teske [14] describe aplicaciones en la teoría de grupos computacional : determinar la estructura de un grupo abeliano a partir de un conjunto de sus generadores. Los algoritmos criptográficos de Kaliski et al. [22] también puede verse como un intento de inferir la estructura de un grupo desconocido.
- Fich (1981) menciona brevemente una aplicación a la simulación por computadora de la mecánica celeste , que ella atribuye a William Kahan . En esta aplicación, la detección de ciclos en el espacio de fase de un sistema orbital puede usarse para determinar si el sistema es periódico dentro de la precisión de la simulación. [18]
- En la generación fractal de Mandelbrot Set se utilizan algunas técnicas de rendimiento para acelerar la generación de imágenes. Uno de ellos se llama "verificación de períodos", que consiste en encontrar los ciclos en una órbita puntual. Este artículo describe la técnica de " verificación de período ". Puedes encontrar otra explicación aquí . Es necesario implementar algunos algoritmos de detección de ciclos para implementar esta técnica.
Referencias
- ^ Joux, Antoine (2009), Criptoanálisis algorítmico , CRC Press, p. 223, ISBN 9781420070033.
- ↑ a b Joux (2009 , p. 224).
- ^ a b Knuth, Donald E. (1969), El arte de la programación informática, vol. II: Algoritmos seminuméricos , Addison-Wesley, p. 7, ejercicios 6 y 7
- ^ Manual de criptografía aplicada, por Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125 , describe este algoritmo y otros
- ^ Floyd, RW (1967), "Algoritmos no deterministas", J. ACM , 14 (4): 636–644, doi : 10.1145 / 321420.321422 , S2CID 1990464
- ^ La función hash BLAKE, por Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), pág. 21 , nota al pie 8
- ^ Joux (2009) , sección 7.1.1, algoritmo de búsqueda de ciclo de Floyd, págs. 225–226.
- ^ a b c d Brent, RP (1980), "Un algoritmo mejorado de factorización de Monte Carlo" (PDF) , BIT Numerical Mathematics , 20 (2): 176–184, doi : 10.1007 / BF01933190 , S2CID 17181286.
- ^ Joux (2009) , sección 7.1.2, algoritmo de búsqueda de ciclos de Brent, págs. 226–227.
- ^ a b "Copia archivada" . Archivado desde el original el 14 de abril de 2016 . Consultado el 8 de febrero de 2017 .CS1 maint: copia archivada como título ( enlace )
- ^ http://www.inwap.com/pdp10/hbaker/hakmem/flows.html
- ^ a b c d Nivasch, Gabriel (2004), "Detección de ciclos usando una pila", Information Processing Letters , 90 (3): 135–140, doi : 10.1016 / j.ipl.2004.01.016.
- ^ Schnorr, Claus P .; Lenstra, Hendrik W. (1984), "Un algoritmo de factorización de Monte Carlo con almacenamiento lineal", Mathematics of Computation , 43 (167): 289–311, doi : 10.2307 / 2007414 , hdl : 1887/3815 , JSTOR 2007414.
- ^ a b Teske, Edlyn (1998), "Un algoritmo eficiente en el espacio para el cálculo de la estructura de grupo", Matemáticas de la computación , 67 (224): 1637–1663, Bibcode : 1998MaCom..67.1637T , doi : 10.1090 / S0025-5718-98- 00968-5.
- ^ Sedgewick, Robert ; Szymanski, Thomas G .; Yao, Andrew C.-C. (1982), "La complejidad de encontrar ciclos en funciones periódicas", SIAM Journal on Computing , 11 (2): 376–390, doi : 10.1137 / 0211030.
- ^ van Oorschot, Paul C .; Wiener, Michael J. (1999), "Búsqueda de colisiones paralelas con aplicaciones criptoanalíticas" , Journal of Cryptology , 12 (1): 1–28, doi : 10.1007 / PL00003816 , S2CID 5091635.
- ^ a b Quisquater, J.-J .; Delescaille, J.-P., "How easy is collision search? Application to DES", Advances in Cryptology - EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques , Lecture Notes in Computer Science, 434 , Springer-Verlag, págs. 429–434, doi : 10.1007 / 3-540-46885-4_43.
- ^ a b Fich, Faith Ellen (1981), " Límites inferiores para el problema de detección de ciclos", Proc. 13 ° Simposio ACM sobre Teoría de la Computación , págs. 96-105, doi : 10.1145 / 800076.802462.
- ^ Allender, Eric W .; Klawe, Maria M. (1985), "Límites inferiores mejorados para el problema de detección de ciclos", Informática teórica , 36 (2-3): 231-237, doi : 10.1016 / 0304-3975 (85) 90044-1.
- ^ Pollard, JM (1975), "A Monte Carlo method for factorization", BIT , 15 (3): 331–334, doi : 10.1007 / BF01933667 , S2CID 122775546.
- ^ Pollard, JM (1978), "Métodos de Monte Carlo para el cálculo de índices (mod p )", Mathematics of Computation , American Mathematical Society, 32 (143): 918–924, doi : 10.2307 / 2006496 , JSTOR 2006496.
- ^ a b Kaliski, Burton S., Jr .; Rivest, Ronald L .; Sherman, Alan T. (1988), "¿Es el estándar de cifrado de datos un grupo? (Resultados de experimentos de ciclismo en DES)", Journal of Cryptology , 1 (1): 3-36, doi : 10.1007 / BF00206323 , S2CID 17224075.
- ^ Joux (2009) , Sección 7.5, Colisiones en funciones hash, págs. 242–245.
- ^ Van Gelder, Allen (1987), "Detección de bucle eficiente en Prolog usando la técnica de la tortuga y la liebre", Journal of Logic Programming , 4 (1): 23–31, doi : 10.1016 / 0743-1066 (87) 90020- 3.
- ^ Auguston, Mikhail; Hon, Miu Har (1997), "Assertions for Dynamic Shape Analysis of List Data Structures", AADEBUG '97, Actas del tercer taller internacional sobre depuración automática , artículos electrónicos de Linköping en informática y ciencias de la información, Universidad de Linköping , págs. 37– 42.
enlaces externos
- Gabriel Nivasch, El problema de detección de ciclos y el algoritmo de pila
- Tortuga y liebre , repositorio de patrones de Portland
- Algoritmo de detección de ciclo de Floyd (La tortuga y la liebre)
- Algoritmo de detección del ciclo de Brent (La tortuga que se teletransporta)