Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 57
Текст из файла (страница 57)
[НМУЗ] (Д, В, Лавленд (П. ЪЧ. Ьате!апд).) Покажите, что если двоичная последовательность (Х„) Ы-случайна н если (е ) — любая исчисляемая последовательность соответственно с определением В4, то Рг(Х,„= 1) > -' и ~г(Х,„= 1) < а. 36. [Над] Пусть (Х ) — двоичная последовательность, "случайная" согласно определению Вб. Покажяте, что [О .. 1)-последовательность (Ьт„), определенная в двоичной системе счисления по схеме Пе = (О Хо)а, Ьта = (О.ХаХа)м Уг = (О ХаХаХа)а, Па = (О.ХеХтХаХэ)а, случайна и смысле определения Вб, ЗТ. [МЮ7] (Д, Копперсмит (1). Соррегзш11Ь).) Постройте последовательность„удовлетворяющую определению В4, но не определению Вб.
[Указание. Рассмотрите преобразование Ь'о, Ьта, Ьт», Ьтэ, ... псгинно случайной последовательности.» 33. [М49] (А. Н. Колмогоров.) Пусть заданы К, и и с Чему равно иаименыпее число алгоритмов в множестве А, таках, чтобы не существовали (п,е)-случайные двоичные последовательности длины Ю по отношению к Ау (Если нельзя задать точные формулы, можно ли найти асимптотические формулы'? Суть этой проблемы — обнаружить, как точная грань (37) становится "наилучшей возможной".) 38. [ИЩо] (В. М.
Шмидт (%, М, бсЬшЫС),) Пусть ӄ— [0..1)-последовательность и пусть и„(о) — число таких неотрицательных целых чисел 1 < и, что О < Ц < и. Докажите, что существует такая положительная постоянная с, что для любого йг и любой [О .. 1)-последовательности (У„) мы получим ]ьь(и) — яи[ > с1п р1 для некоторых и и и при 0 < и < Ф, 0 < в < 1. (Другимн словами, никакая [О, . 1)-последовательность не может бмть слишком равнораспределена.) 40.
[М38] Завершите доказательство леммы Р1. 41. [М31] В лемме Р2 показано существование критерия прогноза, но при доказательстве предполагается существование подходящего Ь без объяснения, как конструктивно находить Ь из А. Покажите, что любой алгоритм А можно обратить в алгоритм А' с У(А') < Т(А) + О(д'), который предсказывает Вл по В~... Вл 1 с вероятностью, по крайней мере равной -' + (Р(А, Я) — Р(А, 3л))/Ф на любом сямметричном сдвиге Ф-источника Я. ь 42.
[М38] (Пепариал истееисимосшь,) а) Пусть Хм ..., Х вЂ” случайные величины со средним, равным д = ЕХ1, и дисперсией о~ = ЕХ1 — (ЕХ1) при 1 < у < и. Докажите неравенство Чебышева Рг((Х1 + + Մ— пд) > спи~) < 1/1 прн дополнительных предположениях, что Е(Х,Х ) ж (Е Х,)(ЕХ1) всякий раз, когда 1 11,7.
Ь) Пусть  — случайная двоичная матрица размера Ь х В. Докажите, что если с и с— фиксированные не равные нулю двоичные векторы размерности Ь, та сВ и с'В— независимые случайные двоичные векторы размерности Я (по молулю 2). с) Примените (а) и (Ь) к анализу алгоритма Ь, 43. [30] Кажется, точно так же тяжело найти множители любого фиксирееаииоге целого числа Влюма Ы, состоящего из В двоичных разрядов. Как найти множители серчейиоее целого числа, состоящего из В двоичных разрядов? Почему тогда теорема Р сформулирована для случайного, а не фяксированного Му ь 44.
[16] (И, Дж, Гуд (1, Л, Свод).) Может ли правильная таблица случайных чисел содержать точно «дну ошибкуу 3.6. ВЫВОДЫ В этой главк было рассмотрено довольно много тем: генерирование случайных чисел, их проверка, их видоизменение при использовании и методы получения теоретических фактов. Возможно, главным для многих читателей был вопрос "Что получено в результате всей этой теории и что такое простой добротный генератор, который можно использовать в программах в качестве надежного источника случайных чисел?". Подробные исследования в этой главе наводят на мысль, что следующая процедура позволяет получить простейший генератор случайных чисел для машинного языка болыпинства компьютеров.
В начале программы присвойте целой переменной Х некоторое значение Хе. Эта величина Х используется только для генерирования случайного числа. Как только в программе потребуется новое случайное число, положите Х < — (аЛ +е) шоот (1) и используйте новое значение Х в качестве случайной величины.
Необходимо тщательно выбрать Хе, и, с и т и разумно использовать случайные числа согласно следующим принципам. !) "Начальное" число Хо может быть выбрано произвольно. Если программа используется несколько раз и каждый раз требуются различные источники случайных чисел, то нужно присвоить Хо последнее полученное значение Х на предыдущем прогоне или, если это более удобно, присвоить Ле текущие дату и время. Чтобы снова запустить программу с такими же случайными числами (например, при отладке программы), нужно напечатать Хо, если иначе его невозможно получить. й) Число т должно быть болыпим, скажем, по крайней мере 2зе.
Возможно, удобно взять его равным размеру компьютерного слова, так как зто делает вычисление (аХ + с) шоб т вполне эффективным. В разделе 3.2,1.1 выбор т обсуждается более детально. Вычисление (аХ+ с) пюс1 т должно быть точимы без округления ошибки. й) Если т — степень 2 (т. е. если используется двоичный компьютер), выбираем а таким, чтобы а шод 8 = 5. Если т — - степень 10 (т. е. используется десятичный компьютер), выбираем а таким, чтобы а шоб 200 = 21. Одновременный выбор а и с даст гарантию, что генератор случайных чисел будет вырабатывать все т различных возможных значений Х прежде, чем они начнут повторяться (см, раздел 3.2.1.2), и гарантирует высокий "потенциал" (см. раздел 3.2.1.3). 1т) Множитель а предпочтительно выбирать между .01т и .99т, и его двоичные или десятичные цифры ие должны иметь простую регулярную структуру.
Выбирая несколько случайных констант, подобных а = 3141592621 (которые удовлетворяют обоим условиям в (й1)), почти всегда получаем достаточно хороший множитель. Дополнительная проверка, конечно, нужна, если генератор случайных чисел используется регулярно. Например, частичные отношения ие должны быть большими, ко~да для нахождения йсй а и т используется алгоритм Евклида (см. раздел З.З.З).
Множитель должен пройти спектральный критерий (раздел 3.3.4) и несколько критериев, описанных в разделе 3.3.2, прежде чем он получит сертификат качества. ч) Значение с не существенно, когда а — хороший множитель, за исключением того, что с не должно иметь общего множителя с т, когда т — размер компьютерного слова. Таким образом, можно выбрать с = 1 илн с = а. Многие используют с = 0 вместе с т = 2", но они жертвуют двумя двоичными разрядами точности и половиной начальных значений, чтобы сэкономить всего несколько наносекунд счета (см.
упр. 3.2.1.2-9). ч() Младшие значащие цифры (справа) Х не очень случайны, так что решения, основанные на числе Х, всегда должны опираться, главным образои, на старшие значащие цифры. Обычно лучше считать Х случайной дробью Х/т между О и 1, т. е. представлять себе Х с десятичной точкой слева, а не относиться к Х как к случайному целому числу между 0 и т — 1. Чтобы подсчитать случайное целое число между 0 и А — 1, нужно умножить его на А (но не делить на А; см. упр, 3.4.1 — 3) и округлить результат. чй) Важное ограничение случайности последовательности (1) обсуждалось в разделе 3.3.4, в котором показано, что "точность" при размерности 1 будет только порядка ~/т, Применяя метод Монте-Карло, необходимо использовать случайные последовательности высокой надежности.
Нх можно получить с помощью технических приемов, описанных в разделе 3.2,2. чйЦ Можно генерировать не больше т/1000 чисел, иначе последующие б);зут вести себя подобно предьсдчщим. Если т = 2зз, значит, новая схема (например, новый множитель а) должна использоваться после генерирования нескольких миллионов случайных чисел.
Комментарии, приведенные вылив, относятся, главным образом, к машинному языку программирования. Некоторые понятия прекрасно работают также на языках высокого уровня, например (1) превращается в Х=а»Х+с на языке С, если Х имеет тпп беззнаковое длинное и если т равно модулю беззнаково длинной арифметики (обычно 2ээ или 2"»). Но С не дает возможности рассматривать Х в качестве дроби, как того требует (и), если не обращаться к числам с плавающей точкой двойной точности. Поэтому для языка программирования, подобного С, часто используют другой вариант (1): выбирается простое число т, близкое к наибольшему легко вычисляемому целому числу, а полагается равным первообразному корню т и приращение с в этом случае равняется нулю. Тогда (1) может полностью выполняться простой арифметикой над числами, остающимися иежду -т н +т, так, как в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
