Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья о повторяющихся функциях. Для другого использования см. Обнаружение цикла (теория графов) .

В информатике , определение цикла или цикл обнаружение является алгоритмической задачей нахождения цикла в последовательности из повторных функциональных значений.

Для любой функции f, которая отображает конечное множество S в себя и любое начальное значение x 0 в S , последовательность повторяющихся значений функции

в конечном итоге должен использовать одно и то же значение дважды: должна быть какая-то пара различных индексов i и j, такая, что x i = x j . Как только это произойдет, последовательность должна продолжаться периодически , повторяя ту же последовательность значений от x i до x j - 1 . Обнаружение цикла - это проблема нахождения i и j при заданных f и x 0 .

Известно несколько алгоритмов быстрого нахождения циклов с малым объемом памяти. Алгоритм Роберта Флойда с черепахой и зайцем перемещает два указателя с разной скоростью через последовательность значений, пока они оба не укажут на равные значения. В качестве альтернативы алгоритм Брента основан на идее экспоненциального поиска . И алгоритмы Флойда, и Брента используют только постоянное количество ячеек памяти и выполняют ряд вычислений функций, которые пропорциональны расстоянию от начала последовательности до первого повторения. Некоторые другие алгоритмы жертвуют большим объемом памяти за меньшее количество вычислений функций.

Приложения обнаружения цикла включают проверки качества псевдослучайных чисел генераторов и криптографических хэш - функции , вычислительных теорию чисел алгоритмов обнаружения бесконечных циклов в компьютерных программах и периодических конфигурации в клеточных автоматах , автоматизированный анализ формы из связанных списка структур данных, выявление тупиков для управление транзакциями в СУБД .

Пример [ править ]

Функция из и в набор {0,1,2,3,4,5,6,7,8} и соответствующий функциональный граф

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

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Цикл в этой последовательности значений - 6, 3, 1 .

Определения [ править ]

Пусть S произвольное конечное множество, F любая функция от S к себе, а х 0 любой элемент из S . Для любого i > 0 положим x i = f ( x i - 1 ) . Пусть μ - наименьший индекс такой, что значение x μ повторяется бесконечно часто в последовательности значений x i , и пусть λ (длина цикла) будет наименьшим положительным целым числом такое, что x μ = x λ +μ . Проблема обнаружения цикла - это задача нахожденияλи μ. [1]

Можно рассмотреть ту же проблему теоретически графически , построив функциональный граф (то есть ориентированный граф, в котором каждая вершина имеет единственное исходящее ребро), вершины которого являются элементами S, а ребра которого отображают элемент в соответствующее значение функции, как показано на рисунке. Множество вершин , достижимая из исходной вершины х 0 формы подграфа с формой , напоминающой греческая буква Rho ( р ): путь длиной ц от й 0 к циклу из Й вершин. [2]

Компьютерное представление [ править ]

Обычно f не указывается в виде таблицы значений, как это показано на рисунке выше. Напротив, алгоритму обнаружения цикла может быть предоставлен доступ либо к последовательности значений x i , либо к подпрограмме для вычисления f . Задача состоит в том, чтобы найти λ и μ , исследуя как можно меньше значений из последовательности или выполняя как можно меньше вызовов подпрограмм. Как правило, также важна пространственная сложность алгоритма для задачи обнаружения цикла: мы хотим решить проблему, используя объем памяти, значительно меньший, чем потребуется для хранения всей последовательности.

В некоторых приложениях, и в частности в алгоритме Ро Полларда для целочисленной факторизации , алгоритм имеет гораздо более ограниченный доступ к S и к f . Например, в алгоритме ро Полларда S представляет собой набор целых чисел по модулю неизвестного простого множителя числа, которое нужно разложить на множители, поэтому даже размер S неизвестен алгоритму. Чтобы позволить использовать алгоритмы обнаружения цикла с такими ограниченными знаниями, они могут быть разработаны на основе следующих возможностей. Первоначально предполагается, что алгоритм имеет в своей памяти объект, представляющий указатель на начальное значение x 0. На любом этапе он может выполнить одно из трех действий: он может скопировать любой указатель, который у него есть, на другой объект в памяти, он может применить f и заменить любой из своих указателей указателем на следующий объект в последовательности, или он может применить подпрограмма для определения того, представляют ли два из ее указателя равные значения в последовательности. Действие проверки равенства может включать в себя некоторые нетривиальные вычисления: например, в алгоритме ро Полларда оно реализуется путем проверки того, имеет ли разница между двумя сохраненными значениями нетривиальный наибольший общий делитель с числом, которое нужно факторизовать. [2] В этом контексте, по аналогии с указательной машиной Модель вычислений, алгоритм, который использует только копирование указателя, продвижение в последовательности и проверки равенства, может быть назван алгоритмом указателя.

Алгоритмы [ править ]

Если ввод задан как подпрограмма для вычисления f , проблема обнаружения цикла может быть тривиально решена с использованием только приложений функции λ + μ , просто путем вычисления последовательности значений x i и использования структуры данных, такой как хеш-таблица, для их хранения. values ​​и проверьте, было ли уже сохранено каждое последующее значение. Однако пространственная сложность этого алгоритма пропорциональна λ + μ , что неоправданно велико. Кроме того, чтобы реализовать этот метод как алгоритм указателяпотребует применения теста на равенство к каждой паре значений, что приведет к квадратичному времени в целом. Таким образом, исследования в этой области сосредоточены на двух целях: использование меньшего пространства, чем этот наивный алгоритм, и поиск алгоритмов указателей, которые используют меньше тестов на равенство.

Черепаха и заяц Флойда [ править ]

Алгоритм обнаружения цикла «черепаха и заяц» Флойда, примененный к последовательностям 2, 0, 6, 3, 1, 6, 3, 1, ...

Алгоритм поиска цикла Флойда - это алгоритм указателя, который использует только два указателя, которые перемещаются по последовательности с разной скоростью. Это также называется «черепаху и зайца алгоритм», имея в виду Эзопа басни Черепаха и Заяц .

Алгоритм назван в честь Роберта У. Флойда , изобретателем которого является Дональд Кнут . [3] [4] Однако алгоритм не появляется в опубликованной работе Флойда, и это может быть неправильная атрибуция: Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированном графе в статье 1967 года [5], но в этой статье нет описать задачу поиска циклов в функциональных графах, которая является предметом данной статьи. Фактически, заявление Кнута (1969 г.), приписывающее его Флойду, без цитирования, является первым известным появлением в печати, и, таким образом, это может быть народная теорема , не относящаяся к одному человеку. [6]

Ключевое понимание алгоритма заключается в следующем. Если есть цикл, то для любых целых чисел я ≥ ц и к ≥ 0 , х я = х я + kλ , где λ является длиной петли должны быть найдены и ц является индексом первого элемента цикла . На основании этого можно показать, что i = kλ ≥ μ для некоторого k тогда и только тогда, когда x i = x 2 i. Таким образом, алгоритму нужно только проверить повторяющиеся значения этой специальной формы, одно в два раза дальше от начала последовательности, чем другое, чтобы найти период ν повторения, кратный λ . Как только ν найдено, алгоритм повторяет последовательность от ее начала, чтобы найти первое повторяющееся значение x μ в последовательности, используя тот факт, что λ делит ν и, следовательно, x μ = x μ + v . Наконец, как только значение μ известно, легко найти длину λкратчайшего повторяющегося цикла путем поиска первой позиции μ + λ, для которой x μ + λ = x μ .

Таким образом, алгоритм поддерживает два указателя на заданную последовательность: один (черепаха) в точке x i , а другой (заяц) в точке x 2 i . На каждом шаге алгоритма он увеличивает i на единицу, перемещая черепаху на один шаг вперед, а зайца - на два шага вперед в последовательности, а затем сравнивает значения последовательности на этих двух указателях. Наименьшее значение i > 0, для которого черепаха и заяц указывают на равные значения, является искомым значением ν .

Следующий код Python показывает, как эту идею можно реализовать в виде алгоритма.

def  floyd ( f ,  x0 ):  # Основная фаза алгоритма: поиск повторения x_i = x_2i.  # Заяц движется вдвое быстрее черепахи и  # расстояние между ними увеличивается на 1 с каждым шагом.  # В конце концов они оба окажутся внутри цикла, а затем  # в какой-то момент расстояние между ними будет  # делиться на период λ.  черепаха  =  f ( x0 )  # f (x0) - элемент / узел рядом с x0.  заяц  =  f ( f ( x0 ))  а  черепаха  ! =  заяц :  черепаха =  f ( черепаха )  заяц  =  f ( f ( заяц ))  # В этот момент положение черепахи ν, которое также  #  равно расстоянию между зайцем и черепахой, #  делится на период λ. Таким образом, заяц, перемещающийся по кругу по одному шагу за раз, # и черепаха (сброшен на x0), двигаясь к кругу,  # пересекутся в начале круга. Поскольку  # расстояние между ними постоянно на 2ν, кратном λ,  # они согласятся, как только черепаха достигнет индекса μ. # Найдите позицию μ первого повторения.  mu  =  0  tortoise  =  x0  while  tortoise  ! =  hare :  tortoise  =  f ( tortoise )  hare  =  f ( hare )  # Заяц и черепаха движутся с одинаковой скоростью  mu  + =  1  # Найдите длину кратчайшего цикла, начиная с x_μ  # Заяц двигается по одному шагу, пока черепаха неподвижна.  # lam увеличивается до тех пор, пока не будет найдено λ.  lam  =  1  hare  =  f ( черепаха ) в  то время как  черепаха  ! =  hare :  hare  =  f ( hare )  lam  + =  1  вернуть  лам ,  му

Этот код обращается к последовательности только путем сохранения и копирования указателей, оценок функций и тестов на равенство; следовательно, он квалифицируется как алгоритм указателя. Алгоритм использует O ( λ + μ ) операций этих типов и O (1) дискового пространства. [7]

Алгоритм Брента [ править ]

Ричард П. Брент описал альтернативный алгоритм определения цикла, который, как и алгоритм черепахи и зайца, требует только двух указателей на последовательность. [8] Однако он основан на другом принципе: поиск наименьшей степени двойки 2 i, которая больше, чем λ и μ . Для i = 0, 1, 2, ... алгоритм сравнивает x 2 i -1 с каждым последующим значением последовательности до следующей степени двойки и останавливается, когда находит совпадение. Он имеет два преимущества по сравнению с алгоритмом черепахи и зайца: он находит правильную длину λцикла напрямую, вместо того, чтобы искать его на следующем этапе, и его шаги включают только одну оценку f, а не три. [9]

В следующем коде Python более подробно показано, как работает этот метод.

def  brent ( f ,  x0 ):  # главная фаза: поиск последовательных степеней двух  power  =  lam  =  1  tortoise  =  x0  hare  =  f ( x0 )  # f (x0) - элемент / узел рядом с x0.  while  tortoise  ! =  hare :  if  power  ==  lam :  # пора начинать новую степень двойки?  черепаха  =  заяц  сила  * =  2  лам  =  0  заяц  =  f ( заяц)  лам  + =  1 # Найти позицию первого повторения длины λ  tortoise  =  hare  =  x0  для  i  in  range ( lam ):  # range (lam) создает список со значениями 0, 1, ..., lam-1  hare  =  f ( hare )  # Теперь расстояние между зайцем и черепахой равно λ. # Затем заяц и черепаха двигаются с одинаковой скоростью, пока не согласятся, что  mu  =  0,  а  tortoise  ! =  Hare :  tortoise  =  f ( tortoise )  hare  =  f ( hare )  mu  + =  1  вернуть  лам ,  му

Подобно алгоритму черепахи и зайца, это алгоритм указателя, который использует O ( λ + μ ) тестов и оценок функций и O (1) дискового пространства. Нетрудно показать, что количество вычислений функций никогда не может быть больше, чем для алгоритма Флойда. Брент утверждает, что в среднем его алгоритм поиска цикла работает примерно на 36% быстрее, чем алгоритм Флойда, и что он ускоряет алгоритм Полларда ро примерно на 24%. Он также проводит анализ среднего случаядля рандомизированной версии алгоритма, в которой последовательность индексов, отслеживаемых более медленным из двух указателей, является не степенью двойки, а скорее рандомизированным кратным степени двойки. Хотя его основное предполагаемое применение было в алгоритмах факторизации целых чисел, Брент также обсуждает приложения для тестирования генераторов псевдослучайных чисел. [8]

Алгоритм Госпера [ править ]

Алгоритм RW Госпера [10] [11] находит период , а также нижнюю и верхнюю границы начальной точки и первого цикла. Разница между нижней и верхней границей того же порядка, что и период, например. .

Основная особенность алгоритма Госпера заключается в том, что он никогда не выполняет резервное копирование для переоценки функции генератора и экономичен как в пространстве, так и во времени. Это можно примерно описать как параллельную версию алгоритма Брента. В то время как алгоритм Брента постепенно увеличивает разрыв между черепахой и зайцем, алгоритм Госпера использует несколько черепах (сохраняются несколько предыдущих значений), которые расположены примерно по экспоненте. Согласно примечанию в элементе 132 HAKMEM , этот алгоритм будет обнаруживать повторение до третьего появления любого значения, например. цикл будет повторяться не более двух раз. В этом примечании также говорится, что достаточно сохранить предыдущие значения; однако предоставленная реализация [10] хранитзначения. Например: значения функции представляют собой 32-битные целые числа, и априори известно, что вторая итерация цикла заканчивается после не более 2 32 вычислений функции с начала, т.е. . Тогда достаточно сохранить 33 32-битных целых числа.

После -й оценки функции генератора алгоритм сравнивает сгенерированное значение с предыдущими значениями; наблюдайте, что идет по крайней мере и максимум . Следовательно, временная сложность этого алгоритма составляет . Поскольку он хранит значения, его пространственная сложность составляет . Это при обычном предположении, присутствующем в этой статье, что размер значений функции постоянен. Без этого предположения сложность пространства состоит в том, что нам нужны как минимум различные значения, и, следовательно, размер каждого значения равен .

Компромиссы между пространством и временем [ править ]

Ряд авторов изучили методы обнаружения циклов, которые используют больше памяти, чем методы Флойда и Брента, но обнаруживают циклы быстрее. Как правило, эти методы хранят несколько ранее вычисленных значений последовательности и проверяют, равно ли каждое новое значение одному из ранее вычисленных значений. Чтобы сделать это быстро, они обычно используют хеш-таблицу или аналогичную структуру данных для хранения ранее вычисленных значений и, следовательно, не являются алгоритмами указателя: в частности, они обычно не могут быть применены к алгоритму rho Полларда. Эти методы различаются тем, как они определяют, какие значения хранить. Следуя Нивашу [12], мы кратко рассмотрим эти методы.

  • Брент [8] уже описывает варианты своей техники, в которых индексы сохраненных значений последовательности являются степенями числа R, отличного от двух. Выбирая R как число, близкое к единице, и сохраняя значения последовательности в индексах, которые близки к последовательности последовательных степеней R , алгоритм обнаружения цикла может использовать ряд оценок функций, которые находятся в пределах произвольно малого коэффициента оптимального λ + μ . [13] [14]
  • Седжвик, Шимански и Яо [15] предлагают метод, использующий M ячеек памяти и требующий в худшем случае только вычислений функций для некоторой константы c , которая, как они показывают, является оптимальной. Этот метод включает поддержание числового параметра d , сохранение в таблице только тех позиций в последовательности, которые кратны d , а также очистку таблицы и удвоение d всякий раз, когда было сохранено слишком много значений.
  • Несколько авторов описали методы выделенных точек, которые сохраняют значения функций в таблице на основе критерия, включающего значения, а не (как в методе Седжевика и др.) На основе их позиций. Например, могут быть сохранены значения, равные нулю по модулю некоторого значения d . [16] [17] Проще говоря, Ниваш [12] доверяет Д. П. Вудраффу предложение хранить случайную выборку ранее увиденных значений, делая соответствующий случайный выбор на каждом шаге, чтобы выборка оставалась случайной.
  • Nivasch [12] описывает алгоритм, который не использует фиксированный объем памяти, но для которого ожидаемый объем используемой памяти (в предположении, что входная функция является случайной) является логарифмической по длине последовательности. При использовании этого метода элемент сохраняется в таблице памяти, когда ни один из последующих элементов не имеет меньшего значения. Как показывает Nivasch, элементы с этой техникой могут поддерживаться с использованием структуры данных стека., и каждое последующее значение последовательности нужно сравнивать только с вершиной стека. Алгоритм завершается, когда обнаруживается повторяющийся элемент последовательности с наименьшим значением. Выполнение того же алгоритма с несколькими стеками с использованием случайных перестановок значений для изменения порядка значений в каждом стеке позволяет найти компромисс между пространством и временем, аналогичный предыдущим алгоритмам. Однако даже версия этого алгоритма с одним стеком не является алгоритмом указателя из-за необходимости сравнения, чтобы определить, какое из двух значений меньше.

Любой алгоритм обнаружения цикла, который хранит не более M значений из входной последовательности, должен выполнять как минимум функциональные оценки. [18] [19]

Приложения [ править ]

Обнаружение цикла использовалось во многих приложениях.

  • Определение длины цикла генератора псевдослучайных чисел является одним из показателей его силы. Это приложение, которое цитирует Кнут при описании метода Флойда. [3] Брент [8] описывает результаты тестирования линейного конгруэнтного генератора таким образом; его срок оказался значительно меньше заявленного. Для более сложных генераторов последовательность значений, в которой должен быть найден цикл, может представлять не выход генератора, а его внутреннее состояние.
  • Несколько теоретико-числовых алгоритмов основаны на обнаружении цикла, в том числе алгоритм Ро Полларда для целочисленной факторизации [20] и связанный с ним алгоритм кенгуру для задачи дискретного логарифмирования . [21]
  • В криптографических приложениях возможность найти два различных значения x μ −– 1 и x λ + μ −– 1, отображаемых некоторой криптографической функцией ƒ на одно и то же значение x μ, может указывать на слабость в ƒ. Например, Quisquater и Delescaille [17] применяют алгоритмы обнаружения цикла при поиске сообщения и пары ключей стандарта шифрования данных, которые отображают это сообщение в одно и то же зашифрованное значение; Калиски , Ривест и Шерман [22] также используют алгоритмы обнаружения цикла для атаки на DES. Этот метод также может быть использован для обнаружения столкновения вкриптографическая хеш-функция . [23]
  • Обнаружение цикла может быть полезно как способ обнаружения бесконечных циклов в определенных типах компьютерных программ . [24]
  • Периодические конфигурации в моделировании клеточного автомата могут быть найдены путем применения алгоритмов обнаружения цикла к последовательности состояний автомата. [12]
  • Форма анализ из связанных списка структур данных представляет собой метод проверки правильности алгоритма с использованием этих структур. Если узел в списке неправильно указывает на более ранний узел в том же списке, структура сформирует цикл, который может быть обнаружен этими алгоритмами. [25] В Common Lisp , то S-выражение принтер, под управлением *print-circle*переменным, обнаруживает кольцевую структуру списка и печатает его компактно.
  • Теске [14] описывает приложения в вычислительной теории групп : определение структуры абелевой группы по набору ее образующих. Криптографические алгоритмы Калиски и др. [22] также можно рассматривать как попытку вывести структуру неизвестной группы.
  • Фич (1981) кратко упоминает приложение для компьютерного моделирования из небесной механики , которую она приписывает Кэхэн . В этом приложении обнаружение цикла в фазовом пространстве орбитальной системы может использоваться для определения того, является ли система периодической в ​​пределах точности моделирования. [18]
  • В генерации фракталов Мандельброта используются некоторые методы повышения производительности для ускорения генерации изображений. Один из них называется «проверка периода» и в основном заключается в нахождении циклов на точечной орбите. В этой статье описывается техника « проверки периода », и здесь вы можете найти лучшее объяснение. Чтобы реализовать это, необходимо реализовать некоторые алгоритмы обнаружения цикла.

Ссылки [ править ]

  1. ^ Жу, Антуан (2009), Алгоритмический криптоанализ , CRC Press, стр. 223, ISBN 9781420070033.
  2. ^ a b Жу (2009 , с. 224).
  3. ^ a b Кнут, Дональд Э. (1969), Искусство компьютерного программирования, т. II: получисловые алгоритмы , Addison-Wesley, p. 7, упражнения 6 и 7
  4. ^ Справочник по прикладной криптографии, Альфред Дж. Менезес, Пол К. ван Оршот, Скотт А. Ванстон, стр. 125 , описывает этот алгоритм и другие
  5. ^ Флойд, Р. (1967), "Недетерминированные Алгоритмы", J. ACM , 14 (4): 636-644, DOI : 10,1145 / 321420,321422 , S2CID 1990464 
  6. ^ Хеш-функция BLAKE, Жан-Филипп Аумассон, Вилли Мейер, Рафаэль К.-В. Фан, Лука Хензен (2015), стр. 21 , сноска 8
  7. ^ Joux (2009) , раздел 7.1.1, алгоритм поиска цикла Флойда, стр. 225–226.
  8. ^ Б с д Brent, Р. П. (1980), "Усовершенствованный алгоритм Монте - Карло факторизационную" (PDF) , BIT вычислительной математики , 20 (2): 176-184, DOI : 10.1007 / BF01933190 , S2CID 17181286  .
  9. ^ Ж (2009) , раздел 7.1.2, Брент цикл нахождения алгоритма, стр. 226-227.
  10. ^ a b «Архивная копия» . Архивировано из оригинала на 2016-04-14 . Проверено 8 февраля 2017 .CS1 maint: archived copy as title (link)
  11. ^ http://www.inwap.com/pdp10/hbaker/hakmem/flows.html
  12. ^ a b c d Ниваш, Габриэль (2004), «Обнаружение цикла с использованием стека», Письма об обработке информации , 90 (3): 135–140, DOI : 10.1016 / j.ipl.2004.01.016.
  13. ^ Шнорр, Клаус П .; Ленстра, Хендрик W. (1984), "Монте - Карло факторинг алгоритм с линейным хранения", Математика вычислениям , 43 (167): 289-311, DOI : 10,2307 / 2007414 , ЛВП : 1887/3815 , JSTOR 2007414 .
  14. ^ a b Теске, Эдлин (1998), "Экономичный алгоритм для вычисления структуры группы", Математика вычислений , 67 (224): 1637–1663, DOI : 10.1090 / S0025-5718-98-00968-5.
  15. ^ Седжвик, Роберт ; Szymanski, Thomas G .; Яо, Эндрю К.-К. (1982), "Сложность нахождения циклов в периодических функций", SIAM журнал по вычислениям , 11 (2): 376-390, DOI : 10,1137 / 0211030.
  16. ^ van Oorschot, Paul C .; Wiener, Michael J. (1999), "Параллельный поиск столкновения с криптоаналитическими приложений" , журнал криптологии , 12 (1): 1-28, DOI : 10.1007 / PL00003816 , S2CID 5091635 .
  17. ^ a b Quisquater, J.-J .; Делескайль, Ж.-П., «Насколько прост поиск столкновений? Применение в DES», Достижения в криптологии - EUROCRYPT '89, Семинар по теории и применению криптографических методов , Лекционные заметки по информатике, 434 , Springer-Verlag, . С. 429-434, DOI : 10.1007 / 3-540-46885-4_43.
  18. ^ a b Фич, Фейт Эллен (1981), "Нижние оценки для задачи обнаружения цикла", Proc. 13 ACM симпозиум по теории вычислений ., Стр 96-105, DOI : 10,1145 / 800076,802462.
  19. ^ Аллендер, Эрик В .; Klawe, Maria M. (1985), "Новые нижние оценки для задачи обнаружения цикла", теоретической информатики , 36 (2-3): 231-237, DOI : 10.1016 / 0304-3975 (85) 90044-1.
  20. ^ Поллард, JM (1975), "Монте - Карло метод факторизации", БИТ , 15 (3): 331-334, DOI : 10.1007 / BF01933667 , S2CID 122775546 .
  21. ^ Поллард, JM (1978), «Методы Монте-Карло для вычисления индекса (mod p )», Математика вычислений , Американское математическое общество, 32 (143): 918–924, DOI : 10.2307 / 2006496 , JSTOR 2006496 .
  22. ^ a b Калиски, Бертон С., мл .; Ривест, Рональд Л .; Шерман, Алан Т. (1988), "Является ли стандарт шифрования данных группы (результаты экспериментов на велосипеде DES)?", Журнал криптологии , 1 (1): 3-36, DOI : 10.1007 / BF00206323 , S2CID 17224075 .
  23. ^ Joux (2009) , раздел 7.5, Столкновения в хэш-функциях, стр. 242–245.
  24. ^ Ван Гелдер, Аллен (1987), "Обнаружение Эффективного цикла в Прологе с помощью черепахи-и-зайца техники", журнал логического программирования , 4 (1): 23-31, DOI : 10.1016 / 0743-1066 (87) 90020 -3.
  25. ^ Августон, Михаил; Хон, Миу Хар (1997), "Утверждения для анализа динамической формы структур данных списка", AADEBUG '97, Труды третьего международного семинара по автоматической отладке , Электронные статьи Linköping в области компьютерных и информационных наук, Университет Линчёпинга , стр. 37– 42.

Внешние ссылки [ править ]

  • Габриэль Ниваш, Проблема обнаружения цикла и алгоритм стека
  • Черепаха и Заяц , Портлендский репозиторий паттернов
  • Алгоритм обнаружения цикла Флойда (Черепаха и заяц)
  • Алгоритм обнаружения цикла Брента (телепортирующаяся черепаха)