Глава 7. Сводимость

146. Здесь речь идет о линейной сводимости P^Q задач, связан­ ных с мультипликативными операциями над квадратными числовы­ ми матрицами порядка п. Рассматриваются лишь такие алгоритмы решения задачи Q, для сложности по числу арифметических опера­ ций каждого из которых выполняется соотношение Т(кп) = 0(Т(п)), к = 2,3.

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

а) умножения симметричных квадратных матриц;

б) умножения верхних треугольных матриц;

в) обращения невырожденных матриц.

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

fl_n М₁ 0 V1

0 1_п М₂ , V0 0 ¹п) где M₁,M₂— исходные матрицы, 1_п — единичная матрица порядка п.

147. а) Доказать свойство (R2) рациональных функций, сформули­ рованное в § 29.

Указание. Достаточно доказать, что если полином р(х₁,х₂, ...,х_п) тожде­ственно равен нулю на некотором непустом открытом множестве U аШ^п, то этот полином нулевой. При п = 1 утверждение очевидно. Пусть п > 1 и точ­ка v = (v₁,v₂,...,v_n)eIRⁿ такова, что р(у₁, v₂,..., v) ф 0. Пусть ueU. Множе­ство U — открытое, поэтому у точки и существует окрестность некоторого радиуса г > 0, целиком принадлежащая U. Пусть I — расстояние от и до v, а с₁,с₂,...,с_п—координаты вектора единичной длины, направленного из и в v. Если t пробегает множество Ж, то формулы

x₁ = u₁+c₁t, x₂ = u₂+c₂t, ..., x_n=u_n+c_nt (32.3)

задают прямую в Ш^п, причем при t = 0 получается точка и, а при t = l — точ­ка v. Остается рассмотреть для полинома p(t) одной переменной t, получаю­щегося подстановкой (32.3) в р(х₁,х₂, ...,х_п), его значения в точке t = l и на интервале -г <t<r.

б) Для каких целых n ^ 1 справедливо утверждение, что ес­ли произвольный полином с вещественными коэффициентами от х₁,х₂,...,х_п обращается в нуль на бесконечном подмножестве мно­жества Ж", то этот полином является нулевым?

148. Функция /(n) = |"log₂n!l является нижней границей сложно­ сти по числу сравнений алгоритмов сортировки массивов длины п

Задачи

211

попарно различных рациональных чисел c помощью сравнений и че­тырех арифметических операций (в предложении 29.1 речь шла о сор­тировке вещественных чисел).

149. Функция /(n) = [log₂(n + 1)1 является нижней границей слож­ ности по числу сравнений алгоритмов поиска места элемента в упо­ рядоченном массиве длины п попарно различных вещественных чи­ сел c помощью сравнений и четырех арифметических операций.

150. Пусть известен алгоритм, который по данным с,т, с > 1,

т е N⁺, строит т значащих двоичных цифр числа - (построить

с т значащих цифр некоторого числа х, 0 < х < 1, — это в данном

контексте означает отыскать первую ненулевую цифру после запя­той в двоичной записи этого числа, а затем отбросить все цифры после т цифр, отсчитанных от найденной), и пусть сложность этого алгоритма есть 0(f(m)), где /(т)—некоторая функция такая, что до­полнительно известен алгоритм умножения произвольных a, b е N⁺, сложность которого тоже есть 0(,f(m)), где m = max{A(a), А(Ь)}. На основе этих двух алгоритмов сконструировать алгоритм построения частного и остатка от деления положительных целых а и Ъ, имеющий сложность 0(f(m)), m = max{A(a), А(Ь)}.

Указание. Нужно построить q и г такие, что a = qb + r, 0 sj г < Ъ, или a-=q + s, 0^5<1. Возникновение погрешности при вычислении - может привести к тому, что найденное q будет отличаться на 1 от точного значе­ния; несколько добавочных проб помогут найти точные q и г, не изменяя оценки 0(f(m)) для сложности.

151. Пусть о 0 и jo удовлетворяет неравенствам у ^ у₀ ^ -; пусть последовательность Уо,Ут_,У2> ■■■ получена по рекуррентной формуле

y_i = 2y_i-₁-c_iyf^L_-1, i = l,2, ...

Тогда последовательность Уп, y-i, ••• сходится к -.

152. (Продолжение предыдущей задачи.) Пусть ceN+. Справедли­ во следующее утверждение^г. Пусть у₀ удовлетворяет неравенствам

9~ ^ Уо ^ ~~ и последовательность УсъУъУг» ••• получена по рекуррент­ной формуле

_Vi,

y_i=2y_i-₁-c_iyf₁, i = l,2,..., (32.4)

См. [5, разд. 8.2].

212