AOP_Tom2 (1021737), страница 45
Текст из файла (страница 45)
Например, когда 1 = 4, случайного числа между 1 и 24 д«ютаточно, чтобы выбрать случайную перестановку из таблицы всех возможностей. Но для болыпих 1 необходимо быть более осторожным, если требуется, чтобы каждая перестановка была равновероятной, так как Н намного больше точности отдельного случайного числа. Подходящая процедура перемешивания может быть получена с помощью уже упоминаемого алгоритма 3.3.2Р, который дает простое соответствие между каждой из Н возможных перестановок и последовательностью чисел (с»,сэ....,с»») с 0 < сэ < 1 Можно легко получить такое множество случайных чисел, и это соответств»»е можно использовать для получения случайных перестановок.
Алгоритм Р (»1еремешиеаиие). Пусть Х», Хз, ..., Л» — множество 1 чисел для перемешивания. Р1. [Инициализация.] Присвоить» « — б Р2. [Генерирование 5».] Ге»»ерировать случайное число Г', равномер»ю распределенное между 0 и 1. РЗ. [Замена.] Присвоить й « — 1)ь'] -«- 1. (Сейчас /с .— случайное целое число между 1 и ~. В упр. 3.4.1 — 3 объясняется, что деление на ! не следует использовать для вычисления А.) Эаь«ени»«Х» «+ Х .
Р4. [Уменьшение ~'.] Уменьшить» ва 1. Если»' > 1, возвратиться к шагу Р2. 1 Впервые этот ш»горит»«опубликовали Р. А. Фишер и Ф. Ятс (Н. А. Р!э)»ег ап«1 Р. Уагеэ, 8!а»»з»»са! ТаЫеэ (1,оп«!оп, 1938), Ехашр!е 12) на обычном языке, а Р. Дурстенфелд — на языке компьютерном (Н.
Рпгэ»еп1е!0, САСМ 7 (1964), 420). Чтобы просто генерировать случайную перестановку (1,..., Г) вместо перемешивания заданной последовательности (Х»,..., Х«), можно избежать операции замены Х» «-» Х, выполнив увеличение»' от 1 до 1 и присвоив Х « — Хь, Х» +- 1 [см. П. Е. Кпцг)», Тйе огш»гог«4 Пгар!»Вазе (»эе»и Уо»1»: АСМ Ргеээ, 1994), 104]. Р. Салфи (К. Ба!б, СОА1РБТАТ 1974 (У!еппа, 1974), 28 — 35) указал, что алгоритм Р не имеет возможности генерировать более гп различных перестановок, когда мы получаем равномерно распределенные (7, из линейной конгруэнтной последовательности по модулю т илн используем рекуррентное соотноп»ение с»„«.» — — 1(бв), для которого Ь'„может дать только т различных значений, потому что окончательная перестановка в таком случае полностью определяется первыми генерированными значениями (/, Так, например, если т = 2зз, определенные перестановки из 13 элементов никогда не появятся, поскольку 13! ко 1.45 х 2эз, В большинстве случаев на самом деле нет необходимости получать все 13! переставовок, но огорчает, что исключение данных перестановок определяется фактически простым математическим правилом, таким как решетчатая структура (см, раздел 3.3.4).
Эта проблема не возникает, когда используется генератор Фибоначчи с запаздыванием, подобный 3.2.2-(7), с достаточно длинным периодом. Но даже таким методом невозможно получать все перестановки постоянно, если нельзя точно задать по крайней мере !! различных начальных значений для инициализации генератора. Другими словами, пе существует возможности получить 15!! истинно случайных двоичных разрядов на выходе, если не получить 15 !! истинно случайных двоичных разрядов на входе. Как говорится в разделе 3.5, не стоит из-за этого огорчаться.
Алгоритм Б можно легко преобразовать для получения случайной перестановки случайных сочетаний (см. упр. 15). Случайные объекты комбинаторики других видов (например, разбиения) рассматриваются в разделе 7.2 и в книге СошЬ!лагос!а! А!Болсбщэ Ьу э!]епЬп!з апб %1!1 (!леч Уог)с Асас1еппс Ргеээ, 1975). УПРАЖНЕНИЯ 1. [МРЯ] Объясните (1). 2. [ЯО],Докажите, что алгоритм Б никогда не пытается прочесть более Х записей своего входного файла.
3. [ЯЯ] (Г-Ь1)-я запись в алгоритме Б выбирается с вероятностью (и-т)/(М-Г), а не и/И, однако алгоритм требует, чтобы выборка была беспристрастной, поэтому каждая запись должна выбираться с одинаковой вероятностью. Почему оба эти утверждения правильны? 4. [МЯУ] Пусть р(т,!) — вероятность того, что выбрано точно т записей среди первых ! в методе отбора выборок.
Покажите непосредственно из алгоритма Б, что 5. [МЯ4] Чему равно среднее значение ! по завершении алгоритма Б? (Другими словами, сколько из !у записей будет просмотрено в среднем, прежде чем выборка станет полной?) 6. [МЯ4] Чему равно среднеквадратичное отклонение значения, вычисленного в упр. 5? 7. [МЯ5] Докажите, чтолюбой эооаннь~й выбор и записей из множества Жзапнсей может быть получен алгоритмом Б с вероятностью 1/(,).
Следовательно, выборка является совершенна беспристрастной. й. [МУЯ] (Д. С. Виттер (Л. Б Уйгег),) Алгоритм Б производит одну равномерно распределенную случайную величину для каждой входной записи. Цель этого упражнеиия— рассмотреть более эффективный подход, при котором можно быстрее вычислить точное число Х входных записей. которые следует пропустить.
прежде чем сделать первый выбор. а) Чему равна вероятность того, что Х > к, к задано? Ь) Покажите, что результат (а) позволяет выполнить вычисление Х, генерируя только одну равномерно распределенную случайную величину 7/, и производит 0(Х) других вычислений. с) Покажите, что можно также присвоить Х 4 — ппп(Ул,Ул 1, ., Уч-ч--1), где Н независимы и каждое Н является случайным целым числом в области 0 < У4 < 1. с)) Найдитс максимальную скорость, т. е. покажите, что Х также может быть вычислено в среднем за 0(1) шагов, ести использовать "метод втискивания", подобный 3.4.1-(18). 9.
[18[ Пусть п = 3. Если алгоритм К применяется к файлу, содержащему 20 записей, которые пронумерованы от 1 до 20, и есши случайные числа, генерированные на шаге НЗ, равны соответственно 4., 1, 6, 7, .5, 3., 5, 11, 11, 3, 7, 9, 3, 11. 4, 5, 4. какая записы1опадет в резервуарэ Какая из них окажется в окончательной выборке7 10. [15[ Преобразуйте алгоритм Н так, чтобы обойтись без резервуара, предполагая, что и записей текущей выборки можно хранить в памяти. ь 11.
[М85[ Пусть р вероятность того, что точно гп элементов занесены в резервуар в течение первого прохода алгоритма Н, Определите производящую функцию С(3) = 2,„ р 3 и найдите среднее значение и среднеквадратичное отклонение. (Используйте идеи из раздела 1.2.10.) 12. [МЯб[ Суть алгоритма Р состоит в том, что любую перестановку я можно однозначно записать как результат транспонирования в виде г = (011)... (033)(022), где 1 < 01' < 1 для 7 > 7 > 1.
Докажите, что существует также единственное представление вида л = (Ь22)(Ь33) (ЬН), где 1 < Ь, < 1 для 1 < 7 < 3, и составьте алгоритм для вычисления Ьь через аь за 0(1) шагов. 13. [МЯЯ[ (С. В. Голомб (Б. "79. Со!ошЪ).) Один из наиболее простых способов тасоваиия игральных карт разделение колоды карт на две максимально равные части и их тасование вместе.
(В правилах Хойла карточных игр при обсуждении профессиональной этики игроков в карты сказано: "Тасование такого вида можно выполнить приблизительно трехкратным тщательным перемешиванием игральных карт".) Рассмотрим колоду из 2п — 1 игральных карт Х1, Х2, ..., Л2„1. "Идеальное перечешивание" — это разделение 8 раз этой колоды на части Х1, Л2, ..., Х„и Х„+1,, Л2 1. Чередуя их, получим Х1.
Х„э1, Х2, Х +2, ..., Ль, 1, Х„. Операция "разрезания" с' меняет Л1, Х2,, Хгч-1 на Х74м,, Л2 -3, Хп..., Хг. Покажите, что, комбинируя идеальное перемешиваиие и разрезание, можно получить не более (2п — 1)(2п — 2) различных упорядочений компоновок игральных карт, если и > 1. 14. [89[ Разрезав и псретасован перестановку 0601...а„1, можно заменить ее последовательностью, содержащей подпоследовательности а ам+,1 54„...01„ы„„а„и а„а1„+0„„4„...01, П „4„, которые перемешаны определенным способом для некоторых х и у. Таким образом, последовательность 3890145267 является разрезанием и перетасовкой 0123456789 с х = 3 и у = 8.
а) Начав с расположенных обычным образом 52 игральных карт 2 3 4 5 6 7 8 9103 г)кА 2 3 4 5 6 7 В 9103 с)к А 2 3 4 5 6 7 8 9103 с)кА 2 3 4 5 6 7 6 9 103 44 к А вааваааваааааьььеоооеоооооооооооооооооо ° в ° ь ° е ° ° ° ь ° ив мистер Д. Г. Квнк (1. Н. Яп1ск) (" Студент" ) сделал случайное разрезание и перетасовку, затем убрал крайнюю слева карту и вставил ее в случайное место. Получилась последовательность 910к 3 с)АкА 2443 2 3 4 5 6 7 4 В 9 Вше Я 741 Вк 9103 11Ак 2 3 А 4 2 3 4 5 6 5 6 7 8 7 9 103 8 ааоааоааоооьвьвьвоьаььоььаоаоооо ° оааь ° оооааооооаооо ° ' Какую карту он убрал из крайней слева позиции? Ь) Начав снова с колоды в ее обычном порядке, Квнк сделал три разрезания и перетасовки, прежде чем сдвинул крайнюю слева карту на новое место: 103 Я 3 4 8 6 3 3 424 6 кА 2 3 к 4 7 3 6ЯА 7 Б л 8 7 6 кк9 А 7 8 9108108 2 3 1 2 3 72 4 У 3 2 910 оаааееоао ° аеааааоаоа ° оао ° от ° во ° оо ° *аоааооооооеоаоаоа Какую карту он сдвинул на этот разу ь 15.
(ЯО) (Олегйохан Дахл (Р)е-1011ап Оаы).) если х» = )7 для 1 < й < 8 в начале алгоритма Р н если остановить алгоритм, когда у достигнет значения 2 — и, последовательность Х1 о+1, ..., Х1 станет случайной перестановкой случайных комбинаций из н элементов. Покажите, как эффективно счоделировать зту процедуру, используя только 0(л) ячеек памяти. ь 16. (мл5) придумайте метод вычисления случайной выборки по и записей из д7 при заданных 77' и и, основываясь на идее рандомизации (раздел 6.4), можете использовать в нем 0(п) ячеек для хранения и в среднем 0(п) единиц времени. Метод должен представлять выборку как упорядоченное множество целых чисел 1 < Х1 < Х2 « Хо < Х. 1Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
