Алгоритм четырёх русских — в информатике представляет собой метод ускорения алгоритмов с использованием булевых матриц или, в более общем смысле, алгоритмов с использованием матриц, в которых каждая ячейка может принимать только ограниченное число возможных значений.
Разработанный комбинаторный алгоритм позволяет умножать матрицы за . С некоторыми изменениями можно получить время работы . В 2015 году был получен алгоритм, работающий за .
Идея Основная идея метода состоит в том, чтобы разделить матрицу на небольшие квадратные блоки размером для некоторого параметра и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а значения в таблице поиска кодируют значения граничных ячеек в правом нижнем углу блока после операции. Таким образом, общий алгоритм может быть выполнен с использованием только блоков вместо ячеек матрицы, где — длина строки матрицы. Для того чтобы размер таблиц поиска (и время, необходимое для их инициализации) было достаточно малым, обычно выбирается равным .
Применение
Алгоритмы, к которым может быть применен метод четырех русских:
вычисление транзитивного замыкания графа, умножение булевых матриц, расчет расстояния редактирования, выравнивание последовательности, вычисление индекса для двоичного сопоставления с шаблоном.
В каждом из этих случаев это ускоряет алгоритм в или раз.
Опубликованный Бардом алгоритм инверсии матрицы «Метод четырёх русских» реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F2. M4RI используется SageMath и библиотекой PolyBoRi.https://malb.bitbucket.io/m4ri/
Алгоритм умножения булевых матриц
Описание алгоритма Алгоритм получает на вход две булевы матрицы и и возвращает матрицу .
Пусть .
Разобьём на матрицы , где , состоит из столбцов матрицы с номерами от до , а — из оставшихся столбцов, к которым добавлены столбцы нулей, если это нужно, чтобы в матрице было столбцов.
Разобьём на матрицы , где , состоит из строк матрицы с номерами от до , а — из оставшихся строк, к которым добавлены строки нулей, если это нужно, чтобы в матрице было строк.
Псевдокод begin
for to do
begin
comment Вычисляем суммы строк матрицы ;
СУММАСТРОК[]
for to do
begin
Пусть таково, что
СУММАСТРОК[]СУММАСТРОК[]
end
Пусть — матрица, i-я строка которой равна СУММАСТРОК[ЧИС()],
где — j-я строка матрицы , ,
end;
Пусть
end.А. Ахо, Дж. Ульман, Дж. Хопкрофт. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979ЧИС(v) — целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0,1,1])=6.
Обоснование корректности Простая индукция по показывает, что СУММАСТРОК[] становится равной поразрядной булевой сумме таких строк матрицы , что в двоичном представлении числа на -том месте справа стоит 1. Отсюда вытекает, что и .
Время работы Рассмотрим цикл по . Вычисление и присваивание значений СУММАСТРОК[] происходит за . Вычисление занимает время . Итерация цикла выполняется за , всего итераций. , , следовательно весь цикл выполнится за .
Вычисление ЧИС() имеет сложность , а копирование вектора СУММАСТРОК[ЧИС()] — сложность , так что инициализация выполняется за . Итого, цикл по выполняется за . Всего итераций. , следовательно сложность цикла — .
Сумма вычисляется за .
Итоговая сложность алгоритма — .
История
Алгоритм был введён В. Л. Арлазаровым, Е. А. Диницем, М. А. Кронродом и И. А. Фараджевым в 1970 году. Происхождение названия неизвестно; А. Ахо, Д. Хопкрофт и Д. Ульман (1974) объясняют:
Второй метод, часто называемый алгоритмом «четырёх русских», в честь его изобретателей, в какой-то мере «практичнее» алгоритма в теореме 6.9.
Все четыре автора работали в Москве в то время.
Примечания
Категория:Информатика