В информатике , то метод четыре россиян является методом для ускорения алгоритмов , связанных с булевыми матрицами , или , в более общем алгоритмах , включающие матрицы , в которой каждая ячейка может принимать лишь ограниченное число возможных значений.
Идея
Основная идея метода состоит в том, чтобы разбить матрицу на маленькие квадратные блоки размером t × t для некоторого параметра t и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а результат таблицы поиска кодирует значения граничных ячеек в правом нижнем углу блока. после операции. Таким образом, общий алгоритм может выполняться, работая только с ( n / t ) 2 блоками вместо n 2 ячеек матрицы, где n - длина стороны матрицы. Чтобы сохранить размер таблиц поиска (и время, необходимое для их инициализации) достаточно малым, t обычно выбирается равным O (log n ) .
Приложения
Алгоритмы, к которым может быть применен метод четырех русских, включают:
- вычисление транзитивного замыкания графа,
- Умножение булевых матриц ,
- редактировать расчет расстояния ,
- выравнивание последовательностей ,
- расчет индекса для сопоставления двоичных беспорядочных шаблонов .
В каждом из этих случаев он ускоряет алгоритм на один или два логарифмических множителя.
Алгоритм обращения матриц «Метод четырех русских», опубликованный Бардом, реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F 2 . M4RI используется SageMath и библиотекой PolyBoRi. [1]
История
Алгоритм был предложен В.Л. Арлазаровым , Е.А. Диничем, М.А. Кронродом и И.А. Фараджевым в 1970 году. [2] Происхождение названия неизвестно; Ахо, Хопкрофт и Ульман (1974) объясняют:
- Второй метод, часто называемый алгоритмом «четырех русских» из-за мощности и национальности его изобретателей, несколько более «практичен», чем алгоритм из теоремы 6.9. [3]
Все четыре автора работали в то время в Москве, Россия . [4]
Заметки
- ^ M4RI - Главная страница
- ^ Арлазаров и др. 1970 .
- ^ Ахо, Hopcraft & Ульман 1974 , стр. 243.
- ^ Автор принадлежности на MathNet.ru.
Рекомендации
- Арлазаров, В .; Dinic, E .; Кронрод, М .; Фараджев И. (1970), "Об экономном построении транзитивного замыкания ориентированного графа", Докл. Акад. АН СССР , 194 (11). Оригинальное название: "Об экономном построении транзитивного замыкания ориентированного графа", опубликовано в Доклады Академии Наук СССР 134 (3), 1970.
- Ахо, Альфред V .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов , Addison-Wesley
- Бард, Грегори В. (2009), Алгебраический криптоанализ , Springer, ISBN 978-0-387-88756-2