ИСТИНА

Курс посвящен компьютерной алгебре и сложности вычислений. Всем известно, как умножать числа в столбик. На первый взгляд кажется, что для умножения $n$-значных чисел нужно $n^2$ элементарных операций. Однако неожиданно в 1960 году А. Карацуба придумал алгоритм делать это за $n^{\log_2(3)}$ операций. Позднее Тоом усовершенствовал этот алгоритм. На первый взгляд кажется что для умножения матриц $n$-го порядка нужно $n^3$ умножений, однако неожиданно Штрассен обнаружил что хватает $n^{\log_2(7)}$ уножений.