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

Cn{x){Ci,i-r+<it)(x" + ll)-

Пусть pW=2/nW.

(а) Докажите, что показатель наибольшей степени переменной X, коэффициент при которой зависит от ау, равен г,;, а показатель наибольшей степени переменной х, коэффициент при которой зависит от pj;, равенri-rtj.

(б) Докажите, что всякий полином степени, не превосходящей т(т+1)+1, со старшим коэффициентом, равным 1, можно представить m(m+1)-Ь1 параметрами, так что (1) этот полином можно вычислить по параметрам за т{т+1)/2+0(т) умножений и (11) параметры являются рациональными функциями от коэффициентов.

Проблемы для исследования

Каждой неветвящейся программе можно следующим образом поставить в соответствие ориентированный ациклический граф. Узлы графа представляют входы и переменные. Если / *~g*li - шаг, то из g в / и из /I в / идут ориентированные ребра. Заметим, что число шагов программы ровно вдвое меньше числа ребер. Поэтому нижняя оценка числа ребер в любом ориентированном ациклическом графе, соответствующем вычислению для конкретной задачи, дает нижнюю оценку числа шагов в любой неветвящейся программе для этой задачи.

(в) Параметры aj в (б) могут оказаться комплексными числами. Как преодолеть эту трудность? Указание: Подставьте у+с вместо х в р {х) при подходящем с и вместо вычисления значения р {х) в точке х=Хо вычислите некоторый полином р(у) в точке у=Хо-с.

Упр. 12.35 не дает метода для вычисления «г. Более того, параметры at не обязательно рациональные числа. В следующем упражнении делается попытка преодолеть эти трудности.

**12.36. Пусть т - целое число. Для 1</<т положим

10--2

И Г[]-т-/+/-Ы, Определим цепь с параметрами а и

как вычисление вида

с„ {x)(xno + ai,)(xri + fii,),

(х) *- (Сц +ai)(xi + р,-з).



12.37. Докажите или опровергните, что для больших п всякий ориентированный ациклический граф с п истоками и п выходами, удовлетворяющий условию на пропускные способности из упр. 12.22, содержит не менее п log п ребер.

12.38. Удовлетворяет ли каждый граф, соответствующий неветвящейся программе для умножения двух «-разрядных двоичных целых чисел (предполагается, что используются битовые операции), условию на пропускные способности из упр. 12.22?

Замечания по литературе

Теорема 12.2 и общая формулировка задачи, изучаемой в этом разделе, принадлежат Винограду [1970а]. Теоремы 12.1 и 12.3 взяты из работы Фидуччиа [19711. Тот факт, что без использования делений для вычисления значения полинома /г-й степени требуется п умножений, приписывается (Кнутом [1969]) Гар-сиа Пан [1966] распространил этот результат на мультипликативные операции. Моцкин [1955] показал, что для вычисления значения полинома с предварительной обработкой коэффициентов необходимо [ п12 \-\-\ умножений. Одной из первых в этом направлении была работа Островского [1954]. Белага [1961] усилил результат Моцкина, а также получил оценку для числа сложений -вычитаний. Виноград [19706] показал, что для умножения комплексных чисел необходимы три умножения.

Упр. 12.7 обсуждается Виноградом [1973]. Материал о нижних оценках для умножения матриц (упр. 12.9-12.16) основан на работе Хопкрофта, Керра [1971]. Результаты упр. 12.17 независимо получены несколькими авторами. Часть (в) Виноград (частное сообщение) приписывает Унгару. Упр. 12.18 и. 12.19 заимствованы у Хопкрофта, Мусинского [1973]. Упр. 12.20-12.22, 12.37 и 12.38 основаны на беседах с Флойдом. Упр. 12.24 и 12.25 взяты у Моргенштерна [1973], упр. 12.28 и 12.29 -у Нечипорука [1966], 12.30(a) - у Харпера, Сэвиджа [1972], упр. 12.32 -у Штрассена [1974], упр. 12.33 - у Керра [1970], упр. 12.34- у Пратта [1974], упр. 12.35 - у Ива [1964] и упр. 12.36 - у Рабина. Винограда [1971].

Еще некоторые попытки получения нижних оценок для числа арифметических операций были сделаны Бородиным, Куком [1974], Кедемом [1974] и Кирк-патриком [1972, 1974].

1) Этот результат был впервые доказан В. Я. Паном в i960 г. в более сильной форме и изложен в его статье [1962].

Читатель, интересующийся алгебраической трактовкой вопросов сложности вычисления наборов полиномов, может обратиться к многочисленным работам Ф. Штрассена, например [1973, 1976].- Прим, перев.



список ЛИТЕРАТУРЫ )

Адельсон-Вельский Г. М., Ландис Е. М.

[1962] Один алгоритм организации информации. Доклады. АН СССР, 146, № 2, 263-266.

Арлазаров В. Л., Диниц Е. А., Кронрод М. А., Фараджев И. А.

[1970] Об экономном построении транзитивного замыкания графа. Доклады

АН СССР, 194, №3, 487-488. Ахо (ред.) (Aho А. V.)

[1973] Currents in the theory of computing, Prentice-Hall, Englewood Cliffs,

N.J.

Axo, Гэри, Ульман (Aho A. V., Garey M. R., Ullman J. D.)

[1972] The transitive reduction of a directed graph, SI AM J.Comput., 1, №2, 131-137.

Axo, Стенглиц, Ульман (Aho A. V., Steiglitz K., Ullman J. D.)

[1974] Evaluating polynomials at fixed sets of points, Bell Laboratories, Murray Hill, N.J. Cm. также SIAM J. Comput., 4, № 4 (1975), 533-539.

Axo, Ульман (Aho A. V., Ullman J. D.)

[1972] The theory of parsing, translation and compiling. Vol. 1: Parsing, Prentice-Hall, Englewood Cliffs, N. J. (Русский перевод: Axo A., Ульмак Дж., Теория синтаксического анализа, перевода и компиляции. Том 1: Синтаксический анализ, М., Мир, 1978.)

[1973] The theory of parsing, translation and compiling. Vol. 2: Compiling, Prentice-Hall, Englewood Cliffs, N.J. (Русский перевод: Axo A., Ульман Дж., Теория синтаксического анализа, перевода и компиляции. Том 2: Компиляция, М., Мир, 1978.) Ахо. Хиршберг, Ульман (Aho А. V., Hirschberg D. S., Ullman J. D.)

[1974] Bounds on the complexity of the maximal common subsequence problem, IEEE 15th Annual Symposium on Switching and Automata Theory, New Orleans, 104-109.

Axo, Хопкрофт, Ульман (Aho A. V., Hopcroft J. E., Ullman J. D.)

[1968] Time and tape complexity of pushdown automaton languages./я/олт. and Control., 13, № 3, 186-206. (Русский перевод в сб. «Языки и автоматы», М.. Мир, 1975, стр. 185-197.)

[1074] On finding lowest common ancestors in trees, SIAM J. Comput., 5, № 1, 115-132.

Бамч, Хопкрофт (Bunch J.. Hopcroft J. E.)

[1974] Triangular factorization and inversion by fast matrix multiplication,

Matli. Comput., 28, № 125, 231-236. Белага Э. Г.

[1961] О вычислении значений многочленов от одного переменного с предва-

1) Работы, отмеченные знаком °, добавлены при переводе.-Ярил, перев.





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.002