Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 100
Текст из файла (страница 100)
Следовательно, ]г(бм...,б )! < А(]бг! — Аг) (]8~! — )У ) + ]5~ ](]эг! ]Ба! — ()уг]-)уз)... (]Е„]-4)). (К. А. ПеМ!!!о аобу. 3. Ырсоп, упб Ргас. Ее!гете 7 (1978), 193-195.] Ууркмечаниг. Указанная верхняя грань — наилучшая из возможных, так как для палпнома /(хп. ° .,х„) = П(х) — гь ! зг б Ям ! < Ус < 4), 1 < У < и) достигаетса равенство. Однако существует другой подход, при котором верхняя грань может быть значительно улучшена, хотя и в другом смысле. Пусть /г(х),...,х„) = /(хп....х„) и пусть / ег(х„.„...,х ) — любой ненулевой коэффициент при степени х) в /у(х„...,х~). Тогда можем положить г(у равным степени при х) в /у вместо (зачастую существенно большей) степени х в /. Например, можем положить гб = 3 и 4г = 1 в полииоме х~гхз — Зхгхг + хгг~+ б.
Это наблюдение гарантирует, что Аг + +4„< 4, когда каждый член / имеет общую степень < 6. Следовательно, вероятность в этих случаях равна при равенстве всех множеств Юу. Если она < -' и если /(хм..., х„) становится равным нулю для 50 случайно выбранных векторов (хг,.,.,х„), то /(хд,...,х„) тождественно равна нулю с вероятностью как минимум 1 — 2 з .
Более того, если /)(ху.....х„) имеет специальный вид х,"/.)~(ху+м..,,хн) с еу > О, можно получить 6) = 1, так как х должно быть равно О, когда /)~.)(хг+),...,х„) Ф О. Поэтому разреженные полиномы с только гл ненулевыми членами будут иметь )Уу < 1 для минимум и — 18 гп значений у. Применения этого неравенства для вычисления бо! и других операций над разреженными полинамами от многих переменных были введены Р. Циппелем (В.
Е!рре!) (1,есгнге №ссз уп Сошр. Яа'. 72 (1979), 216-226). Я, Т. Шварц (г. Т. Бс)пгагзз) (гАСМ 27 (1980), 701-717] привел дальнейшие расширении, включая устранение больших чисел с помощью модулярпой арифметики: если коэффициенты / целые, если Р является множеством целых чисел > 4 и если ]/(хп..., х„)! < Х для каждого хг б Ем то количество решений У(х) ...,х ) ьз О (шоб р) для р б Р не превышает 12.
(а) Для удобства опишем алгоритм только для А = (а, Ь) . Из наших посылок следует, что двбЩ~(Г) = бей(9«Г) > О, беб(9~) < бей(ь)«). Если с(ебЩг) О, то 1Гг представляет собой просто ненулевое рациональное число, так что мы считаем 1,~ = Я«/Щ. Б противном случае пусть 1~~ = аЯм + ьЯд + гм ()« = агги + Ыг««+ г«, где г~ и 㫠— рациональные числа; отсюда следует, что Ф(à — ()«~' = а(6)п(1 — 1Ри(г)+ ЬЮи(1 — 9««У) + г~(à — г«К У нас должно быть либо бейлам ) = баб(Я ~ ) -1, либо деб(Яш) = беЩ ~ ) -1. Б первом случае, рассматривая члены высшей степени, которые начинаются с а, имеем Йеб(1 ЬгЬг- Я«гЪ') < деб(Цм(Г); так что можем заменить Ц~ на 1гм, Я«на Ц«г н повторить процесс.
Подобным образом в последнем случае можно заменить (Ц~, Я«) на (Яи, Я««) и повторить процедуру. (Ь) Положим, что деб(1г) > деб(у), Если деб(В) > Йеб(Ъ'), то заметьте, что Ф (Г-яа у = 1Гг — (Я« — 1ьчьГ)Ъ' имеет степень, меньшую, чем деб(Ъ') < с(еб(1,)гВ), так что можно повторить процесс с Ь', замененнмм на В.
Получим В = 6)'У+ В', (г = (б) + Я')г'+ В', где йеб(В') < йеб(В), так что в конце концов решение будет получено. (с) Алгоритм из (Ь) дает ~'~ = И «+ В, деб(В) < беб(У«); в силу однородности В = 0 н «Г однородно. (б) Мы можем положить, что бей(1') < Йеб(сг). Если беб('г') = О, установить р1' +- У; в противном случае воспользуемся результатом (с) лля поиска (Г = Я1«, так что Я1'$' = Ъ'Яг; (Я1' — Щ) Г = О. Отсюда слелует, что ь)Г = У1г', так что можно установить П +- Р; У <- Ц и повторить процесс, Более подробная информация о рассматриваемом вопросе приводится в работе Р.
М. СоЬп, Ргос. СагнЬгЫбе РЫ). Яос. 57 (1961), 13-30, Существенно более сложная задача описания всех строковых полиномов, таких, что (г1' = УсГ, была решена Дж, М. Бергманом (С. М. Бегбшав) (РЬ. П. «Ьещз, На«та«4 Бштеш1«у, 1967). 18. 1Р.
М. СоЬп, Тгапзасбонз оГ гйе Атег. Ма«Ь. Яос. 109 (1963), 332-336.) С1. Установить н~ +- (ч, иа с- Н«, сг е- Ьц с«+- Ъ~, «~ «- ««е- кч е- ю« ~- 1, «( +- ««+- в( ~- ю«+- О, и е- О. С2. (Б этот момент выполняются данные в условии упражнения тождества и щ ог = и~о«; о« = 0 тогда и только тогда, когда нь м 0.) Если е« = О, алгоритм завершается с НОПД(Рм 1~«) = щ, НОЛК(Ъм ЪЬ) ы «((ч = -««Ъг. (Кроме того, в силу симметрии имеем НОЛД((Ь, (г«) = в«и НОПК((А, «Г«) = (Ашг ы -11«ю«) Сй. Найти «Г и В, такие, что е~ — — Цс«+В, где беб(В) < беб(с«).
(Имеем к~ Яс«+В) = и«в«, так что щВ = (и« вЂ” взбив« = В'е«.) С4. Установить (юм юг, юь ш«, «м ««, «(, ««, им н«, вм с«) е- (ю( — юл9, ю« — ю«Я, шм ю«, «'„««, «~ — Ц«'„«« -Щ, и« -и~1«, им о«, е~ -Яв«) н и <- и+ 1. Бернуться к шагу С2. 3 Это расширение алгоритма Евклида включает большинство особенностей, которые встречались в предыдуших расширениях алгоритма Евклида. Это приводит нас к новому пониманию уже рассмотренных частных случаев.
Для доказательства корректности алгоритма сначала заметим, что деб(о«) уменьшается на шаге С4, так что алгоритм обязательно завершается. По завершении алгоритма в~ представляет собой общий правый делитель 1'~ и У«, поскольку в~ щ = ( — 1) У~ и -ш«ог = (-1)" 1'«. Также, если 4 является любым общим правым делителем Р| и Ъз, он является и правым делителем «г К +««1 «ы ем Следовательно, щ = НОПД(гмЪз) Кроме того, если п«является любьгм общим левым кратным 1) и Ъ~„без потери общности можно считать, что щ = счР) м (Г«)г«, поскольку последовательность значений Ц не зависит от сч и 1Г«.
Значит, т = (-1)" (-а««()Ь) = (-1)" (к«««)Ъз кратно «(Ьм Нв практике, чтобы вычислить только НОПД(гм 1'з), можно опустить зычны~ение и, шз, шз, ю[, к4, зм яз, г'„гз. Эти дополнительные величины были добавлены к алгоритму, в первую очередь, чтобы более просто установить его корректность. Примгчеияг. Нетривиальное разложение строковых полиномов, таких, как приведенные в качестве примера в этом упражнении, могут быть найдены из матричных тождеств наподобие О) (! О) (1 О) (! — ) (! -Ь) (! — ) (О 1) ' поскольку эти тождества выполняются даже при некоммутативности умножения, например (або+ а+ с)(1 + Ьа) = (аЬ+ 1) (сба + а+ с). (Сравните это с континуантами нз раздела 4.5.3.) 19, [См. Епйепе СаЬеп, ТЬ4опе йв й!ошбзяз 1 (Рагм, 1914), 336-338.) Еслк такой алгорптм существует, то в соответствии с рассуждениями из упр.
18 12 является НОПД, Рассмотрим А и В как единую матрицу С размера 2п х п, первые и строк которой представлены строками А, а следующие п строк — строками В. Точно так же можно комбинировать матрипы Р и Я в матрицу Е размера 2п х и, а Х и У вЂ” в матрицу Я размера и х 2п. Требуемые условия теперь сводятся к двум уравнениям: С = В0, 11 = ЯС. Если можно найти целочисленную матрвпу Ь' размера 2п х 2я с детерминантам ш1, такую, что все последние и строк С ~С нулевые, то решением будут матрипы Е = (первые и столбцов П), гг = (первые п строк (г зс), Я = (первые и строк с з). поэтому можно использовать, например, следующий алгоритм (с т = 2п). Алгоритм Т (Триаигулярягацкл), Пусть С вЂ” целочисленная матрица размера гп х и. Данный алгоритм находит целочисленные матрицы С и У размера пз х из такие, что СУ = 1 и УС представляет собой треугольную матрицу (гакую, что элемент на пересечении з-й строки и У-го столбца матрицы 1'С равен нулю, если з > у), Т1.
[Инипиализация.[ Установить П г- У +- 1 (1 — единичная матрица размера из х гп) и Т г- С. (На протяжении всего алгоритма будут выполняться соотношения Т = УС н ПУ = 1.) Т2. [Итерапия по у.) Выполнить шаг ТЗ для у = 1, 2, ..., ппв(гп, и); затем прекратить выполнение апгоритма. ТЗ.
[Обнуление столбца 1.[ Не выполнять следующие действия или выполнять их до тех пор, пока Тп не станет равным нулю для всех 1 ),у, Пусть Тгп — ненулевой элемент (Ткп Тп и,, .., Т, ), имеющий наименьшее абсолютное значение, Переставим строки й и у' матриц Т н 1~ и переставим стсибцы Л и у матрицы Е Затем вычтем строку у из строки ! [То (Тгу) раз в матрицах Т н У и прибавим столыю же раз столбец з к столбцу у в матрице С для 1 < з < т. $ Для приведенного в упражнении примера алгоритм дает (з ) = (з з)(о г), (з г) = (з з)(е -)) (е -!) (г -з)(з з)+ (з о)(з,).
(Нв самом деле в этом частном случае НОПД будет являться люб ьг матрица с детерминантам ш1.) ЗО. Рассмотрите построение из уцр. 4,6.2-22, но такое, что р заменено малым числом г, 21, Для получения верхней грани положим, что алгоритм К используется только при гл — и < 1 и коэффициенты ограничены согласно (26) с ш = и. [Указанная формула дает практическое время вычисления, а не только верхнюю грань. Более подробную информацию можно найти в работе О. Е, Со1!шя, Ргос.
1968 Яппииег 1пяг. ав Яучпбо!!с Магйешайса! Сопзрпгайоп, еб!зш! Ьу КоЬегс С. ТоЬеу (1ВМ Рейеса! Зузсепм Сепгег, Лапе, 1969), 195-231.] 22. Последовательность знаков не может содержать лва идущих подряд нуля, поскольку из+((х) — ненулевая константа в (29). Кроме того, в качестве подпоследавательностн ие моя(ет встретиться "+, О, +" или "-, О, -". Формула е'(и, о) — К(и, Ь), очевидно, верна при Ь = о, тэк что ее необходимо проверить только при умличиваюшемся Ь. Полнномы и) (х) имеют конечное количество корней, н Г(и, Ь) изменяется только тогда, когда Ь встречается ялн проходит через такие корни.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
