Cтраница 1
Полиномиальная цепочка с т О умножениями имеет не более 2т степеней свободы. [1]
Полиномиальная цепочка, содержащая q сложений и вычитаний, имеет не более q - - l степеней свободы. [2]
Найдите полиномиальную цепочку минимальной возможной длины, вычисляющую все многочлены вида uix - - м г / о; докажите, что ее длина минимальна. [3]
Следовательно, любая полиномиальная цепочка с s параметрами имеет не более s степеней свободы. [4]
Покажите, что полиномиальная цепочка, пригодная для вычисления всех нормированных многочленов степени п, имеет не менее n / 2J умножений и не менее л сложений-вычитаний. [5]
Докажите, что полиномиальная цепочка с [ n / 2J l умножениями может вычислять все многочлены степени п, только если она содержит не менее я 2 сложений-вычитаний. Аг-полиномиальная цепочка, в которой все шаги сложения и вычитания являются параметрическими шагами и которая содержит по крайней мере одно параметрическое умножение. [6]
Покажите, что любая полиномиальная цепочка, вычисляющая многочлен шестой степени общего вида и использующая только четыре умножения, должна содержать не менее семи сложений-вычитаний. [7]
Покажите, что любая полиномиальная цепочка, вычисляющая многочлен четвертой степени общего вида и использующая только три умножения, должна содержать не менее пяти сложений-вычитаний. Допустите, что имеется только четыре сложения-вычитания, и покажите, что применимо утверждение упр. [8]
Можно показать, что полиномиальная цепочка с не более чем п степенями свободы не может вычислять все многочлены степени п ( см. упр. [9]
В каком-то смысле очевидно, что полиномиальная цепочка с s параметрическими шагами имеет не более s степеней свободы; мы не можем вычислять функцию с t степенями свободы, имея в своем распоряжении менее чем t произвольных параметров. Этот факт нелегко доказать формально; например, имеются непрерывные функции ( кривые Пеано), отображающие вещественную прямую на плоскость и тем самым переводящие один параметр в два независимых параметра. Однако никакая полиномиальная функция с целочисленными коэффициентами не может обладать таким свойством; доказательство будет дано в упр. [10]
Rm есть множество ( п - наборов вещественных чисел, имеющее не более t степеней свободы. U Я U U т также имеет не более t степеней свободы. Докажите, что полиномиальная цепочка с mi цепными умножениями и та параметрическими умножениями имеет не более 2т1 та бвя, степеней свободы. [11]