Метод четырёх русских

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

Идея

Основная идея метода состоит в том, чтобы разбить матрицу на небольшие квадратные блоки размером t × t для некоторого параметра t и использовать справочную таблицу для быстрого выполнения алгоритма внутри каждого блока. Индекс в справочной таблице кодирует значения ячеек матрицы в левом верхнем углу границы блока до некоторой операции алгоритма, а результат справочной таблицы кодирует значения граничных ячеек в правом нижнем углу блока. после операции. Таким образом, общий алгоритм может быть реализован, оперируя только ( n / t ) ² блоков вместо по n ² ячейки матрицы, где n — длина стороны матрицы. Чтобы сохранить размер таблиц поиска (и время, необходимое для их инициализации) достаточно небольшим, t обычно выбирается равным O (log n ) .

Приложения

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

• вычисление транзитивного замыкания графа,
• Булево матричное умножение ,
• редактировать расчет расстояния,
• выравнивание последовательности ,
• Расчет индекса для сопоставления бинарного смешанного шаблона .

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

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

История

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

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

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

Ссылки

• Arlazarov, V. ; Dinic, E.; Kronrod, M.; Faradžev, I. (1970), "On economical construction of the transitive closure of a directed graph", Dokl. Akad. Nauk SSSR , 194 (11) . Original title: "Об экономном построении транзитивного замыкания ориентированного графа", published in Доклады Академии Наук СССР 134 (3), 1970.
• Ахо, Альфред В .; Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1974). Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. ISBN  978-0-201-00029-0 . ОСЛК   1147299 .
• Бард, Грегори В. (2009), Алгебраический криптоанализ , Springer, ISBN  978-0-387-88756-2