Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 24
Текст из файла (страница 24)
Например, если последовательность знаков представляет собой О, +, —, —, О, +, +, —, получим Р(и, а) = 3. Теорема Штурма утверждает, что колпчество корней и(х) в пнтервале а < х < Ь равно Ъ (и, а) — 1'(и, Ь). Доказательство этого факта на удивление коротко (см. упр. 22), Хотя алгоритмы С и Е интересны, история на них не заканчивается. Важные альтернативные пути вычисления йсб пачиномов нед целыми числами будут рассмотрены в конце раздела 4.6.2.
Имеется также общий алгоритм для вычисления детерминанта, о котором можно сказать, что он включает в себя алгоритм С в качестве частного случая (см. Е. Н. Ввгщэв, МагЬ. Совр. 22 (1968), 565-578), Ф В четвертолг нздвнтг этой кнпгн я намерен переделать магерпал настоящего раздела, уделив достойное вннмвнпе как исследованиям детермннангов в 19 веке, твк и работе 15'.
НвЫсЫ, Сопцп. Мвй. Не1гебс! 21 ('1948), 99-116. Про" восходное обсуясденне последней дано в работе К. Воов !и Сотпрцгщб, Бцрр1етепг 4 (1982), 115-137. К этим жс методам относится и интересный метод вычпслеяшя детермпнвнтов, который выведен Ч. Л. Доджсоном (С, !. Рообвол) (известным также под именем Льюис Кэррол (Ьевчв Свгго)1)) пз теоремы Якоби. Обзор ранней нсгорцп нсследованнй тождественностп детермпнвнтов подматрпц можно найти в работе 11. Е. Кпцй, Е!есггоц!с Х СсииЕйпагог!св 3, 2 (1996), статья К5, 23.
УПРАЖНЕНИЯ 1. [!О) Вычислите псевдочастное 4(х) н псевдоостаток г(х), т. е. поляномы, удовлетворяющие (3), для и(х) = хо+в~ -х4+ 2х~+Зх~ — х+2 и е(х) = 2хо+2х~-х+3 над целыми чисцами. 2. [!5] Чему равен наибольший общий делитель полннома Зхо+х~+4х4+4хо+Зх~+4х+2 и "обратного" ему пцчинома 2х +4хэ+Зхэ+4хо+4хг+т+3 по модулю 77 (В данном случае под "обратным" подразумевается подююм с обращенным порядком коэффициентов.— Приэа.
верее.) 3. (М25) !!окажите, что алгоритм Евклида,ьчя полииомов иод полем 8 может быть расширен для поиска полииомов (Г(х) и Р(х) над 8, таких, что и(х)Ъ~(х) + !7(х)е(х) = Зоб(ц(*),ц(х)) (см. алгоритм 4.5.2Х). Чему равны степени полнномов !Г(х) и Р(х), вычисленных при помощи такого расширенного алгоритма? Докажите, что если Ю вЂ” поле рациональных чисел и если ц(х) м х — 1 н е(х) = х" — 1, то расширенный алгоритм дает пцчиномы (г(х) н 1'(х), имеющие иване коэффициенты. найдите 11(х) и У(х) для и(х) = х ' — 1 и о(х) = х'л — 1. 4.
[МЗО] Пусть р — простое число, и предположим, что алгоритм Евклида, примененный к полнномам и(х) и о(х) по модулю р, пршюдит к последовательности полиномов, имеющих степени соответственно пл, и, пл, ..., пн -оо, где пл = с)ей(и), к = деб(о) и п~ > О. Положим, что пл > н. Если и(х) и о(х) являются нормированными полиномами, независимо и равномерно распределенныыи среди всех р'"а" пар нормированных полиномов степеней соответственно гп н п, то чему равны срелнне значения трех величин й п~ + " + пл н (п — пл) ил + + (пл л — и,) п„выраженные как функции от пл, п и р? (Эти три величины являются основными факторами, влияющими на время работы алгоритма Евклида с полнномами по модулю р, если считать, что деление выполняется при помощи алгоритма П.) ]Указание.
Покавсите, что и(х) пюй в(х) равномерно распределен и независим от и(х).] 5. [М99] Чему равна вероятность того, что и(х) к о(х) взаимно просты по модулю р, если и(х) н о(х) — независимые равномерно распределеннме нормированные пслнномы степени п? 6. [Мйб] Мы вплели, что алгоритм Евклида 4.5.2А дая целых люжет быть преобразован в алгоритм для поиска наибольшего общего делителя пслиномов. Можно ли аналогичным путем преобразовать бинарный алгоритм поиска бед 4.5.2В в алгоритм, работакнций с полиномамк? Т. [М10] Чему равны обратимые элементы в области всех полиномов над областью единственного разложения Я? 8.
[Мйй] Покажллте, что, если поливом с целыми коэффициентами неприводим над областью целых чисел, он неприводим и прн рассмотрении его над полем рациональных чисел. 9. [Мйб] Пусть и(х) н о(х) — примитивные полнкомы над областью единственного разложения В. Докажите, что и(х) н и(х) взаимно просты тогда и только тогда, когда полиномы (?(х) и У(х) над Я таковы, что и(х) У(х) + 11(х) с(х) — полинам нулевой степени. [Указание. Расширьте алгоритм Е так, как алгоритм 4.5.2А был расширен в упр.
3.] 10. [Мйб] Докажите, что полнномы над областью единственного разложения образуют область единственного разложения. [Указание. Используйте результат упр. 9 для того, чтобы показать, что имеется не более одного возможного разложения.] 11. [Май] Какие строки появились бы в табл. 1, если бы последовательлгость степеней была 9, б, 5, 2, -со, а не 8, 6, 4, 2, 1, О? э 12. [ЛЩ] Пусть ил(х), иэ(х), иэ(х),,— последовательность поликанов, полученная во время работы алгоритма С. Матрица Сильвестра представляет собой квадратную матрицу, построенную из строк с А„л по Ае н с В„, л по Ве (в обозначениях, аналогичных обозначениям для табл.
1). Покажите, что если ил(х) и иэ(х) имеют общий множитель положительной степени, то детерминант матрицы Сильвестра равен кулю, н обратно: покажите, что если для некоторого )г с)ей(ил) = О, то детерминант матрицы Сильвестра ненулевой (покажите это, выведя формулу для его абсолютного значения через 4(и1) и с)еб(и ), 1 < У С 9). 13. [Мйй] Покажите, что при б~ ы бэ = м бл л ы 1 старший коэффициент 1 примитивной части бед(и(х), е(х)) входит в показагную в (28) последовательность полнномов, которая получается с помощью алгоритма С.
Какою поведение для общего случая бт? 14. [М99] Пусть г(х) — псевдоостаток от псевдоделения и(х) на о(х). Покалкнте, что если беб(и) > с)еб(с) + 2 и деб(о) > деб(г) + 2, то г(х) кратен Х(э). 15. [Мйб] Докажите неравенство Адамара (25). [Указание. Рассмотрите матрицу ААт.] ь 16. (ММ) Пусть г(ян..., я,) — полянам от многих переменных, не равный тождественно нулю, н пусть г(лн...,Яа) — множество корней (яц, .., к„) уравнения г(х„..., х ) = О, таких, что Я~ е Яы..., к„б о„. еслн степень У' не пРевышает Аг < ) лг ! длЯ пеРеменной хм докажите, что )г(Ям,,Я )) < (Яг(" 1Я«! — 08г) — Аг) "ОЯ.)-4.) Следовательно, вероятность нахождения корня случайным образом, !Г(81,...,8.)1/Фг)...)Я ), пркблнжмтся к нулю прн увелнченнн множеств о .
(Это неравенство имеет множество приложений при разработке алгоритмов рандомнзацнн, так как предоставляет хороший способ проверки, является лн сложная сумма произведений сумм равной нулю без раскрытия всех сомножителей.) 1Т, [Мой) (Алгорвтм П, Ы. Кона (Р. М. Сойп) деленна сглрокоомя по,аиномоо.) Пусть А является аафооищом, т.
е, множеством символов. Сщроке и над алфавитом А предсгавляет собой последовательность нз п > 0 символов а = ан .. о„, где кажлое аг Е А. Данна а, записываемая как )а), равна количеству символов и. Строковым полнномом над алфавитом А является конечная сумма С = 2 „га пы где каждое га является ненулевым рациональным числом, а каждое аа — строкой над алфавитом А; мы полагаем, что а, ~ аь при у Ф Ь.
Сгпепень С, деб(С), определяется как -со, если П = О (т. е. если сумма пуста); в противном случае г)ей(в) = гпах)па!. Сумма н произведение строковых полнномов определяются очеввпшым образом, Так, (2, г а )(2"„оЩ) = ~„ль ггвгпгД, где проязвеленне двух строк получается путем их простого соедннення; после этого онн сгаяовятгя членамн суммы. Например, есзн А = (а, Ь), С = оЬ+ Ьа — 2а — 2Ь н У = п+ Ь вЂ” 1, то деб(С) = 2, боб(у) = 1, уг = па+ оЬ+ Ьа+ ЬЬ-2о — 2Ь+1 н уг — С = по+ ЬЬ+ 1. ясно, что беб(Су) = бей(гг)+бей(У) н Йеб(С+У) < шах(бей(С), Йеб(У)) с равенством в последней формуле прн Пей(С) за бей(У). (Строковые полнномы могут рассматрнватьса как обычные поляномы от многих переменных над полем рациональных чисел, но переменньге не комнрглаиионм относительно умножения.
На математическом языке множество строковых ппзиномов с определенными здесь операцнямн представляет собой "свободную ассоцнатявную алгебру", порожденную А над полем рацнональных чисел.) а) Пусть сом ь)г, С и У вЂ” такие строковые полнномы с с)ея(С) > деб(У), что пев(гогС вЂ” сггУ) < пей(СгС). Разработайге алгоритм поиска строкового полинома б), такого, что деб(С вЂ” ьгУ) < деяЩ. (Следовательно, если даны П и У, такие, что й1С = йгУ+ В и г1ея(В) < пей(сггС) лля некоторых С~ н Ог, то существует решение для зтнх условий прн Сг = 1.) Ь) Даны строковые полнномы С н У с абеб(У) > г)ей(ь)гС вЂ” сггУ) для некоторых йг н Сог.
Покажите, что результат п. (а) может быть улучшен для поиска частного Ц, такого, что С = гоУ+ Н, дея(В) < йеб(У). (Это аналог (1) для строковых полнномов; в п, (а) показано, что можно достичь доя(Я) < дея(С) прн более слабой гипотезе.) с) Одноролнмй полинам — это полипом, все члены ко горого имеют одну н ту же степень (данну). Пусть ггп Сг, Ун Ьг являются однородными строковымн полиномами с С1 У~ = Сг)г н бей(Уг) > бея(Уг). Покажите, что существует однородный строковый полинам Ьг, такой, что Сг = Ьг1 С н Уг = СУг.
и) Даны однородные строковые полнномы (у н У с СУ = УГ Докажите, что имеется однородный строковый полипом )У, такой, что С = г)У", У = о)У" дла некоторых целых щ, и и рацкональных чисел г, о. Разработайте алгоритм для вычисления И', имеющего наибольшую возможную степень. (Этот алгоритм ипгересещ например, когда С = и и У =, — строки, удовлетворяющие соотношению п)1 =,Зп; тогла И'— просто некоторая строка у.
Когда (Г = к н У = я", решение с наибольшей степенью У! = Юз + В, где 4еб(В) с беВЯ). Отсюда легко вывести, что О и В определяются однозначно; они не зависят от данных П! и Пз. Кроме того, результат обладает право-левой симметрией в том смысле, что Уз = (?»О+ В, где бей(Я ) = деб(Б?!) — деб($») +деб(В) с деб((?!). Покажите, что зтот алгоритм для деления может быть расширен до алгоритма, вычисляющего НОЛКЯ, 1 з) и НОПД(1 », К»); фактически расширенный алгоритм находит строковые полиномы й! и й», такие, что й! 1')! + й»Ъ»» = НОПД(Ь!, Ъ»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
