Оглавление
- 1 Обнаружение цикла
- 1.1 Определение цикла
- 1.2 Алгоритм черепахи и зайца Флойда
- 1.3 Алгоритм Брента
- 1.4 Алгоритм Госпера
- 1.5 Сложность и пространство
- 1.6 Компромиссы между временем и пространством
- 1.7 Приложения
- 1.8 Криптографические алгоритмы и структура групп
- 1.9 Компьютерное моделирование небесной механики
- 1.10 Генерация фракталов с набором Мандельброта
- 1.11 Методика “проверки периода”
- 1.12 Рекомендации и внешние ссылки
- 1.13 Полный текст статьи:
- 2 Обнаружение цикла
Обнаружение цикла
-
Определение цикла
- Задача нахождения цикла в последовательности повторяющихся значений функции
- Цикл должен содержать пару индексов i и j, таких что xi = xj
- Алгоритмы быстрого поиска циклов используют постоянное количество памяти
-
Алгоритм черепахи и зайца Флойда
- Использует два указателя, перемещающихся с разной скоростью
- Находит период повторения ν, кратный λ
- Находит первое повторяющееся значение xμ
- Использует O(λ + μ) операций и O(1) памяти
-
Алгоритм Брента
- Основан на поиске наименьшей степени из двух 2i, которая больше, чем λ и μ
- Находит правильную длину λ цикла напрямую
- Использует O(λ + μ) тестов и оценок функций и O(1) места для хранения
- Работает быстрее, чем алгоритм Флойда, и ускоряет алгоритм Полларда ро
-
Алгоритм Госпера
- Находит период и границы начальной точки цикла
- Поддерживает массив черепах для сравнения значений
- Экономичен в использовании пространства и времени
- Обнаруживает повторение перед третьим появлением значения
-
Сложность и пространство
- Временная сложность: O((μ + λ) ⋅ log(μ + λ))
- Пространственная сложность: Θ(log(μ + λ))
- Без предположения о постоянном размере значений: Ω(log^2(μ + λ))
-
Компромиссы между временем и пространством
- Методы с использованием хэш-таблиц и хэш-таблиц
- Методы с сохранением значений по степеням числа R
- Методы с сохранением значений на основе их расположения
-
Приложения
- Определение длины цикла генератора псевдослучайных чисел
- Алгоритмы теории чисел, такие как rho Полларда и Кенгуру
- Криптографические приложения, такие как атаки на DES и поиск коллизий в хэш-функциях
- Обнаружение бесконечных циклов в компьютерных программах
- Моделирование клеточных автоматов и анализ структур данных связанных списков
- Приложения в вычислительной теории групп
-
Криптографические алгоритмы и структура групп
- Криптографические алгоритмы Калиски и др. можно рассматривать как попытку определить структуру неизвестной группы.
-
Компьютерное моделирование небесной механики
- Фич (1981) упоминает применение компьютерного моделирования небесной механики Уильямом Каханом.
- Обнаружение циклов в фазовом пространстве орбитальной системы используется для определения периодичности системы в пределах точности моделирования.
-
Генерация фракталов с набором Мандельброта
- При генерации фракталов с набором Мандельброта используются методы повышения производительности.
- Один из методов называется “проверка периода” и заключается в нахождении циклов на точечной орбите.
-
Методика “проверки периода”
- В статье описывается методика “проверки периода”.
- Для реализации метода необходимо реализовать алгоритмы обнаружения циклов.
-
Рекомендации и внешние ссылки
- Внешние ссылки включают статьи и алгоритмы, связанные с обнаружением циклов.
- Примеры алгоритмов: алгоритм определения цикла Флойда и алгоритм определения цикла Брента.