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

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

• 1 Идея
• 2 Приложения
• 3 История
• 4 Примечания
• 5 ссылки

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

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

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

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

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

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

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

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

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

• v
• т
• е