Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 15
Текст из файла (страница 15)
15. (МЕ7] Пусть последовательность (Х ) в алгоритме М имеет длину периода Л~ и все элементы в этом периоде различны. Пусть д» = ппп[г ( г > 0 и (И'„-,»т] = (И»/т]). Предположим, что д» < 1Л~ для всех п > па и что последовательность (д,) имеет длину периода Л». Пусть Л вЂ” наименьшее общее кратное Л» и Л». Докажите, что последовательность на выходе (а»), полученная с помощью алгоритма М, имеет длину периода Л. ь 16. (МЯЮ] Пусть и методе (10) СО)(ЕРИИИОЕ(1) равно (а~а»...
а»)» в бинарной записи. Покажите, что последовательность, генерируемая младшими разрядами Хо, Хы ..., удовлетворяет соотношению Л» = (а~Х» ~ +а»Х»»+ . +а»Х„») пю42. (Это можно рассматривать как друюй способ определения последовательности, хотя связь между данным соотношением и программой (10), на первый взгляд, не заметна!] 17. (МУУ] (М, Х, Мартин (М. Н, МвгНп), 1934.) Пусть т и 1 -- положительные числа и пусть Х~ = Л» = ° = Л» = О, Для всех и > О положим Х»»» равным наибольшему неотрицательному числу я < т, такому, что й-мерная строка (Х»»ь...,Л,;» му) еще не появилась в последовательности. Другими словами, (Х„.»„...,Х„»,,д) должна отличаться от (Х,эп...,Х +») для 0 < г < и.
При этом каждая возможная к-мерная строка встретится по крайней мере один раз в последовательности. В конце концов процесс закончится, когда будет достигнуто такое значение и, при котором строка (Л +и .,,, Л" +»-и д) уже появлялась в последовательности дли всех неотрицательных д < т. Например, если т = й = 3, такой последовательностью будет 00022212202112102012001110100 и процесс закончится в этой точке. (а) Докажите, что, когда последовательность закончится, будут выполняться равенства Х»а» ы .
= Л„„» ~ = О. (Ь) Докажите, что каакдал )г-мерная строка элементов (ам ат,..., а»), таких, что 0 < а, < т, появляется в последовательности. Поэтому последовательность окончится при к = т». (Указание. Докажите, что л-мерная строка (аь..., а„О,..., 0) появляется, когда а, ~ О, используя инлуктпо по р.] Заметим, что если сейчас определить 1(Х,..., Х„„.» ~ ) = Х„»» лдя 1 < и < т, полагая Х», „= О, то получится функция с максимальным возможным периодом.
18. (мяд] пусть (х„) — это последовательность двоичных разрядов, генерируемая методом (10), с 1 = 35 и СОДЕРЕИИОЕ(А) = (00000000000000000000000000000000101)з. Пусть У» — бинарная дробь (.Х„»Х»»+т .,. Х»»»»»)». Покажите, что эта последовательность (6'„) не удовлетворяет сериальному критерию пар (раздел 3.3.2В), когда»( = 8. 19. (М41] Для каждого простого числа р из первою столбца табл.
2 раздела 4.5,4 найдите подходящие константы а» и аз, как предлагается в разделе, чтобы длина периода (8) при 1» 2 равнялась Р» — 1. (Например, см. Рекуррентное соотношение 3.3.4-(39).) 20. [М40] Вычислите подходящие константы для использования в качестве содержимого регистра А (СОЕЕРИИИОЕ(А) ) в методе (10), имеющие приблизительно то же 'количество нулей, что и констанпя для 2 < 1» < 64. 21. (МУЕ] (Д. Рис (П. Неез).) В разделе объясняется, как найти функции у, такие, что последовательность (11) имеет длину периода т» — !, если т — простое число и не все Ха,, Х»» равны нулю. Покажите, что такие функции могут быть изменены для получения последовательности наподобие (1!) с длиной периода т для всех цечых т. [Указание. Рассмотрите лемму 3.2,1.2(), трюк из упр.
7 и последовательность вцла (РХз„+ Х2.е1)1 ь 22. [М84] В разделе нет обширных обсуждений способов расширения линейной последовательности (8) до случая, когда гл является простым числом. Докажите, что достаточно длинный период может быть получен. когда гп "свободно от квадратов", т. е. является произведением различных простых чисел. (Из табл.
3.2.1.1-1 ясно, что гл = м х 1 часто удовлетворяет этим предположениям. Многие из резулыатов, приведенных в настоящем разделе, могут поэтому быть распространены иа случай, который в некоторой степени более удобеи для вычислений.) ° 23, [80] Рассмотрите последовательность Л„= (Х„ы — Л ы) щоб т как альтернативу последовательности (7) .
24. [М80] Пусть О < 1 < й. Докажите, что последовательность двоичных разрядов, определенная рекурревтиым соотношением х„= (х„ьм + х„ь) шоб 2, имеет длину периода 2 ' — 1 всякий раз, когда такой же период имеет последовательность, определенная ь соотношением У„= (1'„~ + у„ь) шоб 2. 25. [86] Рассмотрите альтернативу для программы А, состоящую в том, что все 55 входов в таблице У-в заменяются 55 раз требуемыми случайными числами. 26. [М40] (Дж.
Ф. рейвер (3. Р. Ве!эег).) Пусть р — простое число и 5 — положительное число. Пусть заданы целые числа ам,..,аь и ем...,хю пусть Л вЂ” период поыедовательности (Х„), заданной рекуррентиым соотношеиием Х = г шеар, О < и < я; Х„= (а~Х„~ + +аьХ„э) шобр", ц > к, и пусть А' равно чисту нулей, которые встречаются в периоде (числу ицлексов у, таких, что дь < 0 < и„+ Л и Хз = О), Докажите или опровергиите следующее утверхсэение: существует коистанта с (зависящая, возможно, от р, я и ам...,аь), такая, что А < срыв цд" П для всех и и всех хм..., хы [Замечание. Рейвер доказал, что если рекуррентная последовательность имеет максимальную ялику периода по модулю р (т. е, если Л~ = р — 1) и если утверждепие имеет место, то я-мерное расхождение (х„) будет равно 0(а"р "~1ь и) при а -э со.
таким образом, адлитивиый геиератор, подобный (7), был бы распределен в 55 измерениях, когда т = 2' и рассматривается полный период. (См, раздел 3.3.4, в котором определена понятие расхождения в я измерениях.) Утверждение является слабым условием, если (Х ) прииимает каждое зиачеиие примерно одинаково часто и если Л = р '(р" — 1).
Величина А' Й (р" — 1)/р ие увеличивается, вообще говоря, когда а возрастает. Рейвер проверил зто утверждение для я = 3. С другой стороны, ои показал, что можно найти необычайно плохие (зависящие от а) иачэльиые значения хм.,,, кы такие, что Мь* > р~, обеспечивающие Л = р ~(р" — 1), й > 3, а достаточно большое,] 27. [М00] Предположим, что алгоритм В применяется к последовательности (Х„) с длиной периода Л, где Л » к. Покажите, что для фиксированиого я и всех достаточно больших Л последовательность на выходе будет периодичиай с той же самой длиной периода Л, если (Х ) не является слишком случайной, [Указание.
Найдите структуру последовательиых значений [йХ, /т), которая обеспечивает "синхронизацию' дальнейшего поведения алгоритма В.] 28. [40] (А. дж. Вотермаи (А. С. 55гаеегшал).) Исследуйте линейиую конгруэитиую последовательность с т, равным квадрату или кубу длины компьютерного слова, в то время как а и с заданы с обычной точностью. ь 29. [40] Найдите хороший метод вычисления функции /(ям...,хь), определенной последовательностью Мартина (Магйп) в упр. 17, если задана только строка (ям, .,,яь) размерности й. 30. [М87] (Р П. Врент (К. Р. Вгепс) ) Пусть 7(х) = хь -о~х" '-".
-оз — первообразный полипом по модулю 2, и предположим, что Хо, " ., Хь ~ — целые числа, не все четные. а) Докажите, что длина периода последовательности, заданной рекуррентным соотношением Х„= (о~Х„-~ + +оьХ„ь) шод2', равна 2' '(2" — 1) для всех е > 1 тогда и тазько тогда, когда у(х)з + у(-х)' щ 27(х') и у(х)'+ у( — х) ~ 2( — 1)~у( — х') (по модулю 8), [Указание. Равенство хз' щ -х (по модулям 4 и у(х)) справедливо тогда и только тогда, когда у(х)т + у(-х)з щ 21(хз) (по модулю 8).] Ь) Докажите, что это условие всегда выполняется, когда полином у(х) = х" х х' —." 1 является первообразным полиномом по модулю 2 и й > 2.
31. [МУР] (Дж. 6(арсазья (С. Магзабйа).) Какова двина периода последовательности (7'), когда т = 2' > 8? Предположите, что не все Хо,..., Хзз щ х1 (по модулю 8). 32. [МИ] Каким рекуррентным соотношениям удовлетворяют злементы подпогледовательностей (Лз„) и (Хз ), когда Хз = (Х„-ы + Х зз) шод т? ° ЗЗ. [МЗЮ] (а) Пустьйм(з) =Х +зо+Х езез+ ..+Х~з~+Ха+меж+" +Х~~зьз где Х„удовлетворяют рекуррентному соотноьчению Фнбоначчи с запаздыванием (7). Найдите простое соотношение между д„(з) н 8 +~(з).
(Ь) Выразите Хзоо в терминах Хо,, Хы. 34. [М88] Докажите, что обратная рекуррентная последовательность (12) имеет период р+ 1 тогда и тшгько тогда, когда полипом /(х) = х~ — ст — а обладает следующими двулщ свойствами: (1) хз'г'шобу(х) равняется отличной от нуля константе, если вычислять, используя полиномиальную арифметику по модулю р; (н) х1геп?е шод 7(х) имеет степень 1 для каждого простого 0, делящего р+1, [Указание. Рассмотрите степени матрицы (~,).] Зб. [НМЮ5] Как много пар (а, с) удовлетворяют условиям упр. 34? 36. [Мйб] Докажите, что обратная конгрузнтнвя последовательность Л г~ = (аХ„'+с) шод 2', Ло = 1, е > 3, имеет периоддлиной 2' ' всякий раз, когдаошо84 = 1 и с щи 4= 2.
ь 37. [НИЗ] Пусть р — простое число, и предположим, что Х,+~ = (аХ„' + с) шопр определяет обратную конгрузнтную последовательность с периодом р+ 1. К тому же пусть 0 < 6~ < < 6з < и. Рассмотрим множество 1' = ((Х ьы Х еы,, Х ~ ьз ) [ 0 < в < и я Х,~ ~ ь, ф сч для 1 < У < И) В нем содержится р + 1 — 8 векторов; любые 8 из ник лежат в некоторой (8 — 1)-мерной гиперплоскости Н = ((в~„...,ве) [ г~е~+ +геев щ ге (по модулю р)], где (гм...,гз)!Ф (О,...,О). Докажите, что никакие И+ 1 векторов из К не лежат в одной и той же гиперплоскости. 3.3.
СТАТИСТИЧЕСКИЕ КРИТЕРИИ Нлшл основная цкль — получить последовательность, которая ведет себя так, как будто она является случайной. Вылив рассказывалось, как сделать период последовательности настолько длинным, что при практических применениях он никогда не будет повторяться. Это важный критерий, но он не дает гарантии, что последовательность будет использоваться в приложениях. Как решить, достаточно ли случайной будет последовательность? Если дать наудачу выбранному человеку карандаш и бумагу и попросить его написать 100 десятичных цифр, то очень мало шансов, что будет получен удовлетворительный результат, Люди стремятся избегать действий, приводящих к результатам, которые кажутся неслучайными, таким, например, как появление пары равных смежных цифр 1хотя приблизительно одна из 10 цифр должна равняться предыдущей), И, если показать тому же человеку таблицу настоящих случайных чисел, он, вероятно, скажет, что эти числа не случайны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
