Метод четырех русских - Method of Four Russians

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

Идея

Основная идея метода - разбить матрицу на небольшие квадратные блоки размером т × т для какого-то параметра т, и использовать Справочная таблица для быстрого выполнения алгоритма в каждом блоке. Индекс в поисковой таблице кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а результат поисковой таблицы кодирует значения граничных ячеек в нижнем правом углу блока. после операции. Таким образом, общий алгоритм может быть выполнен, работая только с (п/т)2 блоки вместо на п2 ячейки матрицы, где п - длина стороны матрицы. Чтобы размер таблиц поиска (и время, необходимое для их инициализации) оставался достаточно маленьким, т обычно выбирается О(бревно п).

Приложения

Алгоритмы, к которым может быть применен метод четырех русских, включают:

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

Алгоритм обращения матриц Метод четырех русских, опубликованный Бардом, реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F2. M4RI используется SageMath и библиотека PolyBoRi.[1]

История

Алгоритм был представлен В. Л. Арлазаров, Э.А.Динич, М. А. Кронрод, И.А.Фараджев в 1970 г.[2] Происхождение названия неизвестно; Ахо, Хопкрофт и Ульман (1974) объяснять:

Второй метод, часто называемый алгоритмом «четырех русских» из-за мощности и национальности его изобретателей, несколько более «практичен», чем алгоритм из теоремы 6.9.[3]

Все четыре автора работали в Москва, Россия в то время.[4]

Примечания

  1. ^ M4RI - Главная страница
  2. ^ Арлазаров и др. 1970 г..
  3. ^ Ахо, Хопкрафт и Ульман 1974, п. 243.
  4. ^ Принадлежность к авторам на MathNet.ru.

Рекомендации

  • Арлазаров, В.; Dinic, E .; Кронрод, М .; Фараджев, И. (1970), «Об экономном построении транзитивного замыкания ориентированного графа», Докл. Акад. АН СССР, 194 (11). Оригинальное название: «Об экономном построении транзитивного замыкания ориентированного графа», опубликовано в Доклады Академии Наук СССР 134 (3), 1970.
  • Ахо, Альфред V .; Хопкрофт, Джон Э .; Ульман, Джеффри Д. (1974), Разработка и анализ компьютерных алгоритмов, Эддисон-Уэсли
  • Бард, Грегори В. (2009), Алгебраический криптоанализ, Спрингер, ISBN  978-0-387-88756-2