AOP_Tom2 (1021737), страница 179
Текст из файла (страница 179)
Каждое /-транспоиирование является взвил»но однозначным с операциями х + у' = х + у и дх' ду' = дх ду. 33. Испольэовать У» как начальное значение для других генераторов случайных чисел (возможен линейный конгруэнтный генератор с другим множителем): в качестве множителя Взять одну из У2, Пз, РАЗДЕЛ 3.4.2 1. Сушествует (~ ') способов выбора и — т записей из последних Х вЂ” 1 и (~ ' ',) способов выбора и — т — 1 записей из Ю вЂ” 1 — 1 после выбора (1+ 1)-й записи. 2.
Переход от шага Б3 к шагу Б5 невозможен, еати количество записей, которые осталось проверить, равно п — т 3. Не будем путать условную и безусловную вероятности. Значение т зависит от случайного выбора первых 1 элементов. Если взять среднее па всем возможным выборам, которые могут появиться среди этих элементов, то можно найти, что (и — т)/(Г»' — 1) в среднем точно равно и/1»'. Например, рвссматрил» второй элемент. Если первый элемент отобран в выборку (это происходит с вероятностью и/Ф), то второй элемент выбирается с вероятностью (и — 1)/(Ю вЂ” 1); если первый элемент не выбирается, та второй выбирветсн с вероятностью и/(1»' — 1). Полная вероятность выбора второго элемента равна (и/1»)((п — 1)/(1»' — 1)) + (1 — п/Ж)(п/(14 — 1)) = и/Х. 4.
Из алгоритма следует, что и — т1 и — (т — 1) р(т,1+ 1) = (1 — — ) р(т,с) + р(т — 1,1). М вЂ” 1) Ю вЂ” 1 Требуемая формула может быть доказана индукцией по А в частности р(п, л») = 1. 5. В обозначениях упр. 4 вероятность того, что 1 = 1», по окончании работы алгоритма равна О» = р(п й) — р(п и — 1) = (» '»)/(~). Среднее равно ~"~~ в(сд» = (Ю+ 1)п/(и+ 1), 6. Так же, как в упр. 5, получим 2» Ь(Ь+ 1)о» = (Ю+ 2)(1»'+ 1)п/(и+ 2); дисперсия, следовательно, равна (1»'+ 1)(д» вЂ” и) и/(и + 2)(п + 1) . Ч. Предположим, есть выбор 1 < х» < хз « х < 1»', Пусть хо = О, х„»» = д»+ 1.
Выбор получен с вероятностью р = П,«,, р», где (й» вЂ” (1 — 1) — и+т)/(1у — (à — 1)) для х <1<х„.„; 1н = (и — т)/(гг — (1 — 1)) для 1 = х„,.» ь Знаменатель произведения р~ равен Ю!, числитель содержит члены»з' — и, 1»' — и — 1,, 1 для тех 1„которые не равны хы а члены и, и — 1, ..., 1 для тех С», которые ровны х». Следовательно, р = (1»' — п)! а!/1»'Ь При.мер. и = 3, Х = 3, (хи х» хз) = (2, 3 1) р = в у в» 4 з» 1 (а),(О ь) = (к»)/(л) = (л„")/(х) из ('„") выбоРок, если пРопУстить первые (с записей. (Ь) Присвоить Х +- Ь вЂ” 1, гле Ь является минимальным с У > Рг(Х > 1). Затем выполнять присвоения Х +- О, р +- Х вЂ” и, о» вЂ” М, В» — р/О и т. д.
до тех пор, пака бг < й. Присвоить Х +- Х + 1, р +- р — 1, о»- д — 1, В+- 14р/о. (Этот метод хорош, когда и/Ж, скажем, > 1/5. Можно предположить, что и/1»' < 1/2, иначе лучше выбрать 1г' — и меембраннмх записей.) (с) Рг(»п1в(уп,...,Ул- »») > й) = П," „' Рг(Ул —, > й) = П,":,'(Д вЂ” 1с й)/Р— 1). (Этот метод хорош, если, скажем, и < 5.) (с1) (См. упр, 3.4.1 — 29.) Значение Х с- [Н(1 — с>'г")) требуется отбросить с вероятностью, равной только 0(и(йг). Точные детали тщательно проработаны в САСМ 27 (1984), 703 — 718, а практическое осуществление приведено в АСМ Тгапя. МаСЛ. Яойпаге 13 (1987)> 58 — 67. (Этот метод хорош, когда, скажем, 5 < и < 1Лг.) После пропуска Х записей и выбора следующих присвоим и +- и — 1, Аг+- Ж вЂ” Х вЂ” 1 и будем повторять процесс до тех пар, пака и = О.
Подобное приближение ускоряет метод резервуара [см. АСМ Тгапз. МаСЛ. БоН>гаге 11 (1985), 37 — 57) 9. В резервуар будет помещена семь записей: 1, 2, 3, 5, 9, 13, 16. В окончательной выборке содержатся записи 2, 5, 16. 10. Удалить шзг Кб и переменную т Заменить таблицу 1 таблицей записей,инициализированных первых и записей на шаге К1, и, заменив М-е значение таблицы, перейти в алгоритме к шагу К4. 11. Поступая, как в разделе 1.2 10, в котором рассматривался частный случай, когда и = 1, получаем, что производящая функция равна (и-Ь1 и+1 )(и+2 и-Ь2 ) ( Н >У ) среднее значение равна и + 2,„<г< (иггс) = и(1 + нл — и ), а дисперсия оказывается равной и(Ня — Н„) — и (Ня — Н„). 2 (>> г2) 12. Заметим, что >г ' = (Ь>1) .. (Ь>3)(Ь>2), поэтому находим алгоритм, который переводит представление я в з г.
Присвоить Ь, +- г для 1 < 2 < Ь Затем лля > = 2, 3, ..., 1 (в таком порядке) произвести взаимный обмен Ь> сч Ь, Наконец для 2 = с,, 3, 2 (в таком порядке) присвоить Ь,, +- Ь, (Алгоритм основывается натам факте, что (агг)сг> = >г>(Ь>г)) 13. Перенумеровав колоду О, 1, ..., 2и — 2, находим, чта номер (2х) шас1 (2и — 1) о рзз присвоен карте с номерам х, .в то время как помер (х + 1) шас1 (2и — 1) с рвз присвоен карте с номером х. Получим (с следует из о) = со = осс. Значит, произведение любого количества с н о можно привести к виду о'с".
Также 2ГС~" И сн 1 по модулю (2и — 1). Поскольку о" Оы ц и с>" ' — тождественные перестановки, то возможно не более (2и — 1)со(2и — 1) компоновок. (Точное число различных компоновок равно (2и — 1))с, где Л равно порядку 2 по модулю (2и — 1). Для случая, когда о~ = с', с' устанавливает нарту О, о" = с' = тождества.) Дополнительные детали приводятся в ЯАМ Кот>е>г 3 (1961), 293-297 14.
(а) ~~. Это можно установить, пе обращая внимаяия на то, где именно была сдвинута карта, кроме случая, когда карта была взята из первых трех или последних двух позиций. (Ь) з. Три разрезании и перетасовки приведут к перемешиванню самое большее восьми циаврвотюансик Пад>ЮСЛЕдаяатЕЛЬГ>аотгйа а>к +>~ О . ас~ + ц ~~О . Звапит, подпоследовательности г оз ос заблокированы.
[Несколько магических трюков основано на там факте, чта три рашрезания и перетасовки являя>тся совсем неслучайными; см. Магбп Сзхс1пег, МасЛешабса! Ыабгс 5Лов (КпорГ, 1977), гл. 7.] 15. Присвоить у; +- г' для 1 — и < Т < Ф. Затем для 7 = й 1 — 1, ..., С вЂ” и + 1 проделать следующие операции. присвоить /с с — [7Ц + 1 если (с > с — и, присвоить Х, с- 1'г, н 1>ь с — 1', иначе, если Ь = Л", для некоторых с > 7 (мажно использовать таблипу идентификаторов алгоритма), присвоить Х, с- 1; н У, +- Ъ;; иначе — присвоить Х> с — Л. (Идея основана па предположении,что И „аг, ..., 1> представляют Хг „+г,, Л, и, вели с > 2 и Х, < 1 — и, на предположении, что 1, представляют Лх, в исполнении алгоритма Р.
Интересна доказать правильность алгоритма Двхла. Алгоритм основан на наблюдении, чта на шаге Р2 из Хь ф (с следует, что Хо > г для 1 < /с < >1) 16. Можно предположить, что и < 1Х, иначе достаточно найти 2Зг — и элементов, не входящих в выборку Иден заключается в том, чтобы, используя таблицу гчучайных данных размерности 2п, генерировать случайные числа между 1 и /4!, хранить их в таблице и выбрасыиать дубликаты до гих пор, пока не будут сгенерированы и различных чисел.
Среднее число генерируемых случайных чисел равно 74г/Гч' + 24'/(74 — 1) + +74!/(Х-пч1) < 2п согласно упр. 3 3 2 19, а среднее время обработки каждого числа равно 0(1). Требуется получить выходные результаты в порядке возрастания, что можно сделать следующим образом. Если использовать таблицу упорядоченных случайных данных (упр. 6.4-66) с линейным зондированием, таблица случайных данных сформируется, как только значения будут включаться в порядке возрастания, и общее среднее число проб будет меньше вп. Так, если использовать монотонные случайные алреса, например (2п,(44 — 1)/Х], для ключа Ь, получится вывод ключей в упорядоченном виде в результате самое бщгьшее двух просмотров таблицы.
(См. САСМ 29 (1986), 366 — 367.] 17. Покажите по индукции перед шагом у, что множество Я является случайной выборкой 1 — Х вЂ” 1 -!- и целых чисел из (1,..., ! — 1). ]САСМ ЗО (1967), 754-757. Метод Флойда может быть использован для ускорения выполнения упр 16. Это, по существу, двойной алгоритм Дахла из упр.
15, который оперирует убывающими значениялги 1; см. упр. 12.] РАЗДЕЛ 3.5 1. Ь-ичная последовательность — да (см. упр. 2); последовательность (О .. 1) — нет (так как предполагается только конечное множество значений элементов), 2. Последовательность 1- и 2-распределенная, только не 3-распределенная (двоичное число 111 никогда не появляется). 3. Повторите последовательность из упр.
3.2.2-17 с периодом длиной 27. 4. Если ьт(п), 442(п), ьз(п), гч(п) считать соответствующими четырем вероятностям, то получим 42! (и) + иг(п) = иг(п) + 424(п) для всех и. Так что требуемый результат вытекает из сложения пределов. 5. Последовательность начинается так: —, —, —, — —, —, —, —, —, —, —, —, -, —, — и т. д. ! 2 2 ! ! ! 1 2 2 2 2 2 2 2 2 Когда и = 1, 3, 7, 15,, гголучим ! (и) = 1, 1, 5, 5, ..., так что ь(2~~ ' — 1) = и(2~~ — 1) = (22"-1)/3. значит, и(п)/и колеблется между -' и приблизительно 2 и предел не существует. Вероятность не определена. (Методы из раздела 4.2.4 показывают, однако, что численное значение малюет быть определено так: Рг(5!„< -') = Рг(старший разряд представления и+ 1 в системе счисления с основанием 4 равен 1), т е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
