Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 29
Текст из файла (страница 29)
Это доказывает эмпирически очевидный момент, что почти все линейные конгруэнтные последовательности имеют чрезвычайно низкую серивльную корреляцию по целому периоду. В упражнениях, приведенных ниже, показано, что другие априорные критерии, такие как критерий серий по целому периоду, могут быть выражены н в терминах небольшого обрбщения сумм Дедекинда. Нз теоремы К следует, что линейная конгруэнтная последовательность будет удовлетворять этим критериям тогда и только тогда, когда определенные дроби (зависящие от а и гп, но не от с) имеют чалые частичные отношения, В частности, из результатов упр. 19 следует, что проверка по критерию серий дэя пар удовлетворительна тогда и толька тогда, когда о/т имеет небольшие частичные отношения. В книге Суммы Дедекинда Ганса Радемахера н Эмиля Гросвальда (Напэ КабешасЬег апб Епп! СгозэнаЫ, МасЬ.
Азэос. оу АщеНсв„Сагыз Ь!опобгарЬ Хо. 16, 1972) обсуждается история и свойства сумм Дедекинда и их обобщений. Другие теоретические критерии, в том числе критерий серий для больших размерностей, рассматриваются в разделе 3.3.4. УПРАЖНЕНИЯ (часть 1) 1. [М10] Выразите х щоО Э в терминах "пилообразной" и 4-функций. 2. [М20] Докажите "реплективный закон", равенство (10). й. [йМйй] Найдите разложение в ряд Фурье (по синусам н косинусам) фупкшш ((а)).
в 4. [М10] Если гл = 10~~, то какое максимальное значение возможно для 4 (в обозначе- ниях теоремы Р), если дано, что потенциал генератора равен 10? б. ]МИ] Получите формулу (17). О. [М27] Предположим, что ЬЬ' + Ьй' = 1. а) Покажите без использоваиня леммы В, что а(Ь,Ь,с) =а(Ь,Ь,О)+12 ~) (( — „~))+б~~ — )) о<!« для всех целых с > О, Ь) Покажите, что Я)) + (( — „~)) = ~ — -ЮЯ, есви 0 <у < Ь. с) Основываясь на предположениях леммы В, докажите равенство (2Ц. ° 7.
[М24) Докажите закон взаимности (19), когда с = О, используя обобщенный закон взанмяости из упр. 1.2.4-45, й. [М84] (Л. Карлиц (Ь. Сагйсв).) Пусть Обобщив метод доказательства, использованный в лемме В, докажите следующее прекрасное тождество Г. Радемахера (Н. Вас)ещасйег). Если каждые из чисел р, а, г взаимно просты одно относительно другого, то р(р, 4, г) + р(4, г р) + р(г,р, а) ш — + — + — — 3.
р а г аг гр ра (Закон взаимности для сумм Дедекинда при с = 0 является частным случаем при г = 1.) О. [М40] Существует ли простое доказательство тождества Радемахера (упр. 3) с использованием в частном случае метода доказательства упр.
72 10. [М30] Покажите, что когда 0 < Ь < й, то можно легко выразитыг(й — Ь, й, с) н а(Ь,Ь, -с) в терминах «(Ь,й,с). 11. [МЯО] Формулы, приведенные в разделе, показывают, как оценить «(Ь, й, с), когда Ь и й — взаимно простые числа и с — целое число. В общем случае докажите, что а) «(»(Ь,»(й,»(с) =«(Ь,й,с) для целых 4 > 0; Ь) «(Ь, й, с+ 6) ш «(Ь„й, с) + 6((Ь'с/й)) для целых с, действительных 0 < 0 < 1, Ь .1.
й и ЬЬ' ж 1 (по модулю Ь). 13. [М34] Покажите, что если Ь и й — взаимно простые числа и с — целое число, то '[«(Ь, й, с)[ < (й — 1)(й - 2)/й. 13. [М34] Обобщите равенство (26) так, чтобы получить выражение для «(Ь,й,с). ь 14. [М30] Линейный ковгрузнтный генератор, для которого щ = 2»э, а = 2ге + 1, с = 1, был подвергнут сериальному корреляционному критерию для трех групп по 1 000 последовательных чисел. В результате этого была получена очень высокая корреляция, лежащая между 0.2 и 0,3 в каждом случае, Чему равна сериальная корреляция данного генератора, взятая по всем 2зз числам периодау 16.
[МИ] Обобщите лемму В так, чтобы ее можно было применять к дейсвшвщааьнм»» числам с, О < с < й. 16. [М34] Залаяв таблица Евклида, определенная в (32). Пусть,ро = 1, р~ = а~ и рз = а,р, ~ + р, з для 1 < / < Ь Покажите„что сложные части сумм в теореме 1» могут быть переписаны следующим образом, позволяющим выполнять вычисления с нецелыми числами: (-1) +' — ~ — — ] (-1)' 'Ьз(ау+сую)рз-и , Ь<й»3» юга ) щ» »+ ' ~<~« [Указание. Докажите тсакдество 2', <„(-1)~+'/тзтз+~ = (-1)'+~р» ~/т~пь+~ для 1 < г<Ь] 1Т.
[М33] Напишите алгоритм вычисления «(Ь, й, с) для целых Ь, 1., с, удовлетворяющих предположениям теоремы П. Ов должен использовать только арифметнку целых чисел (с неограниченной точностью), и ответ должен быть записан в виде А+ В/й, где А и В— целые числа (см. улр. 16.) По вазможности используйте только конечное число переменных для временного запоминания вместо того, чтобы вводить такой массив, как ам аз, ..., а».
° 18. [Мйу] (у. дитер ((). Пшсег).) даны положительные целые числа Ь, й, ю Пусть '"'" = ~ (( — ""')) 0<1<» Покажите, что сумма может быть вычислена в приближенной форме в терминах обобщенных сумм Дедекннда и пилообразной функции. [Указавае. Когда з < й, величина [//й) — [(у — з)/й] равна 1 для О < у < з и равна 0 для з < у < й, поэтому можно включить данный множитель и выполнить суммирование по 0 < / < й.] ь 19.
[МЗЗ] Покажите, что критерий серий можно проанализировать по полному периоду в терминах обобщенных сумм Дедекинда, еспи найти формулу вероятности того, что а < Х <;У и а' < Хи~.~ <,0', когда а, З, а', З' — заданные целые числа, причем 0 < а < З < гп и 0 < а' < З' < т. [Уяозоиве. Рассмотрите величину ((х — а)/ш! — ((х — З)/'ч) ] 20. [МЗУ] (У.
Дитер.) Обобщите теорему Р, чтобы получить формулу для вероятности того, что Х„> Х„е~ > Х„аз, в терминах обобщенных сумм Дедекинда. УПРАЖНЕНИЯ (чисть 2) Во многих случаях точнме вычисления с целыми числами достаточно трудно осуществить, но можно попытаться изучить возникающие вероятности, если усреднить по всем действительным величинам х вместо того, чтобы ограничить вычисление целыми числами. Хотя зги результаты будут только приближенными, они прольют немного света на проблему. Удобно использовать числа С„, лежащие между нулем и единицей.
Для линейной конгрузнтиой последовательности С„= Х„/ш получим, что С„+д = (ос' + у), где у = с/гп и (х) определено как х щоп 1. Например, формула для сериальиой корреляции примет вцк с-Ц И -;-Ии-(/,и) )/ [/ *'и — (/ *и) ). ь 21. [??МЗЮ) (Р. Р, Ковзю (К. К. Сотеуоп).) Чему равно значение С в только что приведенной формуле? и 22. [МЗЗ] Пусть о — целое число и пусть О < З < 1. Если х — действительное число, принимиощее значения между О и 1, и если е(х) = (вх + д), чему равна вероятность, что в(х) < х? (Это аналог теоремы Р для "действительных чисел".) 2$.
[МЗЗ) В предыдущем упражнении дана вероятность того, что Си+~ < Си. Чему равна вероятность с'и+а < (?и+~ < У„в предположении, что С~ — случайное действительное число, лежащее между нулем и единицей? 24. [мзз) Учитывая предположения нз предыдущего упражнения и исключая случай для У О, покажите, что С„> С„+~ > ° ° > С т~ ~ происходит с яероятиостыо —,', (1+ Д ... (1+ ' — ) . Чему раааа средняя длина нисходящих серий, начиная с С„, где Си выбрано наудачу между нулем я единицей? и 2Ь. [МЗЗ) Пусть а,,У, а', р" — действительные числа, О < а < З < 1, 0 < а' < З' < 1. Учитывая предположения из упр. 22, выясните, чему равна вероятность того, что а < х < З и а' < е(х) < З'? (Это аналог упр.
19 для "действительных чисел".) 26. [МЗ?) Рассмотрите генератор Фибоначчи, где П +~ = (Си + С -)) Предполагая что С, и Сз независимо наудачу выбраны между 0 и 1, найдите вероятность того, что Й < Й1з < Сз, С~ < Сз < 1/з, Сз < И < Сз и т. д. [Уиоэоиие. Разделите едяпичный квадрат ((х, у) ] О < х, у < 1) па шесть частей, зависящих от относительного порядка х, у и (х + у), и определите площадь каждой части.] 27. [МУЗ) В генераторе Фибоначчи из предыдущего упражнения будем считать, что Се и С~ независимо выбраны в единичном квадрате, однако исключается следующее неравенство: Се > Сь Определите вероятность, что С~ является началом возрастающей серии длиной у, так что Уе > С~ < ° < Сь > Сеем Сравните с соответствующями вероятностями для случайной последовательности.
2й. (Муз) В соответствии с формулой 3.2.1.3-(5) линейный конгруэитимй гевератор с потенциалом 2 удовлетворяет условию Х„~ — 2Х + Х +~ щ (а — 1)с (по модулю т). Рассмотрим генератор, который обобщает предыдущий. Пусть У~+1 = (а + 2У вЂ” У -1). Как в упр. 26, разаелите единичный квадрат ка части„которые указмваот отвосительный порядок Уп И~ и Ув для каждой пары (У1, ГГ2). Существует ли какое-нибудь значение о, ллв которого все шесть возможных упорядочений имеют вероятность ~, если прелдоложить, что У1 в Уз вмбрвпн наудачу в едивичиом квадрате? 3.3.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
