LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

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 asigne un conjunto finito S a sí mismo, y cualquier valor inicial x ₀ en S , la secuencia de valores de función iterados

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

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 , repitiendo 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 ₀ .

Se conocen varios algoritmos para encontrar ciclos rápidamente y con poca memoria. La tortuga de Floyd y el algoritmo de liebre mueven dos punteros a diferentes velocidades a través de la secuencia de valores hasta que ambos apuntan 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 varias evaluaciones de función que son proporcionales 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 los generadores de números pseudoaleatorios y las funciones criptográficas hash , los algoritmos de la teoría de números computacionales , la detección de bucles infinitos en los programas informáticos y las configuraciones periódicas en autómatas celulares , y el análisis automatizado de formas de las estructuras de datos de listas vinculadas .

Ejemplo [ editar ]

Una función desde y hacia el conjunto {0,1,2,3,4,5,6,7,7,8} y el gráfico funcional correspondiente

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 uno comienza desde x ₀ = 2 y 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 [ editar ]

Vamos S cualquier conjunto finito, f ser cualquier función de S a sí mismo, y x ₀ ser cualquier elemento de S . Para cualquier i > 0 , sea x _i = f ( x _{i - 1} ) . Sea μel índice más pequeño de modo que el valor x _μreaparezca infinitamente a menudo dentro de la secuencia de valores x _i , y sea λ (la longitud del bucle) el entero positivo más pequeño, de modo que x _μ = x _λ +μ. El problema de detección de ciclos es la tarea de encontrarλy μ. ^[1]

Uno puede ver el mismo problema de forma gráfica , construyendo una gráfica funcional (es decir, una gráfica dirigida en la que cada vértice tiene un solo borde de salida) cuyos vértices son los elementos de S y los bordes de los cuales se asigna un elemento a El valor de la función correspondiente, como se muestra en la figura. El conjunto de vértices accesibles desde el vértice inicial x ₀ forman un subgrafo con una forma que se parece a la letra griega rho ( ρ ): una trayectoria de longitud μ desde x ₀ a un ciclo de λ vértices. ^[2]

Representación por ordenador [ editar ]

En general, f no se especificará como una tabla de valores, como se muestra en la figura anterior. Más bien, a un algoritmo de detección de ciclos se le puede dar acceso a la secuencia de valores x _i , oa una subrutina para calcular f . La tarea es encontrar λ y μ al examinar la menor cantidad de valores de la secuencia o realizar la menor cantidad posible de llamadas a subrutinas. Por lo general, también es importante la complejidad de espacio de un algoritmo para el problema de detección de ciclos: deseamos resolver el problema usando una cantidad de memoria significativamente menor de la que se necesitaría para almacenar toda la secuencia.

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 enteros modulo, 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 que los algoritmos de detección de ciclos se utilicen con un conocimiento tan limitado, se pueden diseñar en función de las siguientes capacidades. Inicialmente, se supone que el algoritmo tiene en su memoria un objeto que representa un puntero al valor inicial x ₀. En cualquier paso, puede realizar una de tres acciones: puede copiar cualquier puntero que tenga a otro objeto en la memoria, puede aplicar f y 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 comprobando si la diferencia entre dos valores almacenados tiene un divisor común más grande no trivial con el número a ser factorizado. ^[2] En este contexto, por analogía a la máquina de puntero. El modelo de cálculo, un algoritmo que solo usa la copia de puntero, el avance dentro de la secuencia y las pruebas de igualdad se pueden llamar algoritmos de puntero.

Algoritmos [ editar ]

Si la entrada se proporciona como una subrutina para calcular f , el problema de detección de ciclo se puede resolver de manera trivial utilizando solo las aplicaciones de 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 prueba si cada valor posterior ya ha sido almacenado. Sin embargo, la complejidad de espacio 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 resultaría en un tiempo cuadrático en general. Por lo tanto, la investigación en esta área se ha concentrado en dos objetivos: usar menos espacio que este algoritmo ingenuo y encontrar algoritmos de puntero que usen menos pruebas de igualdad.

La tortuga y la liebre de Floyd [ editar ]

El algoritmo de detección del ciclo "tortuga y liebre" de Floyd, aplicado a la secuencia 2, 0, 6, 3, 1, 6, 3, 1, ...

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 "la tortuga y el algoritmo de liebre", aludiendo a la fábula de Esopo de La tortuga y la liebre .

El algoritmo lleva el nombre de Robert W. Floyd , quien fue acreditado con su invento por Donald Knuth . ^[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 citación, es la primera aparición conocida impresa, y por lo tanto puede ser un teorema popular , no atribuible a un solo individuo. ^[6]

La idea clave en el 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 encuentra y μ es el índice del primer elemento del ciclo . Sobre esta base, 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 tan lejos del inicio de la secuencia como el otro, para encontrar un período ν de una repetición que sea un múltiplo de λ . Una vez que se encuentra ν , el algoritmo vuelve a trazar la secuencia desde su inicio para encontrar el primer valor repetido x _μ en la secuencia, utilizando el hecho de que λ se divide ν y, por lo tanto, que 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 _μ .

El algoritmo mantiene así 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 esta idea puede implementarse 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 punto, 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 
    # 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 (reajustar a x0) moviéndose hacia el círculo, 
    # se intersecará 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 μ.

    # Encuentra la posición μ de la primera repetición.    
    mu  =  0 
    tortuga  =  x0 
    mientras que  tortuga  ! =  liebre : 
        tortuga  =  f ( tortuga ) 
        liebre  =  f ( liebre )    # La liebre y la tortuga se mueven a la misma velocidad 
        mu  + =  1
 
    # Encuentre la duración del ciclo más corto a partir de x_μ 
    # La liebre se mueve paso a paso mientras la tortuga está inmóvil. 
    # lam se incrementa hasta que se encuentra λ. 
    lam  =  1 
    liebre  =  f ( tortuga ) 
    mientras que  tortuga  ! =  liebre : 
        liebre  =  f ( liebre ) 
        lam  + =  1
 
    regresa  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 espacio de almacenamiento O (1) . ^[7]

El algoritmo de Brent [ editar ]

Richard P. Brent describió un algoritmo de detección de ciclo alternativo que, como el algoritmo de tortuga y 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 ⁱ que sea mayor que λ y μ . Para i = 0, 1, 2, ... , el algoritmo compara x _2 ⁱ −1con 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 tortuga y liebre: encuentra la longitud correcta λdel ciclo directamente, en lugar de tener que buscarlo en una etapa posterior, y sus pasos incluyen 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: busca potencias sucesivas de dos 
    potencias  =  lam  =  1 
    tortuga  =  x0 
    hare  =  f ( x0 )   # f (x0) es el elemento / nodo junto a x0. 
    while  tortoise  ! =  hare : 
        if  power  ==  lam :   # ¿tiempo para comenzar una nueva potencia de dos? 
            tortuga  =  poder de liebre 
            * = 2 lam = 0 liebre = f ( liebre  
              
          ) 
        lam  + =  1

    # Encuentre la posición de la primera repetición de 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 es ahora λ.

    # A continuación, la liebre y la tortuga se mueven a la misma velocidad hasta que coinciden 
    mu  =  0 
    mientras que la  tortuga  ! =  Hare : 
        tortuga  =  f ( tortuga ) 
        hare  =  f ( hare ) 
        mu  + =  1
 
    regresa  lam ,  mu

Al igual que el algoritmo de tortuga y liebre, este es un algoritmo de puntero que utiliza pruebas 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 para el 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 de Pollard rho en alrededor de un 24%. También realiza un análisis de casos 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 es la potencia de dos en sí, sino un múltiplo aleatorio de la potencia de dos. Aunque su principal aplicación fue en algoritmos de factorización de enteros, Brent también analiza las aplicaciones en la prueba de generadores de números pseudoaleatorios. ^[8]

Algoritmo de Gosper [ editar ]

El algoritmo de RW Gosper ^[10] [11] encuentra el período pero no el punto de inicio del primer ciclo. Su característica principal es que nunca realiza copias de seguridad para volver a evaluar la función del generador, y es económico tanto en tiempo como en espacio. Por ejemplo, si se sabe a priori que la función del generador tiene un período de 2 ^32, entonces 33 palabras son suficientes.

Intercambios de tiempo-espacio [ editar ]

Varios autores han estudiado técnicas para la detección de ciclos que usan 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 comprueban si cada nuevo valor es igual a uno de los valores calculados previamente. Para hacerlo rápidamente, normalmente utilizan una tabla hash o una estructura de datos similar para almacenar los valores previamente calculados, 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] analizamos 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 que R 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 ciclo puede usar varias evaluaciones de función 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 que solo requiere en el peor de los casos$${\ displaystyle (\ lambda + \ mu) (1 + cM ^ {- 1/2})}Evaluación de funciones, para algunas constantes c , que se muestran óptimas. 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 cuando se hayan almacenado demasiados valores.
• Varios autores han descrito métodos de puntos 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.) Basado en sus posiciones. Por ejemplo, valores iguales a cero módulo algún valor d podría ser almacenado. ^[16] [17] Más simplemente, 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 permanezca aleatoria.
• Nivasch ^[12] describe un algoritmo que no usa una cantidad fija de memoria, pero para la cual la cantidad esperada de memoria utilizada (suponiendo que la función de entrada es aleatoria) es logarítmica en la longitud de la secuencia. Un elemento se almacena en la tabla de memoria, con esta técnica, cuando ningún elemento posterior tiene un valor más pequeño. Como muestra Nivasch, los elementos con esta técnica pueden mantenerse utilizando 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. La ejecución del mismo algoritmo con varias pilas, utilizando permutaciones aleatorias de los valores para reordenar los valores dentro de cada pila, permite un intercambio 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 más pequeño.

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

Aplicaciones [ editar ]

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. 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 lineal congruente de esta manera; Su período resultó ser significativamente más pequeño 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 de teoría de números se basan en la detección de ciclos, incluido el algoritmo rho de Pollardpara la factorización de enteros ^[20] y su algoritmo de canguro relacionado para el problema del logaritmo discreto . ^[21]
• En criptográficos aplicaciones, la capacidad de encontrar dos valores distintos x _{μ - 1} y x _{λ + μ - 1} mapeada por alguna función criptográfica ƒ para el mismo valor de 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 usan algoritmos de detección de ciclos para atacar a DES. La técnica también se puede utilizar para encontrar una colisión en unFunció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 simulaciones de autómatas celulares se pueden encontrar aplicando algoritmos de detección de ciclos a la secuencia de estados de autómatas. ^[12]
• El análisis de formas de las estructuras de datos de listas vinculadas es una técnica para verificar la corrección 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 pueden ser detectados por estos algoritmos. ^[25] En Common Lisp , la impresora de expresiones S , bajo el control de la *print-circle*variable, detecta una estructura de lista circular y la imprime de forma compacta.
• Teske ^[14] describe aplicaciones en la teoría de grupos computacionales : 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 para 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 se puede usar para determinar si el sistema es periódico dentro de la precisión de la simulación.