AOP_Tom2 (1021737), страница 133
Текст из файла (страница 133)
[МЯЯ[ Мы видели, что алгоритм Евклида 4.5.2А для целых может быть преобразован в алгоритм для поиска наибольшего общего делителя полиномов, Можно ли аналогичным путем преобразовать бинарный алгоритм поиска боб 4.5.2В в алгоритм, работающий с полнномами? Т. [М10[ Чему равны обратимые эдементы в области всех полиномов над областью единственного разложения Я? 8. [МЯЯ) Покажите, что, если полипом с целыми коэффициентами неприводим над областью целых чисел, он неприводим и при рассмотрении его над полем рациональных чисел, 9. [МЯ5[ Пусть и(х) и е(х) — примитивные полиномы над областью единственного разложения Э'.
Докажите, что и(х) и е(х) взаимно просты тогда и только тогда, когда полиномы (?(х) и Г(х) над Я таковы, что и(х) И(х) + (?(х) с(х) — полипом нулевой степени. [Укаэанне. Расшнрьте алгоритм Е так, как алгоритм 4.5.2Л был расширен в упр. 3.) 19. [МЯЯ[ Докажите, что полиномы над областью единственного разложения образуют область единственного разложения. [Указание. Используйте результат упр. 9 для того, чтобы показать, что имеется не более одного возможного разложения.[ 11. [МЯЯ[ Какие строки появилнсь бы в табл. 1, если бы последовательность степеней была 9, б, 5, 2, — оо, а не 8, 6, 4, 2, 1, О? ° 12. [МЯ4] Пусть из(х), из(х), пз(х), ...— последовательность полнномов, полученная во время работы алгоритма С.
Матрица Сильвестра представляет собой квадратную матрицу, построенную из строк с А, г по Ао и с В, з по Ве (в обозначениях, аналогичных обозначениям для табл. 1). Покажите, что если из(х) и из(х) имеют общий множитель положительной степени, то детерминант матрицы Сильвестра равен нулю, н обратно: покажите, что если для некоторого 5 беб(из) = О, то детерминант матрицы Сильвестра ненулевой (покажнте это, выведя формулу для его абсолютного значения через Я(п,) и беб(и,), 1 ( з' < 9). 13.
[МЯЯ[ Покажите, что при бз = бз = = б» з = 1 старший коэффициент 4 примитивной части боб(и(х),е(х)) входит в показанную в (28) последовательность полиномов, которая получается с помощью алгоритма С. Каково поведение для общего случая 5,? 14. [МЯО[ Пусть г(х) — псевдоостаток от псевдоделения н(х) на е(х), Покажите, что если беб(и) > деб(е) + 2 н Оеб(е) > беб(г) + 2, то г(х) кратен Я(о). 15. [МЯО) Докажите неравенство Адамара (25).
[Указание. Рассмотрите матрицу ААт.[ ь 16. (Мйк) Пусть |(хп...,х„) — полипом от многих переменных, не равный тождественно нулю, н пусть г(ЯИ...,5„) — множество корней (хм..., х„) уравнения 1(хп...,х ) = О, таких, что х~ б Ям..., х» б о . Если степень / не превышает А, < ~Я,) для переменной х;, докажите, что Следовательно, вероятность нахождения корня случайным образом, приближается к нулю при увеличении множеств 51. (Это неравенство имеет множество приложений при разработке алгоритмов рандомизации, так как предоставляет хороший способ проверки, является ли сложная сумма произведений сумм равной нулю без раскрытия всех сомножителей.) 17. (М32) (Алгоритм П.
М. Кока (Р. М. Собп) деления строковых поли»омов.) Пусть А является алфавитом, т. е. множеством символов. Сшрока а над алфавитом А представляет собой последовательность из и > О символов а = аы .. а, где каждое аз б А. Длина и, записываемая как (и), равна количеству символов п. Строковым полономом над алфавитом А является конечная сумма П = 2 гг аю где каждое гь является ненулевым рациональным числом, а каждое пь — строкой над элфвлитом А; мы полагаем, что и, ф пь при 1' ф К.
Сшепень У, бей(У), определяется как -оо, если У = О (т. е. если сумма пуста); в противном случае г(еб(и) = шах(пь). Сумма и произведение строковых полиномов определяются очевидным образом. Так, (2, г,пз)(Я вэба) = 2, г,выл~ба, где произведение двух строк получается путем их простого соединения;после этого они становятся членами суммы. Например, если А = (о, 6), У = аЬ+ Ьа — 2а — 2Ь и Г = а+ Ь вЂ” 1, то Оеб(У) = 2, бей(Г) = 1, У = па+ аЬ+Ьа+ЬЬ вЂ” 2а — 2Ь+1 и Г~ — П = аа+ЬЬ+1. Ясно, что г1ея(ЬГГ) ж пей((/)+бей(Г) и деб(1г+Г) < шах(пей(П), йей(Г)) с равенством в последней формуле при цей(сГ) эч бей(Г), (Строковые полиномы могут рассматриваться как обычные полиномы от многих переменных над полем рациональных чисел, но переменные не коммушашпвнм относительно умножения.
На математическом языке множество строковых полиномов с определенными здесь операциями представляет собой»свободную ассоциативную алгебру", порожденную А над полем рациональных чисел.) а) Пусть Яц 1яз, У и à — такие строковые полиномы с деб(У) > бей(Г), что г(еб(1»1~ П вЂ” ь)зГ) < бебЯ~У). Разработайте алгоритм поиска строкового полинома ьг, такого, что бей(У вЂ” 1яГ) < бей(П), (Следовательно, если даны У и Г, такие, что (~~Ьг = 'ызГ+ гс и деб(гс) < беб(С~Ьг) для некоторых я~ и б)ы то существует решение для этих условий при Ц~ = 1.) Ь) Даны строковые полиномы Ьг и 1» с деб(Г) > деб(Щ У- 1яз Г) для некоторых Ц~ и ггь Покажите, что результат п. (а) может быть улучшен для поиска частного й, такого, что П = сГГ+ В, г(еб(В) < йеб(1').
(Это аналог (1) для строковых полиномов; в п. (а) показано, что можно достичь Оеб(1ь) < Оеб(У) при более слабой гнпогезе.) с) Однородкыб полинам — это полинам, все члены которого имеют одну и ту же степень (длину). Пусть (и, сГг, Гц Гг являются однородными строковыми полиномами с счГг = УгГз и бебЯ) > йеб(1г).
Покажите, что существует однородный строковый полипом ЬГ, такой, что Уг = УгЬГ и Г~ = И'г. б) Даны однородные строковые полиномы Ьг и Г с УГ = Г(Г. Докажите, что имеется однородный строковый полипом И', такой, что П = гИ"", Г = зИг" для некоторых целых т, и и рациональных чисел г, з. Разработайте алгоритм для вычисления И', имеющего наибольшую возможную степень. (Этот алгоритм интересен, например, когда Ьг = а и Г = б — строки, удовлетворяющие соотношению а;3 = Дп, тогда И'— просто некоторая строка ч, Когда П = з'" и Г = х, решение с наибольшей степенью Ъ1= ЯУ2+В, где!!еб(В) < с)ея(У2), Отсюда легко вывести, что Я и Я определяются однозначно; они не зависят от данных П1 и 612. Кроме того, результат обладает право-левой симметрией в том смысле, что 612 = 6119+ В', где с(еб(В') = с!ей(6!1) — бей(12) + с)Еб(В) < с)ей(ь!1).
Покажите, что этот элгоритм для деления может быть расширен до алгоритма, вычисляющего НОЛК(У1, Уг) н НОПД(У1, Ъг); фактически расширенный алгоритм находит строковые полиномы Е1 и Ег, такие, что Е1 У1 + Егер! = НОПД(У1, Ъг). (Указание. Используйте вспомогательные переменные ис, иг, ос, иг, юс, юг, со„юг. 21, 22, 21 и 2, значения которых представляют собой строковые переменные; начните с установки ис +- Р1, иг +- 6!2, ос с — 11! ог +- ! г и на протяжении алгоритма поддерживайте выполнение условий г111 + х21'2 о1 г111 + 22!'2 = и2, сосо! — сосо! = (-1)" Ъс, ! л со2и1 + сого2 = ( 1) 12 П +бг !' 11о1 + П21о2 и2 и... -„.', =(-1)"ЬГ„ — и!ге+иге! = ( — 1) С'г, на и-й итерации.
Это можно рассматривать, как "окончательное" расширение алгоритма Евклида.) 19. [МЯР) (Общие делители квадратных моосрии.) В упр. 19 показано, что концепция нанболыпих общих правых делителей может иметь смысл при некоммутативном умно- жении. Докажите, что любые две целочисленные матрицы А и В размера и х п имеют наибольший общий правый матричный делитель Р. (Вредлооссение. Разработайте алго- ритм, на вход которого поступают матрицы А н В, а на выходе получаются целочисленные матрицы Р, Р, Я, Х, У, где А = РР, В = ОР и Р = ХА+ 1'В.) Найдите наибольший общий правый делитель матриц (1 с) и (с 2).
20. (ЛЦО) Исследуйте точность алгоритма Евклида: что можно сказать о вычислении наибольшего общего делителя полиномов с коэффициентами, представляющими числа с плавающей точкой? представляет собой строку И' = хгыС~л1, так что этот алгоритм включает в себя как частный случай алгоритм поиска бес! целых чисел.) ° 19. (Мйд) (Алгоритм Евклида длл строковых полиномов.) Пусть Ъс и !'2 — строковые полиномы, не равные одновременно нулю и имеющие общее левое кратное (это означает, что существуют не равные одновременно нулю строковые полиномы Ц и 6!2, такие, что (22!'1 = П212).
Назначение данного упражнения — найти алгоритм для вычисления их наибольшего общего правого делителя НОПД(У1, 1'2) н наименьшего общего левого крап!ного НОЛК(Ъ1, 1'2). Эти величины определяются следующим образом: НОПД(Ъ1, Уг) является общим правым делителем Ъ1 и Ъг (т. е, Ъс = !У1НОПД(У1, Ъг) и Ъг = ЪУгНОПД(У1, Ъг) для некоторых И'1 н И'2), и любой общий правый делитель Ус и Ъг является правым делителем НОПД(У1, Ъг); НОЛК(Ъ1! Уг) = Е1 !'1 = Е2У2 для некоторых Ес и Ег, и любое общее левое кратное У1 и Уг является левым кратным для КОЛК(У1, 1'2).
Например, пусть Пс — — аЬЬЬаб + аЬЬаЬ вЂ” ЬЬаб + аЬ вЂ” 1, Ус = ЬабаЬ+ аЬаЬ + аЬ вЂ” 6; сгг = аЬЬ+ аЬ вЂ” Ь, Ъг = ЬаЬЬабаЬ+ ЬаЬоЬаЬ+ ЬаЬаЬ+ аЬаЬ вЂ” ЬабЬ вЂ” 1. Тогда имеем (2!У! = Пг Уг = аЬЬЬаЬЬабаЬ+ аЬЬаЬЬаЬаб+ оЬЬбабаЬаЬ+ аЬЬаЬобаЬ- ЬЬаЬЬаЬаЬ+ абЬЬаЬаЬ вЂ” ЬЬабаЬаЬ+ 2аЬбаЬаЬ вЂ” аЬЬЬабЬ+аЬаЬаЬ вЂ” аЬЬаЬЬ вЂ” ЬЬаЬаЬ вЂ” баЬаб+ЬЬаЬЬ вЂ” аЬЬ вЂ” аЬ+Ь. Для этих строковых полиномов можно показать, что НОПД(Ъ'1, Ъг) = аЬ+ 1 и НОЛК(У1, Ъг) = 611Ъ1, Алгоритм деления из упр. 17 можно сформулировать так: есви Ъс н Ъг являются строковыми полниомами, причем Уг ~ О, и если с!с ф О и (!2 удовлетворяет соотношению Р1 Ъ1 = с!2 У2, то существуют строковые полиномы Я и В, такие, что 21.
[Мхб] Докажите, что время вычисления, требуемое алгоритмом С для поиска бей двух полиномов и-й степени нэд кольцом целых чисел, составляет 0(п~(1ой ггп) ), если коэффициенты полинома ограничены по абсолютному значению величиной М. 22. [Мху] Докажите теорему Штурма. [Указание. Некоторые последовательности знаков невозможны.] 23. [Мйй] Докажите, что если и(х) в (29) имеет йек(и) действительных корней, то йеб(и +~) = йее(в,) — 1 для 0 < / < 1> 24. [Мй!] Покажите, что (19) упрощается до (20) и (23) упрощается до (24). 25.
[Мхе] (В. С. Браун (Ъг'. 8. Вгони) ) Докажите, что вге пааиномы и,(х) в (16) для 5 > 3 кратны йсй(4(и), 4(ю)), и поягните, как в соответствии с этим можно улучшить алгоритм С. ь 26. [МЯ5] Назначение этого упражнения — найти аналог для полиномов того факта, что цепная дробь с целыми положительными элементами дает наилучшее приближение действительных чисел (упр. 4.5.3-42). Пусть и(х) и е(х) — полиномы над полем с йей(и) > йей(е) и пусть а~ (х), аг(х),...— частные полиномы, образующиеся в результате применения алгоритма Евклида к и(х) и с(х). Например, последовательность частных в (5) и (б) представляет собой 9х +7, 5х + 5, бх +5х +Ох+5, 9х+12. Необходимо показать, что представления р„(х)/д„(х) цепной дроби //аг(х),аг(х),... // являются "наилучшими приближениями" малых степеней рациональной функции о(х)/и(х), где р„(х) = К„г(ог(х),..., а„(х)) и д„(х) = Кь(ог(х),..., а (х))— континуанты из 4.5.3 — (4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
