Викия

Математика

Гипотеза Штрассена

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


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

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

Шаблон:Сирота

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

Точная формулировка Править

Для сколь угодно малого \varepsilon > 0 существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера n \times n за {\rm O}(n^{2+\varepsilon}) операций.

История Править

Задача перемножения двух больших квадратных матриц часто встречается на практике — этим объясняется практическая ценность гипотезы. Поскольку умножение чисел есть операция более трудоёмкая, чем сложение, то при оценке сложности алгоритма перемножения матриц учитывают только количество умножений. Очевидно, что две матрицы размера n \times n можно перемножить за n3 умножений и n2(n-1) сложений; очевидно также, что нельзя сделать степень n меньше 2 (т.к. в таких матрицах n2 значений, и все их надо обработать). Однако хотелось бы сократить количество производимых умножений (возможно, за счёт увеличения количества сложений). В 1969 году немецкий учёный Штрассен предложил более быстрый алгоритм, который требовал {\rm O}(n^{\log_2 7}) \approx {\rm O}(n^{2,807}) умножений. В 1982 году было доказано, что достаточно {\rm O}(n^{2,376}) операций (алгоритм Копперсмита—Винограда), хотя предложенный ими алгоритм редко используется на практике и имеет скорее теоретическое значение.

Викия-сеть

Случайная вики