Главная Промышленная автоматика.

) Как обычно, знак • опускается, если это не приводит к недоразумениям. Кольцо с коммутативным умножением.

3) каждый элемент а из А-{0} обладает обратным а-* относительно умножения, т. е. аа-*=а-*а=1).

Пример 12.1. Вещественные числа с обычными операциями сложения и умножения образуют поле. Целые числа образуют кольцо, но не поле, поскольку целые числа, отличные от ±1, не имеют обратных, являющихся целыми числами. Но для простого числа р целые числа по модулю р образуют (конечное) поле. □

Рассмотрим задачу вычисления произвольного полинома р{х)=

=aijc в некоторой точке л:. Мы хотим найти алгоритм, который по

значениям QiHXb качестве входов строит соответствующее значение р{х) в качестве выхода. Этот алгоритм должен работать на всех возможных значениях своих входов, принадлежащих некоторому полю. Максимальное число сложений, вычитаний и умножений, выполняемых алгоритмом, где максимум берется по всем допустимым входам, называется арифметической сложностью этого алгоритма.

Заметим, что одни полиномы л-й степени вычислить оказывается проще, чем другие. Например, на вычисление л:"+2 тратится порядка log п операций, тогда как интуитивно мы чувствуем, что на вычисление "произвольного" полинома л-й степени должно расходоваться линейное число операций. Поэтому алгоритм для вычисления значений, пригодный только для конкретного полинома, может работать много быстрее, чем алгоритм, применимый ко всем полиномам. Чтобы сформулировать понятие алгоритма, пригодного для целого класса задач, введем для представления входных переменных формальные переменные.

Определение. Формальной переменной над алгебраической системой называется символ, не принадлежащий множеству элементов этой системы. Пусть f=(Л, +, •, О, 1) - поле и Xi,. . ., x„ - формальные переменные над F. Расширением F[xi,. . ., л:„] поля F этими переменными Xf,. . ., л;„ называется такое наименьшее коммутативное *) кольцо (в, +, •, О, 1), что В содержит A[i{Xi,. . . . . ., Хп).

Заметим, что эти формальные переменные не связаны никакими тождествами. Всякий полином с коэффициентами из F и "неизвестными" Xi,. . ., Хп представляет некоторый элемент из F[xu. . ., х„\. Два полинома обозначают один и тот же элемент из F[xi,. . ., xj, если один из них можно превратить в другой с помощью аксиом коммутативного кольца. Единица в F будет также единицей в F\xu. ., Xnl



Пример 12.2. Пусть F- поле вещественных чисел. Тогда кольцо F[x, у\ включает в себя х, у и все вещественные числа. Так как оно замкнуто относительно сложения, то х+у и х+А принадлежат Fix, у\. Так как оно замкнуто относительно умножения, то оно содержит элемент (х+у)(х+А), эквивалентный х+ху-\-4х+Ау в силу закона дистрибутивности для кольца. □

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

Зададим снова вопрос. "Сколько арифметических операций требуется для вычисления значений произвольного полинома?" На самом деле вопрос касается числа операций + и •, необходимых

для построения выражения atx (или эквивалентного ему) от формальных переменных Оо.....а„ и х. Это мотивирует следующую

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

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

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

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

3) последовательности ишгов вида а ч-- &9с, где Э - один из знаков -f, - или *, а - переменная, не участвующая на предыдущих шагах, b и с - либо входы, либо элементы из F, либо имена переменных, появившиеся слева от стрелки на одном из предыдущих шагов.

Краткости ради будем писать а -<-~Ь вместо а Ь+0 и а -<--b

вместо а -«-О-Ь. Элемент поля F, входящий в вычисление, называется постоянной.

Для определения результата вычисления нам нужно понятие значения переменной в вычислении. Говоря неформально, мы считаем, что вычисление производится шаг за шагом; на каждом шаге новой переменной присваивается элемент из F[Xi, . . . , х„], где Xi, . . . , Хп - входы. Значение v (а) переменной или входа а определяется следующим образом. Если а - вход или элемент из F, то V {а)=а. Если а - переменная и а Ь9с - шаг, в котором а стоит слева, то v{a)=v(b)Uv(c).

Данное вычисление вычисляет множество Е выражений из F[xi, ... , Хп\ относительно поля F, если для каждого выражения еЕ найдется в этом вычислении такая переменная /, что v{f)=e.

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



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

Пример 12.3. Вспомним, что вычисление произведения двух комплексных чисел a+ib и c+id относительно поля вещественных чисел можно рассматривать как вычисление выражений ас-bd и ad+bc. Очевидное вычисление выглядит так:

/i <-о*с

hb*d

fia*d /б -/. + /5-

Значением fi является ас. Аналогично v(f2)=bd и v{f3)=ac-bd. Таким образом, значение /я равно первому выражению. Значение /в равно ad+bc, т. е. второму выражению. Следовательно, это вычисление вычисляет произведение двух комплексных чисел.

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

ha + b h *- a*h

hh + h

h*-d + c

hb*f.

Легко показать, что v{fb)=ad+bc и v(f„)=ac-bd. □

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

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 [155] 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037