Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 49
Текст из файла (страница 49)
° 36. [Мйб] Покажите, что любая цепочка поликанов, которая вычисляет папином обще~о вида четвертой степени, используя три умножения, лачжна иметь по крайней мере пять сложений-вычитаний. [Указание. Предположите, что существует только четыре сложения- вычнтания, и покажите, что применимо упр, 34, поэтому схема должна быть частного вида, который не предсзавляет все полнномы четвертой стецени.] Зб. [М37] Продолжая предыдущее упражнение, покажите, что любая цепочка палино- мов, которая вычисляет обычный полинам седьмой степени и использует только четыре умножения, должна иметь по крайней мере семь сложений-вычитаний, Зу. [Мв1] (Т. С. Мацкин (Т.
3. Мосхрбп).) Покажите, что "почти все" рациональные функции вида (и„х" + х" '+. + и~к+ ие)/(х" +и ~х" '+ + е х+ ие) с коэффициентами из поля Н можно вычислить, воспользовавшись схемой п~+/)~/(к+аз+ба/(х+ +В /(х+и +1) ")) для соответствующих и, 8, из Н. (Эта схема цепных дробей имеет и делений н 2п сложений; под "почти всеми" рациональными функциями понимаются все функции, за исключением тех, коэффициенты которых удовлетворяют некоторым нетривиальным полиномиальным уравнениям.) Определите оь и /1 для рациональной функции (х + 10х+ 29)/(х + 8х+ 19). ь 38. [НМУЗ] (В. Я. Пан, 1962.) Назначение данного упражнения — доказать, что правило Горнера действительно оптимально, если предварительно не адаптировать коэффициент.
Необходимо произвести и умножений ни сложений для вычисления и х" + +и1х+ие, если заданы переменные и, ..., им ие, х и произвольные постоянные, рассмотрим цепочки, такие, как раньше, но тшс, что и„, ..., иц ие, х являются переменными.
Например, можно сказать, что Л з 1 = и;, Ла = х. Чтобы показать, что правило Гарнира наилучшее, удобно доказать более общую теорему. Пусть А = (а, ), 0 < 1 < т, 0 < 1 < и, — действительная матрица размера (т+ 1) х (и+ 1) и ранга и+ 1 и пусть В = (Ье,..., Ь,) — действительный вектор. Докажите, что любая цепочка гпьтипомов, которая вычисляет м Р(х;ие,...,и,) = ~ (а*око+. +а;„и +Ь„)х', =е включает по крайней мере и умножевий в цепочке. (Заметим, что это не тодько означает, что рассматривается несколько фиксированных цепочек, параметры а которых— определенные значения, зависящие от А и В, Это означает, что и цепочка, и значения аэ могут зависеть от заданных матрицы А и вектора В. Не важно, как выбраны А, В и значения аэ", невозможно вычислить Р(х;ие,..., и„), не выполнив и "умножений в ценочке".) Из предположения, что ранг матрицы А рэвен и+ 1, вытекает, что и» > и. [Указание.
Покажите, что из любой такой схемы можно вывести другую схему, которая имеет меныпе умножений в цепочке и и уменьшено на единицу.] 39. [М88] (Т. С. Моцкин, 1954.) Покажите, что схему вцла нч = х(к+п~)+ бы ю» = ю» ~(ип + э»к+ а») + б»х+б» для 1 < й < п»г где оы Ỡ— действительные числа и у», Ỡ— целые числа, можно использовать для вычисления всех нормированных полиномов степени 2щ нед полем действительных чисел. (Для различных полиномов можно по-разному выбирать о„, 8», у» и б».) Попытайтесь, когда возможно, предположить, что б» = О. 40.
[М41] Можно ли нижнюю грань количества операций умножения в теореме С поднять от [и/2] + 1 до [и/2]+ 1 (см, упр, ЗЗ)? 41. [88] Покажите, что действительную и мнимую части (а+ Ей)(с+ б() можно получить с помощью трех умножений и пяти сложений действительных чисел, где два сложения включают только а и б. 42. [8б] (М. Патерсон (йй Раэегэоп) и Л. Штокмейер (Ь. 3»ос(ешеуег).) (а) Докажите, что цепочка полиномов с и» > 2 умножениями имеет максимум е гл + 1 степеней свободы.
(Ь) Покажите, что для всех и > 2 существуют такие полиномы степени и, все коэффициенты которых — нули или единицы, которые не могут быть вычислены любой цепочкой полиномов с менее чем [»/й] умноженкями, если все параметры оэ должны быть целыми числами.
(с) Покажите, что любой полипом степени и с целыми коэффициентами можно вычислить при помощи полностью целочисленного алгоритма, который вьпюлняет максимум 2 [»/г»] умножений, если количество произведенных сложений не имеет значения. 43. [88] Объясните, как вычислить х" + + к + 1, выполнив 21(п + 1) — 2 операций умножения и 1(и+ 1) сложения (не операций деления или вычитания), где 1(п) — функция, рассматриваемая в разделе 4.6.3. ь 44.
[Мйб] Покажите, что любой нормированный полипом и(х) = х" + и»я" '+ +ее можно вычислить, выполнив у»и+ О()об и) Умножений и < 2»п ело»хений и использовав параметры ац аэ, ... — полииомы от и„и и э, ... с целыми коэффициентами. [Уеиахпе. Сначала рассмотрите случай, когда и = 2'.] ь 46. [НМ88] Пусть (Еп») — танзер размера и» х и х э и пусть Р, О, Н вЂ” невырожденные матрицы соответственно размера и» х и», и х и и э х в. Если Тз» = ~,, ~,".,„, ~„».. Рн ОВ Н»м Ек; » для всех», /, /», докажите, что тензор (тэ») имеет такой же ранг, как и (еп»).
[Указание. Рассмотрите, что произойдет, когда Р», С ', Н е применить таким же способом к (Тп»).] 46. [М88] Докажите, что все пары (эц ээ) билинейных форм от (хц яэ) и (рц рэ) можно вычислить с максимум тремя умножениями в цепочке. Другими словами, покажите, что каждый тенэор размера 2 х 2 х 2 имеет ранг < 3. 47. [М88] Докажите, что для всех и», и и э существует тенэор размера и» х и х э, ранг которого равен по крайней мере ] гине/(и»+и+э)]. Обратно, покажите, что каждый теизор размера и» х и х э имеет ранг, не превышающий тпв/щвх(»п, и, э).
46. [М81] Если (Ец») и (Е',1») — тензоРы РазмеРа и» х и х в и и»' х и' х э' соответственно, то их прлмал сумма (Е, «)Ю(Ед») = (Е';») является тензором размера (т+из) х (ц+и ) х (э+э ), определен»ьпе как Е» Е» если Е < и» б < и й < э илн если е > т, 2 > и, lе > щ в остальных случаях Е' „= О. Их прямое произведение (Ео «) З (Ез «) = (Е;. «) — эта тензор размера тт х ии х эв', определенный как ЕЕ ь > О> > Е„«>— ЕМ«Е; '« „, Получите верхние грани га>«)е(Е' «) < гап(е(Е;;«) + гап)е(Е[««) н гап(е(Е''«) < 1(еи ) ' )е(е "«).
° 49. [НМ26] Покажите, что ранг тензора (Е, «) размера гп х и х 1 такой же, как его ранг, когда он записан в виде матрицы (ео> ) размера пе х и, соответствующий традиционному определению ранга матрицы как максимального числа линейно независимых строк. 50. [НМЯО] (Ш. Виноград.) Пусть (О.«) — танзер размера гии х и х т, соответствующий умножению матрицы размера ги х и на вектор-столбец размерности и х 1. Докажите, что ранг теизора (Ем«) равен ти. 51. [М84] (Ш, Виноград.) Придумайте алгоритм для циклической свертки степени 2, который использует 2 умножения и 4 слаженна, ие считая операций с х,. Подобно этому придумайте алгоритм для степени 3, используя 4 умножения и П сложений.
(См, соотношение (69), которое позволяет релеить аналогичную задачу для степени 4.) 52. [М26] (Ш. Виноград.) Пусть и = и'и", где и' Л. и". Пусть заданы нормальные схемы для циклических сверток степени и' и и"', использующие соответственно (т', т") умножений в цепочке, (р,р") умножений параметров и (а,а ) сложений. Покажите, Ф ) как построить нормальную схему для циклической свертки степени и, используя т т умножений в цепочке, р'и" + т'р" умножений параметров и а'и" + т'а" сложений.
53. ]НМ40] (Ш. Виноград.) Пусть «о — т-й комплексный корень нз единицы. Рассмотрим одномерное дискретное преобразование Фурье Да) = ~~. Р(Е)ео", для 1 < э < гл. а) Когда т = р' — степень нечетного простого числа, покажите, чта эффективные нормальные схемы вычисления циклических сверток степеней (р-1)р для О < й < е при« водят к эффективным алгоритмам вычисления преобразования Фурье т комплексных чисел.
Предложите подобную конструкцию для случая, когда р = 2, Ь) Когда т = т'т" и т' л т", покажите, что алгоритмы преобразования Фурье для т' и т" мовена скомпоновать так, чтобы получить алгоритм преобразования Фурье для т элементов. 54. [М23] Теорема «Ч доказана для бесконечных полей. Сколько элементов должно содержаться в конечном ноле, чтобы доказательство теоремы ЪЧ оставалось справедливым7 $$.
[НМ33] Определите ранг ганзе>ра (74), когда Р— ироизеольнал матрица размера ахи. 56. [МУ2] (У. Штрассен (Ч. Яегвваеп).) Покажите, что любая цепочка полиномов, которая вычисляет множество квадратичных форм 2,". > 2"" га«х,х«для 1 < к < э, должна использовать, в целом, по крайней мере -'гап(е(ге>«+ г,«) умножений в цепочке, [Указание. Покажите, что минимальное число умножений в цепочке равно минимальному рангу (й>«), взятому по всем тензорам (ео«), таким, что ео«+ е и = гу«+ гз«для всех е, у, >е.] Воспользуйтесь этим для доказательства того, что любая цепочка полиномов, вычисляющая множество билинейных форм вида (47) и соответствующая тензору (Е;;«), нормален он или анормален, должна использовать хотя бы угвп)е(Е, «) умножений в цепочке.
57. [М20] Покажите, что быстрое преобразование Фурье можно использсеать для вычисления коэффициентов произведения двух заданных полнномов степени и х(в) 9(и), произведя 0(и!оба) операций (точно) сложений и умножений комплексных чисел. [Указание. Рассмотрите произведение коэффициентов преобразования Фурье.] хь = хауз+ . +хаус — (хь»ау»-> + + х»-~ул»>).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
