12.2. ЕЩЕ РАЗ О НЕВЕТВЯЩИХСЯ ПРОГРАММАХ

Зададим снова вопрос. "Сколько арифметических операций требуется для вычисления значений произвольного полинома?" На самом деле вопрос касается числа операций необходимых для построения выражения (или эквивалентного ему) от формальных переменных Это мотивирует следующую модель вычислений, которая, по существу, есть модель неветвящейся программы, введенной в разд. 1.5.

Определение. Пусть поле. Вычисление относительно состоит из

1) множества формальных переменных, называемых входами,

2) множества имен переменных,

3) последовательности шагов вида где один из знаков или — переменная, не участвующая на предыдущих шагах, и с — либо входы, либо элементы из либо имена переменных, появившиеся слева от стрелки на одном из предыдущих шагов.

Краткости ради будем писать вместо вместо а Элемент поля входящий в вычисление, называется постоянной.

Для определения результата вычисления нам нужно понятие значения переменной в вычислении. Говоря неформально, мы считаем, что вычисление производится шаг за шагом; на каждом шаге новой переменной присваивается элемент из где входы. Значение переменной или входа а определяется следующим образом. Если а — вход или элемент из то Если а — переменная и а шаг, в котором а стоит слева, то

Данное вычисление вычисляет множество выражений из относительно поля если для каждого выражения найдется в этом вычислении такая переменная что

Заметим, что вычисление рассматривается относительно данного основного поля. Например, чтобы вычислить относительно поля вещественных чисел, требуются два умножения, даже если

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

Пример 12.3. Вспомним, что вычисление произведения двух комплексных чисел относительно поля вещественных чисел можно рассматривать как вычисление выражений Очевидное вычисление выглядит так:

Значением является Аналогично Таким образом, значение равно первому выражению. Значение равно т. е. второму выражению. Следовательно, это вычисление вычисляет произведение двух комплексных чисел.

Другое вычисление для комплексного умножения использует только три вещественных умножения:

Легко показать, что

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

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

умножения имеют гораздо большую сложность, чем сложения или вычитания.

Например, в гл. 6 мы видели, что умножение двух -матриц за 7 арифметических умножений дает алгоритм умножения произвольных матриц за время Использование же 18 сложений в алгоритме Штрассена не влияет на асимптотику. На первом уровне рекурсии для алгоритма Штрассена 7 умножений -матриц по мере роста становятся гораздо сложнее, чем 18 (или любое другое число) сложений и вычитаний матриц того же размера.

На самом деле если бы можно было умножать две -матрицы с помощью только шести умножений в некоммутативном кольце, то у нас мог бы быть алгоритм умножения матриц со сложностью независимо от того, сколько тратится на умножение -матриц сложений и вычитаний. (Можно, однако, показать, что для того, чтобы такой алгоритм работал для произвольного кольца, для умножения -матриц необходимы 7 умножений; см. Хопкрофт, Керр [1971].)

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