AOP_Tom2 (1021737), страница 169
Текст из файла (страница 169)
11. 23. Вычитание может происходить быстрее суммирования (см. упр. 3.2.1.1-5); длина периода все еще равна 2' '(2м — 1) согласно упр. 30. Р, Брент (К. Вгепг) отметил, что при использовании чисел с плавающей точкой вычисления можно произвести точно в [О .. 1) (см, упр, 3.6-11). 24. Обратите последовательность. Другими словамн, если Я = У „, то Я„= (Я«ьы— г.
) 02=(2. « .+Е„,) 42. 26. Эта идея поможет избежать болъшинства затрат времени на обращение к программам, Например, предположим, что программа А вызывается командой 5МР НАИРИ, где ЕАИОИ 373 1Р СОА Т,б появятся в последовательности (з„), для алгоритма В будут выполняться неравенства У[1) <т/й,О</<й, атакже1 <т/й. Доказательсслео. Пусть 5„— множество позиций с, таких, что 1'Я < т/й точно перед тем, как генерируется Х„, и пусть з'„— такой индекс, что ЦУ„)»- Х . Если /„й 5„ иХ„=О,тоЯ„ес = ЯйО(1/и,~.»с >О, еслиже с б о и7„=0, то>„.»с = о'„и /„.»с = О.
После й+ 2 последовательных нулей далжно вьспалняться 0 б Е„и /„ь» = О. Тогда после "1 0»1'» должно выполняться (О, 1) С 5 и/„ес — — 0; после "2 Оы' выполняется (О, 1, 2) С 5 и у ьс = О; и т. д. Следствие. Пусть 1 = (йз + 7й — 2)/2. Если Л > 1й~, го либо алгоритм В обеспечивает длину пернссла Л, либо последовательность (Х„) плохо распределена. Доказасаельстео. Вероятность того, что любая данная схема з" длиной 1 ие появляется в случайной пскледовательнос» и длиной Л, меньше, чем (1 — й ')~д < ехр( — й 'Л/1) < е следовательно, фиксированные схемы могут появляться. Пошсе того как это произойдет, дальнейшее поведение алгоритма В будет таким же каждый раз, когда он достигнет этой части периода. (Когда й > 4, то требуется Л > 10, поэтому данный результат чисто м академический, но возможны также меньшие границы.) 29.
Следующий алгоритм в худшем случае осуществляет около йз операций. Но среднее времн выполнении операций намного меньше; воз»южно, 0(1о8 й) или даже 0(1). Х1. Присвоить (ае, ам, а») с — (хс,, х», т — 1), Х2. Пусты' — минимум для а, > О и с > О. Реализуйте программу У для / = с + 1, ..., й, пака а» > О. ХЗ. Если ае > а», /(х»,..., х») = ао, 'иначе, если ае > О, /(хс,..., х») = ае — 1; иначе /(х»,..., х») = а».
3 'У1. Присвоить 1 с — О. (Программа на шагах У1-Ъ'3 проверяет лекснкографическое отношение (а„...,ас~»» с) > (ам,аз.»»»). Убывание а» необходимо, чтобы сделать это неравенства верным. Предполагается, что а»ь» = ас, а»+з = аз и т. д.) Ъ'2. Если а,ьс > аз»с, выйтн из программы. Иначе, если 1+1 = й, присвоить а» с — асьс. Иначе, если а,ьс = азьс, перейти к шагу УЗ.
Иначе, если 1 +1 > й, уменьшить а» на 1 и выйти иэ программы, Иначе присвоить а» с- 0 и выйти из программы. »»»3. Увеличить 1 на 1 и возвратиться к шагу Ъ'2, если 1 < й. $ Эта проблема впервые была решена Г. Фредриксеном (Н. Егебг1с1свеп) для т = 2 (з. Сош54аагог1Ы Тйеогу 9 (1970), 1-5; А12 (1972), 153 — 154). В этом частном случае алгоритм проще и может быть задан с й-разрядным регистром. См. также работу Б. Х1е, РЫсгеге Аррйес( Мв15. 18 (1987), 157-177. ЗО. Из упр.
11 следует, что достаточно показать, что длина периода по модулям 8 равна 4(2" — 1). Это будет выполняться тогда и только тогда, когда хзш" -М 1е 1 (по модулям 8 и /(х)), а также тогда и только тогда, когда хз -' ~ 1 (по модулям 4 и /(х)). Запишем /(х) = /с(хз) + х/,(хз), где /.(хз) = 1(/(х) + /( — х)). Тогда /(х)з + /( — х)з ш 2/(хз) (по модулю 8) тогда и только тогда, когда /с(х) +х/с(х) ив в /(х) (по модулю 4); и последнее условие имеет место тогда и только тогда, когда /,(х)з щ — х/»(х)з (по модулям 4 и /(х)), так как /,(х) + х/ (х) = /(х) + 0(х" ').
Балее того, работая по модулю 2 и /(х), мы получим /с(х) щ /,(х') щ х/»(х ) ш хз /»(х) . Следовательно, /,(х) щ хз~,'/»(х). Поэтому /,(х) щ хз'/„(х) (по мсщулям 4 и /(х)), отсюда следует утверждение указания. Рассуждая подобным образом, можно доказать, что х'с = х (по модулю 4 и /(х)) тогда и только тогда, когда /(х) + /(-х) щ 2(-1) /( — х') (по модулю 8).
(Ь) Условие может выполняться только тогда, когда ! нечетно и lс = 2!. Но в таком случае 7'(х) является первообразным полиномом по модулю 2, когда /4 = 2. [МаСЬ. Сошр. 63 (1994), 389-40Ц 31. Соотношение Х„ш ( — 1)~" Зг" шо62' выполняется для некоторых У„и х по теореме 3.2.1.2С. Следовательно, 1'„= (1'„24 + 1'„55) шод 2 и Я = (Я» — 24 + Я» ы) шоо! 2' Так как Яз нечетио тогда и только тогда, когда Хз шоб 8 = 3 или 5, из предыдущего упражнения следует, что длина периода равна 2' з(255 — 1).
32. Можно не обращать внимания на шос! т и вернуться к этому позже. Производящая функция д(г) = Л,'„Х„г" — это полипом, кратный 1/(1 — гз — г ); поэтому 2 „Лз„гз" = 1(д(г)+д(г))этопол14ноделениьзйна(1224255)(1224+255)12224+245г110 Первое требуемое рекуррентиое соотношение поэтому имеет вид Хз = (2Х2!» — ы>— Лц -зз> +Хзы 55>) шобт. Аналогично 2 »„Хз гз" = 1(д(г) + д(442) + д(52~2)), где ы ы ез 1!з, и можно найти, что Хз» = (ЗХВ>» В> — ЗХВ! -15> + Хз> -ы> + ЛВ!»-ы>) шоб т зз. (а) д„,(г) ш г'д„(г) (по модулю пз и 1 + гз' — г 5) индукцией по 2.
(ь) так как гзоо шоб (1+ 2п — 255) = 79222+ гз+ 1725+ 715го+3622+ г 5+3642 5+ 210212 +105гзз ->- 462гзо + Ьбгзо + 1287255 > 9255 + 18 51 + 1001245 + 120 Вз + 244 + 455241 + 462гю + 120 54 (см. алгоритм 4.6.1П), то получим Лзоо = (792Х2 + ХВ + + 120Лы) шоб т. [Интересно сравнить подобную формулу Х155 = (Хо + ЗХ2 ->- Х14 ->- ЗЛз> + 4Хзз + х45) тобт с "прореженным" рекурреитным соотношением для (хз ) в предыдущем упражнении. Метод Люшера для генерирования 165 чисел, в котором используются только первые 55 чисел, очевидно, не лучше идеи генерирования 165 чисел с помощью только Хз, ХВ, °, Хыз] з4.
пусть до = О, д1 = 1, д»4.1 = сд + ад 1, тогда выполняется равенство ( ) 15 11 ("4" ' 4", ), Х„= (д»+1Хо+ ад„)/(д Хо+ ад 1) и х" гпос1/(х) ш д„х+ ад„1 для и > 1. Таким образом, если Хо = О, то Х = 0 тогда и только тогда, когда х" шо4! >(х) — не равная нулю константа. 35. Из условий (1) и (й) получаем, что у(х) неприводима. Если 7(х) = (х — г1)(х — гз) и г1 гз ~ О, то х~ ' ш 1, если г1 ~ гз, и х" и 11, если г1 = гз. Пусть 5 — первообразный корень паля, имеющего рз элементов, и предположим, что = сзб + аз. квадратичные полиномы, как было установлено, — это точно поли- 25 номы 15(х) = х — сзх — аз, где 1 < >4 < р — 1 и >4 !.
р+ 1. (См. упр. 4.6.2-16.) Каждый полинол1 Паявпястея для двух значений )4; СлЕдовательно, число рЕШений равно 2(Р ) П412+1,4 о» 4»4( /д)' 36. В данном случае Х„всегда нечетно, поэтому Х„' существует по модулю 2'. Последовательность (д ), определенная в ответе 34, имеет вид О, 1, 2, 1, О, 1, 2, 1,... по модулю 4. Справедливы также д2» = д (д»аз+ ад„1) и д2,-1 = ад„з+ д„, поэтому дз»+1 — адз»-1 = (д +1 — ад -1)(д 41+ад„41) следовательно, д 41+ад„41 ш 2 (по модулю 4), когда пчетно Получим, что дз.
— это нечетное кратное 2" и дз. +1 — адз., — зто нечетное кратное 24 ю для всех е > О. Поэтому дз +ад2.-1 шдз т1+адз + 2'+ (по модулю 2'+2). И Хз'-' ьл (дз'-2+1+адз*-2)/(дз -2+адз.-з,) х> 1 (по модулю 2'), в то время как Х1,-1 щ 1, И обратно: необходимо, чтобы а шоб 4 = 1 и с шоб 4 = 2, иначе Хз„ш 1 (по модулю 8). [См. работу Эйхенауэра, Лехна и Топаэогли (Е!сЬепапег, ЬВЬп, авб Торпго8!и, Магй Сошр. 51 (1988), 757-759).) Младпзий двоичный разряд этой последовательности имеет короткий период, поэтому предпочтителен обратный генератор с простым модулем. 37. Можно предпазожить, что 5) = О.
Из уир. 34 следует, что типичным вектором в 1! будет вектор (х, (взх + авз)/(взх + овз ),, (ввх + авв)/(ввх + авв ) ), где ь! = Ол), в, = дь,е), в, = чь! — ! Он принадлежит гиперплоскости Н тогда и только тогда, когда гзсз гвга г)х + — + + — = га — гзвзвз — ° — гввввв (по модулю р) х — нз Х вЂ” Вв где С! = а — ав;в,')вз з = — (-а) в, и и = ав,"в '.
Но зто соотношение эквивалентно палиномиальной сравнимостн степени < 4(, поэтому для 4(+ 1 нельзя найти значения х, если это соотношение не выполняется для всех х, включая различные точки х = из, ..., х = вв. Следовательно, гз = = гв а О и г) ш О. [См. работу Ю. Эйхенаузр-Геррмана (5. Е1сЬепааег-Неггшапп, МаНл Сошр.
56 (1991), 297-301).) Замечание. Если рассмотреть матрицу М размера (р + 1 — )4) к (44+ 1) со строками ((1, а),..., ав) ~ (о),.,, ! ов) б И), то это упражнение будет эквивалентна утверждению, чта любые 4(+ 1 строк матрицы Ы линейно независимы по модулю р. Интересно было бы построить график точек (Х, Х +) ) для р ж 1000 и 0 < и < р; тогда можно увидеть больше следов от окружностей, чем от прямых линий.
РАЗДЕЛ 3.3.1 1. Есть 5 = 11 категорий, поэтому следует использовать строку )4 = 10. З З 4 Ь Ь В Ь Ь 4 З З 2. 4В' 4В' 4В' 4В' 4В' 4В' 4В' 4В' 4В' 4В! 4В' 3. И = 7Я только немногим больше, чем значение, полученное при использовании хороших игральных костей! Существует два объяснения, почему мы ие определили, что игральная кость поддельная. (а) Новые вероятности (см. упр. 2) в действительности не очень далеки от тех, которые заданы в (1). Сумма показаний двух игральных костей стремится к сглажнваняю вероятностей.
Если подсчитать вместо сумм каждую из 36 возможных пар значений, скорее всего, можно будет определить разницу быстрее (предполагая, что игральные кости разлнчиллы). (Ь) Намного более важное объяснение состоит в том, что и является слишколл малым для того, чтобы фиксировать значимое различие. Если бы этот же экспериллент был проведен для достаточно большого и, то подделка была бы раскрыта (см. упр. 12). 4. р, = —,' для 2 < в < 12 и в Ьл 7; рг = -'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
