Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 25
Текст из файла (страница 25)
[Указание. Используйте вспомогательные переменные и!, из, щ, о», ш,, шз, ш',, ш», гп гз. з, 'и з», значения которых представляют собой строковые переменные; начните с установки и! +- (?», и» з- (?з, о! +- Ъ~, из +- Ъз и на протяжении алгоритма поддерживайте выполнение условий з! 1'! + гзрз = и», ° Ф з»Ь! +з»»з оз ! и ш!о! — ш»вз = (-1) г)», -4о»с! + шзоз = (-1) Уз П!ш»+(?зш» = и», (?! ш', + П»и!» ш из, и»з! — изз! м (-1)"(?», -и»зз + изз,' = (-1)" (?», на и-й итерации, Это можно рассматривать, как "окончательное" расширение глгоритма Евклида.] 19. [Мбй] (Общие дели»пели квадратных матрац.) В упр. 18 показано, что концепция наибольших общих правых делителей может иметь смысл при некоммутптивном умно- жении. Докажите, что любме две целочисленные матрицы А н В размера и х и имеют накбольший общий правый матричный делитель В.
[Пргдловсеииг. Разработайте алго- рятм, на вход которого поступают матрицы А н В, а на выходе получаются целочисленные матрицы 11, Р, О, Л, У, где А = РВ, В = Ц.0 к В = ХА + КВ,] Найдите иаибштьшнй общий правый делитель ма»1»иц (з 4) и (» ! ). 20. [М40] Исследуйте точность алгоритма Евклида; что можно сказать о вычислении нанболыпего общего делителя полиномов с ковффициентами, представляющими числа с плавающей точкой? представляет собой строку 1»г = хг'г!"'"1, так что этот алгоритм включает в себя ющ частный случай алгоритм поиска бес( целых чисел.) ь 18.
[Мгг] (Алгоритм Евклида длл строковмв полиномое.) Пусть $'! и 0~ — строковые полиномы, не равные одновременно нулю и имеющие общее левое кратное (зто означает, что существуют не равные одновременно нулю строковые полиномы с?! н (?з, такие, что с?! У! = (?» Ъ~). Назначение данного упражнения — найти алгоритм для вычисления нх каи6олыаего общего правого дглителл НОПД(Ь», У») и наименьшего общего левого кроткого НОЛК(И, Ъг). Этн величины определяются следующим образом: НОПД(У», $~з) является обшнм правым делителем Р! и $~ (т. е. Ь! = И"»НОПД()г», зз) и гз = И'зНОПД(1'», 1'з) для некоторых 1»'! и 1»з), и любой общий правый делитель Ъ'! и $р является правым делителем НОПД(Ь!, Уз); НОЛКЯ, Рб) = й! Ъд = й» зз для некоторых й! и йз, и любое обвзее левое кратное У! и Ъз является левым кратным лля НОЛКЯ, 'гз).
Например, пусть (?! = абббаЬ+ аббпб — ббаЬ+ аЬ вЂ” 1, $'! = ЬабаЬ+ абаб+ аЬ вЂ” Ь! (?» = аЬЬ+ аЬ вЂ” Ь, 1з = ЬаЬЬаЬаЬ+ ЬаЬпбаЬ+ ЬаЬаЬ+ аЬаб — Ьпбб — 1. Тогда имеем П»Ъ! = (?»Ъа = аЬЬЬаЬЬаЬаЬ+ аЬбпЬЬпЬпЬ+ пбббаЬпЬпЬ+ пЬЬабабаб- ЬбаЬЬабаЬ+ аЬЬЬпбаЬ вЂ” 6ЬаЬаЬпЬ+ упббабпб — аЬЬЬабб+ пбабаб — аббабб- Ьбаба Ь - баЬпЬ+ Ьбпбб- абЬ -аЬ+ Ь, Длв этих строковых пслнномов можно показать, что НОНА, 1 з) т аЬ+ 1 н НОЛКЯ, 1з) = с?»Ь!. Алгоритм деления из упр. 17 можно сформулировать так! есвн 1»! и 1» явлаютсв строковыми полнномами, причем $'з;г О, и если с?! -,Б 0 н (?з удовлетворяет соотношению П»1! = с?з'гз, то существуют строковые полииомы О и В, такие, что 21.
[М35[ Докажите, что время вычисления, требуемое штгоритмом С для поиска йсб двух полиномов и-й степени над кольцом целых чисел, составляет О(н~(1ойХп) ), если коэффициенты полннома ограничены по абсолютному значению величиной Х. 22. [МЯЛ) Докажите теорему Штурма. [Указание. Некоторые последовательности знаков невозможны.) 23.
[Мзх] Докажите, что если и(х) в (29) имеет г1ей(и) действнтелыгык корней, то абеб(кг ы) = бей(и ) — 1 для 0 < у < й. 24. [МИ) Покажите, что (19) упрощается до (29) и (23) упрощается до (24). 25. [ЛЩ [ (В. С Браун (Ж. 8. Вгони).) Докажите., что все полиномы иг(х) в (15) лля у > 3 кратны бсг1(4(к), 4(г )), и поясните, как в соответствии с этим можно улучшить алгоритм С. ь 26. [Мйб) Назначение этого упражнения- — найти аналог для полиноиов того факта, что цепная дробь с целымн положительными элементами дает наилучшее приближение действительных чисел (упр.
4.5,3-42). Пусть и(х) н с(х) — полиноыы над полем с бей(к) > бей(с) и пусть аг(х), аг(х), ...— частные полиномы, образующиеся в результате применения алгоритма Евклида к и(х) н с(х), Например, посэедовательность частных в (5) н (б) представляет собой 9хг+7, 5хг+5, бхг+5хг+бх+5, 9х+12. Необходимо показать, что представления р„(х)/4 (х) цепной дроби //пг(х), пг(х),...// явлшотся "наилучшими приближениявги" малых степеней рациональ.- ной функции с(х)/и(х), где р (х) =К д(аг(х)„,а„(х)) н 4„(х) жК„(аг(х),...,а (х))— континуанты из 4.5.3-(4). По определению ро(х) = 4-1(х) = 9, р-1 (х) = Чо(х) = 1 Докажите, что если р(х) н д(х) являются полиномами, такимгг, что деб(9) < г(ей(д„) и деб(ри-ес) < бей(р -гк-4„-ге) для некоторого и > 1, тор(х) = ср г(х) и о(х) = се -1(х) для некоторой константы с.
В частности, каждый 4„(х) является полнномом, "разбивающим запись" (гесого-ЬгеаЫпй) в том смысле, что не существует ненулевого полнноиа 4(х) меныпей степени, такого, что для любо~о полинома р(х) полипом р(х) и(х) — 4(х) с(х) имел столь же малую степень, что н р„(х) и(х) — 4„(х) с(х). 27. [Мйз) Предложите путь ускорения деления и(х) на и(х), если заранее известно, что остаток будет нулевым. е4.6.2. Разложение полииомов нв множители Рассмотрг(м теперь задачу ие только поиска наибольшего общего делителя двух или более полиномов, но и разлоогссмил полииомов. Разложение по модулю р.
Как и в случае целых чисел (разделы 4.5.2 и 4.5.4)„ задача разложения представляется существенно сложнее поиска наибольшего общего делителя. Однако разложение полиномов по модулю некоторого простого целого числа р не настолько сложно, как кажется. Гораздо проще найти множители проязволького полинома степени и по модулю 2, чем использовать любой известный метод для поиска множителей произвольного и-битового двоичного числа. Эта неожиданная ситуация является следствием поучительного алгоритма разложения, открытого в 1967 году Элвином Р. Берлекампом (Е)эгуп В.
Вег!е(гашр) [Ве)) Яузгеггг Тес(гпгса) Х 46 (1967), 1853-1859). Пусть р — простое число; все арифметические операции над полиномами в приведенном далее материале выполняются по модулю р. Предположим, задан полипом и(х), коэффициенты которого выбраны из множества (0,1, ...,р — 1), Мы можем считать, что и(х) нормирован.
Наша цель — выразить а(х) в виде п(х) =р (х)"" р.( )' (1) где р»(х), ..., р,(х) — различные нормированные неприводимые полиномы. В качестве первого шага можно использовать стандартную технологию определения, не является ли какой-либо показатель степени ем ..., е, больше единицы. Если н(х) — м х + ' ' ' + пе — О(х)~ге(х) то производная (найденная так, как обычно, но»ю модулю р) будет равна и'(х) = пи„х ~ + . + и» = 2с(х)с'(х)ш(х) + п(х)зв'(х), (3) а зто выражение кратно с(х).
Значит, наш первый шаг в разложении и(х) должен состоять в поиске ясс)(и(х), и'(х)) = И(х). (4) Если Н(х) равно 1, то, как мы только что убедились, и(х) свободен ош кеафагпов, т. е. представляет собой произведение различных простых р~ (х)... р„(х). Если п(х) не равно 1 и фх) ~ и(х), то с((х) является собственным множителем и(х); соотношение между множителями Н(х) и множителями и(х)/п(х) уткоряет процесс разложения для этого случая (см. упр, 34 и 36).
И наконец, если И(х) = п(х), то необходимо, чтобы и'(х) = 0; следовательно, коэффициент н» прн х» ненулевой только тогда, когда» кратно р. Это означает, что и(х) может быть записан как почином вида и(х"). В таком случае имеем ( ) = (х') = ( ( О'.
(3) Процесс разложения может быть завершен нахождением неприводимых множителей и(х) и возведением их в степень р. Тождество (5) может показаться читателю несколько странным, однако это важный факт, лежащий в основе алгоритма Берлекампа н других методов, которые мы обсудим чуть позже. Его можно доказать следующим образом.
Если щ(х) и сз(х) — некоторые полнномы по модулю р, то (щ (х) + вт (х)) = щ (х)г + (г) и» (х)" ~ цт(х) + " . + („~,) гч (х) пз(х)~ ' + н»(х) г = п»(х)" +гя(х)г, Эти замечания показывают, что задача разложения сводится к задаче разложения свободных от квадратов полиномов. Таким образом, положим, что и(х) = р»(х)рз(х)...р,(х) является произведением различных простых сомножителей. К какой хитрости следует прибегнуть, чтобы суметь найти р.
(х), если дан только и(х)2 Идеи Берлекампа поскольку биномиальные коэффициенты (~'), ..., ( г,) кратны р. Далее, если а— произвольное целое число, имеем аг = а (по модулю р) согласно теореме Ферма. Таким образом, когда и(х) = с„,х"' + с »х"' ' + + еш находим, что с(х)г = (ю~х-)л + (О,. !х--') + " + (гв)г = и х ~+с, ~х~"' ~~+ .
+гв = с(хг). состоит в применении китайской теоремы об остатках, которая справедлива для полиномов так же, как и для целых чисел (см. упр. 3). Если (вм вв,..., в„) является произвольным набором из г целых чисел по модулю р, из китайской теоремы об остатках вытекает, что существует единственный полином е(х), такой„что е(х) ке в1 (по модулю р1(х)), ..., и(х) гя в, (по мсдулю р„(х)), бей(е) < бей(рс) + с1ей(рв) + " + де8(р,) = бей(и). Запись "й(х) ьз Ь(х) (по модулю )'(х))", появляющаяся здесь, имеет тот же смысл, что и "й(х) ьй Ь(х)(по модулю 7(х) и р)" в упр. 3.2.2-11, поскольку мы рассматриваем полиномиальную арифметику по модулю р.
Полипом е(х) в (7) предоставляет способ получения множителей и(х), так как при г > 2 и в1 ~ зв мы получим йсо(и(х), е(х) — »1), делящийся на р1 (х), но не на рт(х). Поскольку зти наблюдения показывают, что информацию о множителях и(х) можно получить из соответствующих решений и(х) (7), проанализируем (7) более тщательно, Во-первых, можно заметить, что полипом и(х) удовлетворяет условию е(х)" ав в~~ = ву гй е(х) (по модулю рв(х)) для 1 < у < г. Таким образом, и(х)» вт и(х) (по модулю и(х)), бей(и) < бей(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
