Detección de ciclo

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 una función iterada .

Para cualquier función $f$ que mapea un conjunto finito $S$ sobre sí mismo, y cualquier valor inicial $x 0$ en $S$ , la secuencia de valores de función iterados

x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots

Debe eventualmente 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 , repitiendo la misma secuencia de valores desde $x i$ hasta $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 rápidamente y con poca memoria. El algoritmo de la tortuga y la liebre de Robert W. Floyd mueve dos punteros a diferentes velocidades a través de la secuencia de valores hasta que ambos apuntan a valores iguales. Por otro lado, el algoritmo de Brent se basa en la búsqueda exponencial . Tanto el algoritmo de Floyd como el de Brent utilizan una cantidad constante de celdas de memoria y requieren un número de evaluaciones de función proporcional a la distancia desde el inicio de la secuencia hasta la primera repetición. Otros algoritmos priorizan el uso de memoria sobre la reducción del número de evaluaciones de función.

Las aplicaciones de la detección de ciclos incluyen la comprobación de la calidad de los generadores de números pseudoaleatorios y las funciones hash criptográficas , los algoritmos de teoría computacional de números , la detección de bucles infinitos en programas informáticos y configuraciones periódicas en autómatas celulares , el análisis automatizado de la forma de las estructuras de datos de listas enlazadas y la detección de interbloqueos para la gestión de transacciones en sistemas de gestión de bases de datos ( DBMS) .

Ejemplo

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 observa 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

Sea $S$ un conjunto finito cualquiera, $f una$ endofunción cualquiera de $S$ a sí mismo, y $x 0$ un elemento cualquiera 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 μ$ reaparece infinitas veces dentro de la secuencia de valores $x i$ , y sea $λ$ (la longitud del bucle) el entero positivo más pequeño tal que $x μ = x λ + μ$ . El problema de detección de ciclos es la tarea de encontrar $λ$ y $μ$ . ^{[ 1 ]}

Se puede abordar el mismo problema desde una perspectiva de teoría de grafos , construyendo un grafo funcional (es decir, un grafo dirigido en el que cada vértice tiene una única arista saliente) cuyos vértices son los elementos de $S$ y cuyas aristas asignan a cada elemento 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₀$ forma un subgrafo con una forma que se asemeja a la ^letra griega rho ( $ρ$ ): un camino de longitud $μ$ desde $x₀$ hasta un ciclo de $λ$ vértices. ^[ $2$ ^]

Los algoritmos prácticos de detección de ciclos no encuentran $λ$ y $μ$ con exactitud. ^{[ 1 ]} Generalmente encuentran límites inferiores y superiores $μ l \leq μ \leq μ h$ para el inicio del ciclo, y se debe realizar una búsqueda más detallada del rango si se necesita el valor exacto de $μ$ . Además, la mayoría de los algoritmos no garantizan encontrar $λ$ directamente, sino que pueden encontrar algún múltiplo $kλ < μ + λ$ . (Continuar la búsqueda durante $kλ / q$ pasos adicionales, donde $q$ es el divisor primo más pequeño de $kλ$ , permitirá encontrar el verdadero $λ$ o demostrar que $k = 1$ .)

Representación informática

Excepto en ejemplos sencillos como el anterior, $f$ no se especificará como una tabla de valores. Dicha tabla implica una complejidad espacial de $O (| S |)$ , y si eso es permisible, construir un arreglo de predecesores ( un arreglo asociativo que mapea $xᵢ$ $a$ i $)$ mientras se itera f detectará el primer valor repetido cuando se visite por segunda vez, momento en el que el valor en el arreglo de predecesores es $μ$ y el índice actual es $μ$ + $λ$ . En cambio, a un algoritmo de detección de ciclos se le proporciona una caja negra para generar la secuencia $xᵢ$ $,$ y la tarea es encontrar $λ$ y $μ$ usando muy poca memoria.

La caja negra podría consistir en una implementación de la función de recurrencia $f$ , pero también podría almacenar un estado interno adicional para optimizar el cálculo. Si bien $x i = f (x i - 1)$ debe ser verdadera en principio , su cálculo directo podría resultar costoso; la función podría definirse en términos del logaritmo discreto de $x i - 1$ o alguna otra propiedad difícil de calcular que solo puede determinarse en la práctica a partir de información adicional. En tales casos, el número de cajas negras necesarias se convierte en un indicador clave para diferenciar los algoritmos.

Una segunda razón para usar uno de estos algoritmos es que son algoritmos de punteros que no realizan ninguna operación sobre los elementos de $S$ , salvo comprobar si son iguales. Una implementación de arreglo asociativo requiere calcular una función hash sobre los elementos de $S$ o bien ordenarlos . Pero la detección de ciclos se puede aplicar en los casos en que ninguna de estas opciones sea posible.

El ejemplo clásico es el algoritmo rho de Pollard para la factorización de enteros , que busca un factor $p$ de un número $n$ dado buscando valores $x i$ y $x i + λ$ que sean iguales módulo $p$ sin conocer $p$ de antemano. Esto se hace calculando el máximo común divisor de la diferencia $x i - x i + λ$ con un múltiplo conocido de $p$ , a saber, $n$ . Si el mcd no es trivial (ni 1 ni $n$ ), entonces el valor es un factor propio de $n$ , como se desea. ^{[ 2 ]} Si $n$ no es primo, debe tener al menos un factor $p \leq \sqrt n$ , y por la paradoja del cumpleaños , una función aleatoria $f$ tiene una longitud de ciclo esperada (módulo $p$ ) de $\sqrt$ $p$ $\leq$ $4$ $\sqrt$ $n$ .

Algoritmos

Si la entrada se proporciona como una subrutina para calcular $f$ , el problema de detección de ciclos puede resolverse trivialmente utilizando solo $λ + μ$ aplicaciones de la función, simplemente calculando la secuencia de valores $x i$ y utilizando una estructura de datos como una tabla hash para almacenar estos valores y comprobar si cada valor subsiguiente ya se ha almacenado. Sin embargo, la complejidad espacial de este algoritmo es proporcional a $λ + μ$ , innecesariamente grande. Además, para implementar este método como un algoritmo de punteros se requeriría aplicar la prueba de igualdad a cada par de valores, lo que resultaría en 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 punteros que utilicen menos pruebas de igualdad.

La tortuga y la liebre de Floyd

El algoritmo de búsqueda de ciclos de Floyd es un algoritmo de punteros que utiliza solo dos punteros, los cuales se mueven a través de la secuencia a diferentes velocidades. También se le conoce como el "algoritmo de la tortuga y la liebre", en alusión a la fábula de Esopo de La tortuga y la liebre .

El algoritmo recibe su nombre de Robert W. Floyd , a quien Donald Knuth le atribuyó su invención . ^{[ 3 ]}^{[ 4 ]} Sin embargo, el algoritmo no aparece en la obra publicada de Floyd, y esto podría deberse a una atribución errónea: Floyd describe algoritmos para enumerar todos los ciclos simples en un grafo dirigido en un artículo de 1967, ^{[ 5 ]} pero este artículo no describe el problema de la búsqueda de ciclos en grafos funcionales que es el tema de este artículo. De hecho, la afirmación de Knuth (en 1969), atribuyéndolo a Floyd, sin citar la fuente, es la primera aparición impresa conocida, y por lo tanto podría tratarse de un teorema popular , no atribuible a una sola persona. ^{[ 6 ]}

La idea clave del algoritmo es la siguiente. Si hay un ciclo, entonces, para cualesquiera enteros $i \geq μ$ y $k \geq 0$ , $x i = x i + kλ$ , donde $λ$ es la longitud del bucle a encontrar, $μ$ es el índice del primer elemento del ciclo y $k$ es un entero que representa el número de bucles. Basándonos en esto, se puede demostrar que $i = kλ \geq μ$ para algún $k$ si y solo si $x i = x 2 i$ (si $x i = x 2 i$ en el ciclo, entonces existe algún $k$ tal que $2 i = i + kλ$ , lo que implica que $i = kλ$ ; y si existen algunos $i$ y $k$ tales que $i = kλ$ , entonces $2i = i + kλ$ y $x 2 i = x i + kλ$ ). Por lo tanto, el algoritmo solo necesita verificar valores repetidos de esta forma especial, uno al doble de distancia del inicio 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 retrocede 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 que $x μ = x μ + v$ . Finalmente, una vez que se conoce el valor de $μ$ es trivial encontrar la longitud $λ$ del ciclo repetitivo más corto, buscando la primera posición $μ + λ$ para la cual $x μ + λ = x μ$ .

El algoritmo mantiene dos punteros a la secuencia dada, uno (la tortuga) en $x i$ , y el otro (la liebre) en $x 2 i$ . En cada paso del algoritmo, incrementa $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 la 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 Python muestra cómo se puede implementar esta idea como un algoritmo.

def floyd ( f , x0 ) -> ( int , int ): """Algoritmo de detección de ciclos de Floyd.""" # Fase principal del algoritmo: encontrar una repetición x_i = x_2i. # La liebre se mueve el doble de rápido que la tortuga y # la distancia entre ellas aumenta en 1 en cada paso. # Eventualmente ambas estarán dentro del ciclo y entonces, # en algún punto, la distancia entre ellas será # divisible por el período λ. tortuga = f ( x0 ) # f(x0) es el elemento/nodo siguiente 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 moviéndose en el ciclo un paso a la vez, # y la tortuga (reiniciada a x0) moviéndose hacia el ciclo, se # cruzarán al comienzo del ciclo. Debido a que la # distancia entre ellas es constante en 2ν, un múltiplo de λ, # coincidirán tan pronto como la tortuga alcance el índice μ.# Encuentra la posición μ de la primera repetición. mu = 0 tortuga = x0 mientras tortuga != liebre : tortuga = f ( tortuga ) liebre = f ( liebre ) # La liebre y la tortuga se mueven a la misma velocidad mu += 1# Encuentra la longitud del ciclo más corto comenzando desde 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 tortuga != liebre : liebre = f ( liebre ) lam += 1devolver lam , mu

Este código solo accede a la secuencia almacenando y copiando punteros, evaluando funciones y realizando pruebas de igualdad; por lo tanto, se clasifica como un algoritmo de punteros. El algoritmo utiliza $O (λ + μ)$ operaciones de este tipo y un espacio de almacenamiento de $O (1)$ . ^{[ 7 ]}

El algoritmo de Brent

Richard P. Brent describió un algoritmo alternativo de detección de ciclos que, al igual que el algoritmo de la tortuga y la liebre, requiere solo dos punteros a la secuencia. ^{[ 8 ]} Sin embargo, se basa en un principio diferente: buscar la potencia de dos más pequeña $2 i$ que sea mayor que $λ$ y $μ$ . Para $i = 0, 1, 2, ...$ , el algoritmo compara $x 2 i - 1$ con cada valor de la 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 la función $f$ en lugar de tres. ^{[ 9 ]}

El siguiente código Python muestra con más detalle cómo funciona esta técnica.

def brent ( f , x0 ) -> ( int , int ): """Algoritmo de detección de ciclos de Brent.""" # Fase principal: búsqueda de potencias sucesivas de dos power = lam = 1 tortoise = x0 hare = f ( x0 ) # f(x0) es el elemento/nodo siguiente a x0. # Esto supone que hay un ciclo; de lo contrario, este bucle no terminará while tortoise != hare : if power == lam : # ¿Es hora de empezar una nueva potencia de dos? tortoise = hare power *= 2 lam = 0 hare = f ( hare ) lam += 1# Encuentra la posición de la primera repetición de longitud λ tortuga = liebre = x0 para i en rango ( lam ): liebre = f ( liebre ) # La distancia entre la liebre y la tortuga ahora es λ.# A continuación, la liebre y la tortuga se mueven a la misma velocidad hasta que coinciden mu = 0 mientras tortuga != liebre : tortuga = f ( tortuga ) liebre = f ( liebre ) mu += 1devolver lam , mu

Al igual que el algoritmo de la tortuga y la liebre, este es un algoritmo de punteros que utiliza $O (λ + μ)$ pruebas y evaluaciones de funciones, y un espacio de almacenamiento de $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 detección de ciclos se ejecuta un 36 % más rápido que el de Floyd y que acelera el algoritmo rho de Pollard en un 24 % aproximadamente. También realiza un análisis del caso promedio para una versión aleatoria del algoritmo en la que la secuencia de índices rastreada por el puntero más lento no son potencias de dos, sino un múltiplo aleatorio de potencias de dos. Aunque su principal aplicación prevista era en algoritmos de factorización de enteros, Brent también analiza aplicaciones en la prueba de generadores de números pseudoaleatorios. ^{[ 8 ]}

El algoritmo de Gosper

El algoritmo de RW Gosper ^{[ 10 ]}^{[ 11 ]} encuentra el período $\lambda$ y el límite inferior y superior del punto de partida, $\mu _{l}$ y $\mu _{u}$ , del primer ciclo. La diferencia entre el límite inferior y el superior es del mismo orden que el período, es decir $\mu _{l}+\lambda \approx \mu _{h}$ .

El algoritmo mantiene una matriz de tortugas. $T_{j}$ . Para cada $x_{i}$ :

Para cada $0\leq j\leq \log _{2}i,$ comparar $x_{i}$ a $T_{j}$ .
Si $x_{i}=T_{j}$ , se ha detectado un ciclo, de longitud $\lambda =(i-2^{j}){\bmod {2}}^{j+1}+1.$
Si no se encuentra ninguna coincidencia, establezca $T_{k}\leftarrow x_{i}$ , dónde $k$ es el número de ceros finales en la representación binaria de $i+1$ . Es decir, la mayor potencia de 2 que divide a $i+1$ .

Si resulta inconveniente variar el número de comparaciones como $i$ aumenta, puede inicializar todo el $T_{j}=x_{0}$ pero luego debe regresar $\lambda =i$ si $x_{i}=T_{j}$ mientras $i<2^{j}$ .

Ventajas

Las principales características del algoritmo de Gosper son que es económico en espacio, muy económico en evaluaciones de la función generadora y siempre encuentra la longitud exacta del ciclo (nunca un múltiplo). El costo es una gran cantidad de comparaciones de igualdad. Podría describirse aproximadamente como una versión concurrente del algoritmo de Brent. Mientras que el algoritmo de Brent usa una sola tortuga, reposicionada cada vez que la liebre pasa una potencia de dos, el algoritmo de Gosper usa varias tortugas (se guardan varios valores anteriores), que están espaciadas aproximadamente de forma exponencial. Según la nota en el elemento 132 de HAKMEM , ^{[ 11 ]} este algoritmo detectará repetición antes de la tercera ocurrencia de cualquier valor, es decir, el ciclo se iterará como máximo dos veces. HAKMEM también afirma que es suficiente almacenar $\lceil \log _{2}\lambda \rceil$ valores anteriores; sin embargo, esto solo ofrece un ahorro si sabemos a priori que $\lambda$ es significativamente más pequeño que $\mu$ . Las implementaciones estándar ^{[ 10 ]} almacenan $\lceil \log _{2}(\mu +2\lambda )\rceil$ valores. Por ejemplo, supongamos que los valores de la función son enteros de 32 bits, por lo que $\mu +\lambda \leq 2^{32}$ y $\mu +2\lambda \leq 2^{33}.$ Entonces el algoritmo de Gosper encontrará el ciclo después de menos de $\mu +2\lambda$ evaluaciones de funciones (de hecho, lo más posible es $3\cdot 2^{31}-1$ ), mientras que consume el espacio de 33 valores (cada valor es un entero de 32 bits).

Complejidad

Sobre el $i$ -ésima evaluación de la función generadora, el algoritmo compara el valor generado con $\log _{2}i$ valores anteriores; observe que $i$ llega hasta al menos $\mu +\lambda$ y como máximo $\mu +2\lambda$ Por lo tanto, la complejidad temporal de este algoritmo es $O((\mu +\lambda )\cdot \log(\mu +\lambda ))$ Dado que almacena $\log _{2}(\mu +2\lambda )$ valores, su complejidad espacial es $\Theta (\log(\mu +\lambda ))$ Esto se basa en el modelo transdicotómico habitual , asumido a lo largo de este artículo, en el que el tamaño de los valores de la función es constante. Sin esta suposición, sabemos que requiere $\Omega (\log(\mu +\lambda ))$ espacio para almacenar $\mu +\lambda$ valores distintos, por lo que la complejidad espacial general es $\Omega (\log ^{2}(\mu +\lambda )).$

Compensaciones espacio-temporales

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 que detectan los ciclos con mayor rapidez. En general, estos métodos almacenan varios valores de secuencia previamente calculados y comprueban si cada nuevo valor es igual a alguno de los valores previamente calculados. Para hacerlo rápidamente, suelen utilizar una tabla hash o una estructura de datos similar para almacenar los valores previamente calculados, por lo que no son algoritmos de punteros; en particular, normalmente no se pueden aplicar al algoritmo rho de Pollard. La diferencia entre estos métodos radica en cómo determinan qué valores almacenar. Siguiendo a Nivasch, ^{[ 12 ]} revisamos brevemente estas técnicas.

Brent ^{[ 8 ]} ya describe variaciones de su técnica en las que los índices de los valores de secuencia guardados son potencias de un número $R$ distinto de dos. Al elegir $R$ como 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 cantidad de evaluaciones de función que está dentro de un factor arbitrariamente pequeño del óptimo $λ + μ$ . ^{[ 13 ]}^{[ 14 ]}
Sedgewick, Szymanski y Yao ^{[ 15 ]} proporcionan un método que utiliza $M$ celdas de memoria y requiere en el peor de los casos solo $(\lambda +\mu )(1+cM^{-1/2})$ Evaluaciones de funciones, para alguna constante $c$ , que demuestran ser óptimas. La técnica consiste en mantener un parámetro numérico $d$ , almacenar en una tabla solo aquellas posiciones de la secuencia que son múltiplos de $d$ , y borrar la tabla y duplicar $d$ cuando se han almacenado demasiados valores.
Varios autores han descrito métodos puntuales distinguidos que almacenan valores de función en una tabla basándose en un criterio que involucra los valores, en lugar de (como en el método de Sedgewick et al.) basándose en sus posiciones. Por ejemplo, se podrían almacenar valores iguales a cero módulo algún valor $d .$ ^{[ 16 ]}^{[ 17 ]} De manera más simple, Nivasch ^{[ 12 ]} atribuye a DP Woodruff la sugerencia de almacenar una muestra aleatoria de valores vistos previamente, haciendo una elección aleatoria apropiada en cada paso para que la muestra siga siendo aleatoria.
Nivasch ^{[ 12 ]} describe un algoritmo que no utiliza una cantidad fija de memoria, sino que la cantidad esperada de memoria utilizada (bajo el supuesto de que la función de entrada es aleatoria) es logarítmica en la longitud de la secuencia. Con esta técnica, un elemento se almacena en la tabla de memoria cuando ningún elemento posterior tiene un valor menor. Como muestra Nivasch, los elementos con esta técnica se pueden mantener utilizando una estructura de datos de pila , y cada valor sucesivo de la secuencia solo necesita compararse con la parte superior de la pila. El algoritmo termina cuando se encuentra el elemento de secuencia repetido con el valor más pequeño. Ejecutar el mismo algoritmo con múltiples pilas, utilizando permutaciones aleatorias de los valores para reordenarlos dentro de cada pila, permite una compensación tiempo-espacio similar a la de los algoritmos anteriores. Sin embargo, incluso la versión de este algoritmo con una sola pila no es un algoritmo de punteros, debido a las comparaciones necesarias para determinar cuál de dos valores es menor.

Cualquier algoritmo de detección de ciclos que almacene como máximo $M$ valores de la secuencia de entrada debe realizar al menos $(\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)$ evaluaciones de funciones. ^{[ 18 ]}^{[ 19 ]}

Aplicaciones

La detección de ciclos se ha utilizado en numerosas aplicaciones.

Determinar la longitud del ciclo de un generador de números pseudoaleatorios es una forma de medir su robustez. Esta 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 de lo 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 de teoría 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} que, mediante alguna función criptográfica ƒ, se asignen 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 del Estándar de Cifrado de Datos que asignen 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 puede utilizarse 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 informáticos . ^{[ 24 ]}
Las configuraciones periódicas en simulaciones de autómatas celulares pueden encontrarse aplicando algoritmos de detección de ciclos a la secuencia de estados del autómata. ^{[ 12 ]}
El análisis de la forma de las estructuras de datos de listas enlazadas es una técnica para verificar la corrección de un algoritmo que utiliza dichas estructuras. Si un nodo de la lista apunta incorrectamente a un nodo anterior de la misma lista, la estructura formará un ciclo que puede ser detectado por estos algoritmos. ^{[ 25 ]} En Common Lisp , el impresor de expresiones S , bajo el control de la *print-circle*variable, detecta la estructura circular de la lista 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 pueden considerarse como intentos 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 atribuye a William Kahan . En esta aplicación, la detección de ciclos en el espacio de fases 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 de fractales del conjunto de Mandelbrot, se utilizan diversas técnicas para acelerar la generación de imágenes. Una de ellas se denomina "detección de periodos" y consiste en identificar los ciclos en la órbita de un punto. Este artículo describe la técnica de " detección de periodos ". Puede encontrar otra explicación aquí . Para implementar esta técnica, es necesario implementar algoritmos de detección de ciclos.

Referencias

1 2 Joux, Antoine (2009), "7. Algoritmos basados en cumpleaños para funciones", Criptoanálisis algorítmico , CRC Press, pág. 223, ISBN 978-1-420-07003-3.
1 2 Joux (2009 , p. 224) .
1 2 Knuth, Donald E. (1969), El arte de la programación informática, vol. II: Algoritmos seminuméricos , Addison-Wesley, pág. 7, ejercicios 6 y 7
↑ El Manual de Criptografía Aplicada, de Alfred J. Menezes, Paul C. van Oorschot y Scott A. Vanstone, pág. 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 ciclos de Floyd, págs. 225–226.
1 2 3 4 Brent, RP (1980), "Un algoritmo de factorización de Monte Carlo mejorado" (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.
1 2 Warren, Henry S. Jr. "Detectores de bucle de Floyd y Gosper" . Hacker's Delight . Archivado del original el 14 de abril de 2016. Recuperado el 8 de febrero de 2017 .
1 2 "Hakmem -- Flujos y funciones iteradas -- Borrador, aún no revisado" . Archivado del original el 18 de marzo de 2020. Recuperado el 2 de mayo de 2024 .
1 2 3 4 Nivasch, Gabriel (2004), "Detección de ciclos mediante 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 .
1 2 Teske, Edlyn (1998), "Un algoritmo eficiente en espacio para el cálculo de la estructura de grupos", Mathematics of Computation , 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 paralela de colisiones con aplicaciones criptoanalíticas" , Journal of Cryptology , 12 (1): 1– 28, doi : 10.1007/PL00003816 , S2CID 5091635 .
1 2 Quisquater, J.-J.; Delescaille, J.-P. (1990), "¿Qué tan fácil es la búsqueda de colisiones? Aplicación a DES", Avances en criptología – EUROCRYPT '89, Taller sobre la teoría y aplicación de técnicas criptográficas , Lecture Notes in Computer Science, vol. 434, Springer-Verlag, pp. 429–434 , doi : 10.1007/3-540-46885-4_43 , ISBN 978-3-540-53433-4.
1 2 Fich, Faith Ellen (1981), "Límites inferiores para el problema de detección de ciclos", Actas del 13.º Simposio ACM sobre Teoría de la Computación , Stoc '81, págs. 96–105 , doi : 10.1145/800076.802462 , ISBN 978-1-4503-7392-0, S2CID 119742106 .
↑ Allender, Eric W. ; Klawe, Maria M. (1985), "Límites inferiores mejorados para el problema de detección de ciclos", Theoretical Computer Science , 36 ( 2– 3): 231– 237, doi : 10.1016/0304-3975(85)90044-1 .
↑ Pollard, JM (1975), "Un método de Monte Carlo para la factorización", 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 , 32 (143), American Mathematical Society: 918–924 , doi : 10.2307/2006496 , JSTOR 2006496 , S2CID 235457090 .
1 2 Kaliski, Burton S. Jr.; Rivest, Ronald L. ; Sherman, Alan T. (1988), "¿Es el Estándar de Cifrado de Datos un grupo? (Resultados de experimentos cíclicos 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 eficiente de bucles en Prolog mediante 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), "Aserciones para el análisis dinámico de la forma de estructuras de datos de lista", AADEBUG '97, Actas del Tercer Taller Internacional sobre Depuración Automática , Artículos Electrónicos de Linköping en Ciencias de la Computación e Información, Universidad de Linköping , págs . 37–42 .

Enlaces externos

Gabriel Nivasch, El problema de la detección de ciclos y el algoritmo de pila
Tortuga y liebre , repositorio de patrones de Portland
Algoritmo de detección de ciclos de Floyd (La tortuga y la liebre)
Algoritmo de detección de ciclos de Brent (La tortuga teletransportadora)

[Joux-1] 1 2 Joux, Antoine (2009), "7. Algoritmos basados en cumpleaños para funciones", Criptoanálisis algorítmico , CRC Press, pág. 223, ISBN 978-1-420-07003-3.

[j224-2] 1 2 Joux (2009 , p. 224) .

[knuth-3] 1 2 Knuth, Donald E. (1969), El arte de la programación informática, vol. II: Algoritmos seminuméricos , Addison-Wesley, pág. 7, ejercicios 6 y 7

[4] El Manual de Criptografía Aplicada, de Alfred J. Menezes, Paul C. van Oorschot y Scott A. Vanstone, pág. 125 , describe este algoritmo y otros.

[5] Floyd, RW (1967), "Algoritmos no deterministas", J. ACM , 14 (4): 636– 644, doi : 10.1145/321420.321422 , S2CID 1990464

[6] 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

[7] Joux (2009) , Sección 7.1.1, Algoritmo de búsqueda de ciclos de Floyd, págs. 225–226.

[brent-8] 1 2 3 4 Brent, RP (1980), "Un algoritmo de factorización de Monte Carlo mejorado" (PDF) , BIT Numerical Mathematics , 20 (2): 176– 184, doi : 10.1007/BF01933190 , S2CID 17181286 .

[9] Joux (2009) , Sección 7.1.2, Algoritmo de búsqueda de ciclos de Brent, págs. 226–227.

[gosper-impl-10] 1 2 Warren, Henry S. Jr. "Detectores de bucle de Floyd y Gosper" . Hacker's Delight . Archivado del original el 14 de abril de 2016. Recuperado el 8 de febrero de 2017 .

[hakmem-132-11] 1 2 "Hakmem -- Flujos y funciones iteradas -- Borrador, aún no revisado" . Archivado del original el 18 de marzo de 2020. Recuperado el 2 de mayo de 2024 .

[nivasch-12] 1 2 3 4 Nivasch, Gabriel (2004), "Detección de ciclos mediante una pila", Information Processing Letters , 90 (3): 135– 140, doi : 10.1016/j.ipl.2004.01.016.

[13] 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 .

[teske-14] 1 2 Teske, Edlyn (1998), "Un algoritmo eficiente en espacio para el cálculo de la estructura de grupos", Mathematics of Computation , 67 (224): 1637– 1663, Bibcode : 1998MaCom..67.1637T , doi : 10.1090/S0025-5718-98-00968-5 .

[15] 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 .

[16] van Oorschot, Paul C.; Wiener, Michael J. (1999), "Búsqueda paralela de colisiones con aplicaciones criptoanalíticas" , Journal of Cryptology , 12 (1): 1– 28, doi : 10.1007/PL00003816 , S2CID 5091635 .

[qd-17] 1 2 Quisquater, J.-J.; Delescaille, J.-P. (1990), "¿Qué tan fácil es la búsqueda de colisiones? Aplicación a DES", Avances en criptología – EUROCRYPT '89, Taller sobre la teoría y aplicación de técnicas criptográficas , Lecture Notes in Computer Science, vol. 434, Springer-Verlag, pp. 429–434 , doi : 10.1007/3-540-46885-4_43 , ISBN 978-3-540-53433-4.

[fich-18] 1 2 Fich, Faith Ellen (1981), "Límites inferiores para el problema de detección de ciclos", Actas del 13.º Simposio ACM sobre Teoría de la Computación , Stoc '81, págs. 96–105 , doi : 10.1145/800076.802462 , ISBN 978-1-4503-7392-0, S2CID 119742106 .

[19] Allender, Eric W. ; Klawe, Maria M. (1985), "Límites inferiores mejorados para el problema de detección de ciclos", Theoretical Computer Science , 36 ( 2– 3): 231– 237, doi : 10.1016/0304-3975(85)90044-1 .

[20] Pollard, JM (1975), "Un método de Monte Carlo para la factorización", BIT , 15 (3): 331–334 , doi : 10.1007/BF01933667 , S2CID 122775546 .

[21] Pollard, JM (1978), "Métodos de Monte Carlo para el cálculo de índices $(mod$ $p$ )", Mathematics of Computation , 32 (143), American Mathematical Society: 918–924 , doi : 10.2307/2006496 , JSTOR 2006496 , S2CID 235457090 .

[krs-22] 1 2 Kaliski, Burton S. Jr.; Rivest, Ronald L. ; Sherman, Alan T. (1988), "¿Es el Estándar de Cifrado de Datos un grupo? (Resultados de experimentos cíclicos en DES)", Journal of Cryptology , 1 (1): 3– 36, doi : 10.1007/BF00206323 , S2CID 17224075 .

[23] Joux (2009) , Sección 7.5, Colisiones en funciones hash, págs. 242–245.

[24] Van Gelder, Allen (1987), "Detección eficiente de bucles en Prolog mediante 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.

[25] Auguston, Mikhail; Hon, Miu Har (1997), "Aserciones para el análisis dinámico de la forma de estructuras de datos de lista", AADEBUG '97, Actas del Tercer Taller Internacional sobre Depuración Automática , Artículos Electrónicos de Linköping en Ciencias de la Computación e Información, Universidad de Linköping , págs . 37–42 .

[ 1 ]

letra

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]