Введение

Алгоритмическая проблема итерированных функций.

В информатике, обнаружение цикла или поиск цикла — это алгоритмическая проблема поиска цикла в последовательности значений, полученных в результате последовательного применения функции. Для любой функции f, отображающей конечное множество S само на себя, и любого начального значения x0 из S, последовательность значений, полученных в результате итераций функции,

в конечном итоге должна повторить какое-либо значение: должна существовать пара различных индексов i и j, таких что xi = xj. Как только это происходит, последовательность начинает повторяться периодически, воспроизводя одну и ту же последовательность значений от xi до xj − 1. Обнаружение цикла — это задача нахождения i и j, заданных функцией f и начальным значением x0. Существует несколько алгоритмов, позволяющих быстро находить циклы с небольшим использованием памяти. Алгоритм «черепаха и заяц» Роберта Флойда перемещает два указателя по последовательности значений с разной скоростью, пока они не укажут на одно и то же значение. Альтернативно, алгоритм Брента основан на идее экспоненциального поиска. Как алгоритм Флойда, так и алгоритм Брента используют лишь постоянное количество ячеек памяти и выполняют количество вычислений функции, пропорциональное расстоянию от начала последовательности до первого повторения. Другие алгоритмы используют больший объем памяти для уменьшения количества вычислений функции. Области применения обнаружения циклов включают тестирование качества генераторов псевдослучайных чисел и криптографических хеш-функций, алгоритмов вычислительной теории чисел, обнаружение бесконечных циклов в компьютерных программах и периодических конфигураций в клеточных автоматах, автоматизированный анализ структуры данных, реализованных в виде связных списков, и обнаружение взаимоблокировок при управлении транзакциями в СУБД.

Пример

На рисунке показана функция f, которая отображает множество S = {0, 1, 2, 3, 4, 5, 6, 7, 8} на само себя. Если начать с x₀ = 2 и неоднократно применять f, то можно увидеть последовательность значений 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1. Цикл в этой последовательности значений — 6, 3, 1.

Определения

Пусть S — любое конечное множество, f — любая функция из S в себя, а x0 — любой элемент S. Для любого i > 0, пусть xi = f(xi − 1). Пусть μ — наименьший индекс, при котором значение xμ появляется бесконечно часто в последовательности значений xi, и пусть λ (длина цикла) — наименьшее положительное целое число, такое что xμ = xλ + μ. Задача обнаружения цикла — это задача поиска λ и μ. Эту же задачу можно рассмотреть с точки зрения теории графов, построив функциональный граф (то есть ориентированный граф, в котором у каждой вершины есть одно исходящее ребро), вершины которого являются элементами S, а ребра отображают элемент в соответствующее значение функции, как показано на рисунке. Множество вершин, достижимых из начальной вершины x0, образует подграф, имеющий форму, напоминающую греческую букву ро (ρ): путь длиной μ от x0 к циклу из λ вершин.

Приложения

Обнаружение циклов используется во многих приложениях. Определение длины цикла генератора псевдослучайных чисел является одной из мер его надежности. Это приложение приводится Кнутом при описании метода Флойда и его связанного алгоритма «кенгуру» для задачи о дискретном логарифме. В криптографических приложениях возможность найти два различных значения xμ−1 и xλ+μ−1, отображаемые некоторой криптографической функцией ƒ в одно и то же значение xμ, может указывать на слабость ƒ. Например, Quisquater и Delescaille также используют алгоритмы обнаружения циклов для атаки на DES. Этот метод также может быть использован для поиска коллизии в криптографической хеш-функции. Обнаружение циклов может быть полезно для выявления бесконечных циклов в определенных типах компьютерных программ. Периодические конфигурации в симуляциях клеточных автоматов можно обнаружить, применяя алгоритмы обнаружения циклов к последовательности состояний автомата. В Common Lisp принтер S-выражений, управляемый переменной *print circle*, обнаруживает циклическую структуру списков и печатает ее в компактном виде. Теске описывает применение в вычислительной теории групп: определение структуры абелевой группы по заданному множеству ее образующих. Криптографические алгоритмы Калиски и др. также можно рассматривать как попытку определить структуру неизвестной группы. Кратко упоминается применение в компьютерном моделировании небесной механики, которое автор приписывает Уильяму Кахану. В этом применении обнаружение циклов в фазовом пространстве орбитальной системы может использоваться для определения, является ли система периодической с точностью, допустимой для симуляции. При генерации фрактала множества Мандельброта используются некоторые методы повышения производительности для ускорения генерации изображения. Один из них называется «проверкой периодов», который заключается в поиске циклов на орбите точки. В этой статье описывается метод «проверки периодов». Здесь можно найти другое объяснение. Для реализации этой техники необходимо реализовать некоторые алгоритмы обнаружения циклов.