AOP_Tom2 (1021737), страница 147
Текст из файла (страница 147)
з Если М и?»' — мультимножества, соответствующие т и п, то какие мультимножества соответствуют бед(т, и), !сш(т, и) и тп? Ь) Каждый нормированный полинам у(х) над полем комплексных чисел естественным образом соответствует мультимножеству его "коРней"; имеем ?(х) = Псах(х»). Если ? (х) и д(х) — полиномы, соответствующие конечным мультимиожествам Г и С комплексных чисел, то какие полиномы соответствуют Р!к С, Р1! С и Р П С? с) Найдите как можно больше интересных соотношений, вьшачняющихся при приложении к мультимножествам операций ЬЬ О, О. 20. [МЗ0] Какие последовательности Я, и Мо (О < 1 < г, 0 < З < !) появляются при структурной лекомпознцни Хансена звездных цепочек (а) типа 3 и (Ь) типа 5? (Шесть "типов" цепочек определены в доказательстве теоремы В.) ° 21.
[Муб] (В. Хансен (%. Нюзвеп).) Пусть д — некоторое натуральное число. Найдите значение и, такое, что !(и) < !*(и) — Ф 22. [МЗО] Докажите, что аддитивная цепочка, построенная в доказательстве теоремы Р, является !е-цепочкой. 23. [М20] Докажите неравенство Брауэра (50), ь 24. [МЗЗ] Обобщите доказательство теоремы С, чтобы показать, что !" ((В" — 1)/( — 1)) < (и — 1) !е(В) + !е(п) для любого целого В > 1; докажите также, что !(2 " — 1) < !(2 — 1) + тп — т+ !о(п). 25. [20] Пусть у является дробью 0 < у < 1, выраженной и двоичной системе счисления как у = (.А 0ь)э Разработайте алгоритм для вычисления х" с использованием операций умножения н извлечения квадратного корня.
ь 20. [МЗЗ] Разработайте эффективный юпоритм, вычисляющий и-е число Фибопаччи Р» по модулю т по данным большим целым числам п и т. 27. [МЗ1] (А. Фламменкамп (А. Р!ашпгеп!сашр) ) Чему равно наименьшее и, для которого каждая аддитивная цепочка содержит как минимум шесть малых шагов? 25. [НМЗЗ] (А. Шенхаге (А. БсЬопЬабе).) Назначение данного упражнегшя — дать ясное и короткое доказательство того, что !(и) > Л(п) + 15 п(п) — С(!об !об(п(п) + 1) ). а) Егтн х = (хь ха.х ~ )г и у = (уь... уе.у ~...)э представляют собой действительные числа в двоичной записи.
то введем обозначение х С у, если х, < у, для всех 1 Приведите простое правило для построения наименьшего числа в, обладающего тем свойством, что из х' С х и у' С у вытекает, что х'+ у' С х. Обозначив такое число как хзУу, докажите, что и(х1ту) < п(х) + п(у). Ь) Дана произвольная авдитивная цепочка (11) с г = 1(п) и погледовательность»?е»»?»,... ..., »?„определенная» как в (35). Определим последовательность Ае, А»,..., А, таким образом: Ае = 1; если а, = 2а, », то А, = 2А, », в противном случае, если о, = а, + аь для некоторых О < к < б <», А, = А»» и(А, »/2е» "").
докажите, что эта последовательность '"покрывает" данную цепочку в том смыате, что а, С А, длн О < 1 < г. с) Пусть б — натуральное число (которое будет выбрано позже). Назовем неудванвающий шаг а» = а» + аь небольшим шагом, если 4» — »?ь > б, в противном случае назовем его близким шагам*. Пусть Ве = 1; В; = 2В» и если а, = 2а, », В, В,-»'Р(В, »/2~г ~'), если а, = а, +ае — небольшой шаг, В, = р(2В, ») — в противном случае, где р(х) — наименьшее число р, такое, что х/2' С р для О < е < б. Покажите, что А, С В, и»»(В,) < (1 + бс;)2к для О < 1 < г, где Ь, н с, означают соответственно число небольших шагов и число близких шагов < ь [Указание.
Покажите, что единицы в В; появляются в последовательных блоках размером > 1+ бс,.] Й) Теперь 1(п) = г = Ь„+ с, +»4, и и(п) < и(В„) < (1+ бс,)2м Объясните, квк выбрать б, чтобы получить неравенство, упомянутое в начале этого упражнения. ]Указание. См. (16); обратите внимание на то, что п < 2'пе" для некоторого и < 1, зависящего от б.] 29. (Мбр] Справедливо ли и(п) < 26"1 щ"1 для всех натуральных чисел и? (Если справедливо, то получим нижнюю границу 1(2" — 1) > и — 1+ (16п]; см.
(17) и (49).) 30. ]20] В цепочке со слов»гением и емчишанием вместо правила (2) имеется правило а, = а, х ае. Воображаемый компьютер, описанный в тексте раздела, оснащается новой операцией — 363. (На практике это соответствует тому, что прн вычислении х" используются и умножение, и деление.) Найдите такую цепочку для некоторого и, имеющую менее 1(п) шагов. 31. (Мбб] (Д. Г. Лехмер (П.
Н. 1еЬптег).) Исследуйте задачу минимизации ед+ (г — 9) в адднтнвной цепочке (1), где 9 — число простых шахов, в которых а; = а, » + 1, пр»и данном малом положительном весе е. (Эта задача ближе к реальности для многих вычислений х", если умножение на х проще, чем общее умножение; см. приложения в разделе 4.6.2.) 32. ]МЗО] (Э. Ч.
Яо (А, С. Уао), Ф. Ф. Яо (Е. Е. Уао) и Р. Л. Грэхем (В. Ь СгаЬап»).) Назначим "цену" а»ае для каждого шага а, = а» + аь аддитивной цепочки (1). Покажите, что бинарный метод "слева направив приводит к цепочке миннмавьной общей стоимости для всех наеурвльных и. ЗЗ. ]!5] Сколько алдитивных цепочек длиной 9 имеет (52) в качестве приведенного ориентированного графа? 34. (МЗЗ] Бинарная алдитнвная цепочка для и = 2'е + + 2", когда ео » . е» > О, представляет собой 1,2,...,2'е "»,2'е '» + 1,...,2" "-1-2" ",2'е "+2" "+1,, п.
Это соответствует методу "Б и Х", описанному в начале этого раздела, в то время как алгоритм А соответствует аддвтнвной цепочке, полученной посредством сортировки двух последовательностей — (1,2,4,...,2'е) и (2"-' + 2",2"-' + 2"-' + 2",...,и) — в порядке возрастания. Докажите или опровергните следующее: каждая из этих аддитивных цепочек дувльна по отношению к другой. 35. ]М27] Как много аддитивных цепочек без шагов, которые не используются, эквивалентны каждой из алдитивных цепочек, обсуждавшихся в упр.
34, если ее > е» + 1? ° 36. (25] (Э. Г. Штраус (Е. О. Бсгаиэ).) Найдите способ вычисления обобщенного монопома х",'хт'... х„", за не более чем 2Л(шах(п», пю ..,, и )) + 2 — ш — 1 операций умножения. е В орвгквэле — "Ьаьу егер" н "с1оэе втер" соответственно. — Прим. перев. 37. [!?М30] (Э, Ч.
Яо.) Пусть Цим, л„) — длина наикратчайшей вддитивной цепочки, которая содержит т чисел и~ < < и . Докажите, что Цим..., и„,) < Л(п ) + тЛ(п,)/ЛЛ(и, ) + 0(Л(л,)ЛЛЛ(и,„)/ЛЛ(и )~), тем самым обобщая (23). 33. [М47] Чему равно асимптотическое значение Ц1,4,9,, т ) — т при т -+ оо в обозначениях из упр. 37? ь 39. [М25] (Х. Оливос (У Ойтов), 1979.) Пусть Ц[ип ла..., и„,]) — минимальное количество умножений, требующихся для вычисления мононома х",'х~э... х" в смысле упр. 36, где каждое л, — натуральное. Докажите, что эта задача эквивалентна задаче из упр.
37, показав, что 1([лы пм, и ]) = Цл,, лм, .., и„,) + т — 1. [Указание. Обобщите ориентированный граф, построив рассмотренный граф с более чем одной исходной вершиной.) ь 40. [М21) (Х. Оливос.) Обобщая метод множителя и теорему Е, докажите, что Цт~ль + + тип) < Цтм...,та) + Цлм...,Ш) +1 — 1, где Цим..., и~) определено в упр. 37. 41. [М40) (П.
Давни (Р. Пожпеу), Б. Леон (В. 1еопб) и Р. Сети (К. Бесй!).) Пусть С— связный граф с и вершинами (1,..., и) и т ребрами, где ребра объединяют и, с е, для 1 <,!' < т. докажите, что ц1,2,...,2'",24'*'+2""'+1,...,2~" +2~" +1) = Ал+т+?с для всех достаточно больших А, где й — минимальное число вершин в покрытии вершин для С (т. е.
множество, содержащее либо и„либо еэ для 1 < У < т). 42. [М50] Справедливо ли Ц2" — 1) < и — 1 + Цл) для всех натуральных и? Всегда ли выполняется равенство? Выполняется ли Цл) = 1е(и)? 4.6.4. Вычисление полиномов Так как нам известен эффективный метод вычисления палинома специального ви- да х", рассмотрим общую задачу вычисления полинома л-й степени п(х) = п„х" + пи гх" ' + ° + игх+ иоэ ии ф О, (1) для определенных значений х.
Такая задача часта возникает на практике. Затем сканцентрируем внимание на минимизации числа операций, требуемых для вычисления полиномов на компьютере, в идеальном случае предполагая, что все арифмехические операции точны. Чаще всего полнномы вычисляются с использованием арифметики с плавающей точкой, которая не является точной, и различные схемы для оценки обычно дают различные ответы. Численный анализ достигаемой точности зависит от коэффициентов рассматриваемого полинома, но в данной книге он не проводится; читателю следует внимательно исследовать точность любых вычислений, полученных с использованием арифметики с плавающей точкой. В большинстве случаев будут описаны методы, вполне удовлетворительные с точки зрения численного анализа, на будет также рассмотрено достаточно много плохих примеров.
[См. работу %еЪЪ М!!!ег, В1СОМР 4 (1975), 105-107, в которой приведены обзор литературы по устойчивости быстрых вычислений полинома и доказательство, что определенные виды численной устойчивости не могут быть гарантированными для некоторых семейств быстродействующих алгоритмов.] Во всем этом разделе будем считать переменную х просто числом. Но важно помнить, что большинство рассматриваемых методов действительны также, когда переменные являются более сложными объектами, такими как числа с многократной точностью, полинамы и матрицы. В подобных случаях эффективная формула приводит даже к большему выигрышу, в особенности, когда можно уменьшать количество операций умножения.
Начинающий программист, скорее всего, вычислит полипом (1) способом, который прямо соответствует его традиционному виду; сначала вычислит и„х", затем— и„-гх" ', ..., и,х и наконец суммирует все члены (1). Но даже если использовать эффективные методы из раздела 4.6.3 для вычисления степеней х этими методами, результирующее вычисление излишне медленно, кроме случая, когда почти все коэффициенты ил равны нулю. Если не все коэффициенты равны нулю, то очевидной альтернативой должно быть вычисление (1) справа натево посредством вычисления значений х" и илх" + .
+ иэ для й = 1,..., п. Такой процесс включает 2п — 1 операций умножения и п операций сложения и, возможно, потребует дополнительных команд для сохранения промежуточных результатов в памяти и их извлечения из памяти. Правило Горнера. Одной из первых забот начинающего программиста обычно является изучение элегантного способа перестройки этих вычислений следующим образом: и(х) = (... (и„х+ и„,)х+. )х+ иа (2) (начать с и„, умножить на х, добавить и„м умножить на х, ..., умножить на х, добавить ие). Эту модель вычисления обычно называют "правило Горнера" (либо "схел1а Горнера".— Прим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
