Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 72
Текст из файла (страница 72)
Интересно доказать правильность алгоритма Дахла. Алгоритм основан на наблюдении, что на шаге Р2 из Хь 14 Й следует, что Хе > 2 лля 1 < Ь < 1) 16. Можно предположить, что и < -'Х, иначе достаточно найти Х вЂ” и атементов, не входящвх в выборку. Идея заключается в том, чтобы, используя таблицу случайных данных размерности 2п, генерировать случайные числа между 1 и )т', хранить их в таблице и выбрасывать дуЫтикаты до тех пор, пока не будут сгенерированы и различных чисел. Среднее число генерируемых случайных чисел равно Ф/йг+ Ю/(79 — 1) +. +Х/(Ф-и+1) < 2п согласно упр.
З.З. 2-10, а среднее время обработки каждого числа равно О(Ц. Требуется получить выходные результаты в порядке возрастания, что можно сделать следующим образом. Если использовать таблицу упорядоченных случайных данных (упр. 6.4-66) с линейным зондированием, таблица случайных данных сформируется, как только значения будут включаться в порядке возрастания, и общее среднее число проб будет меньше зп, Так, есзи использовать монотонные случайные адреса, например [2п(к — 1)/79), для ключа Й, получится вывод ключей в упорядоченном виде в результате самое большее двух просмотров таблицы.
[См, С4СМ 29 (1986), 366-367,[ 17. Покажите по индукпии перед шагом /, что множество Я является случайной выборкой 7' — Л' — 1 + и цетых чисел из (1,...,у — 1). [С4СМ 30 (1987), 754-757. Метод Флойда может быть использован для ускорения выполнения упр. 16. Это, по существу, двойной алгоритм Дахла из упр. 15, который оперирует убмеающпмк значениями У, см. упр.
12,[ РАЗДЕЛ 3.5 1. Ь-ичная последовательность — да (см. упр. 2); последовательность [0..1) †.нет (так как предполагается только конечное множество значений элементов). 2. Последовательность 1- и 2-распределенная, только не 3-распределенная (двоичное число 111 никогда не появляется). 3. Повторите последовательность из упр. 3.2.2-17 с периодом длиной 27.
4. Если ш(п), из(п), из(н), ьч(п) считать соответствующими четырем вероятностям, то получим щ(п) + вз(п) = из(п) + гч(п) для всех п. Так что требуемый результат вытекает из сложения пределов. 5. Постедовательность начинаежя так; з, з, 1, з, з, 3 з з 1 з 1 з з з з и т.
д Когда и = 1, 3, 7, 15,..., получим и(п) ы 1, 1, 5, 5, ..., так что и(2ы ' — 1) = и(2ы — 1) = (2ы-1)/3. Значит, ы(п)/п колеблется между -' и приблизительно 1 и предел не существует. Вероятность не определена. [Методы из раздела 4,2.4 показывают, однако, что численное значенке может быть определено так: Рг((7„< 11) = Рг(старший разряд представления н + 1 в системе счисления с основанием 4 равен 1), т. е, 1о8з 2 = з.) 6. По индукции и согласно упр. 5 Рг(Я (и) для некоторого г', 1 < у' < я) = ~~ Рг(Я,(п)). Когда к -+ оо, последняя является монотонной последовательностью, ограниченной 1, так что она сходится и ~г(Я1(н) лля некоторых у > 1) > ~ Рг(Я„(п)) для всех й.
В качестве контрпримера. показывающего, что равенство будет не всегда, не трудно устроить так, что Я,(п) будет всегда верно для некоторых /0 однако Рг(Я~(п)) = 0 для всех зб 7. Пусп р; = ~,1>, Рг(ЗВ(п)), Результат предыдущего упражнения можно обобщить так: ~г(З1(п) двянекоторогоу > 1) > 2 .>,Рг(Я~(п)) для любил непересекающихся утверждений о (и).
Так что получим 1 = Рг($;,(и) для некоторых ~,у > 1) > 2„',>,Рг(ЗО-(п)длв некоторогоу > 1) > 2,'„>,р; = 1 и, следовательно, Рг(ЯВ(п) для некоторого 1 > 1) = рь Зададим е > 0; пусть у достаточно велико, так, что 2, , р; > 1 — е. г Пусть р,(Х) = (число и < Ю с Яо(к) справедливых для некоторого у > 1)/Х. Очевидно, что 2.~ еч(Ж) < 1, н для всех достаточно больших М получим 2,'.
„е4(й7) > р, — г; следовательно, чч(лГ) < 1 — рз(Ж) — - — 4г(Ф) < 1 — рз — . - — рг + е < 1 — (1 — с -р~) +е = р~ + 2е, Это доказывает, что Рг(Ям (и) для некоторого у > 1) < р~ + 2е. Значит, Рг(ЯП(п) для некоторого у > 1) = ра и требуеиыб результат получается для 1 = 1.
Из симметрии гипотез следует, что он справедлив для любого значения 1. 8. Сложите вероятности для у', у + И, у + 2д, ..., т + у' — г( в определении Е. 8. Ипззпр„ (а + Ь ) < 1ппзар„ а + 1ппзпр„ Ь; отсюда найдем, что 1ппзпр((ры — и) + . + (р,ь~ — и) ) < гпа — 2те" + гно =- О, и это может происходить только тогда, когда каждая (рз„— а) стремится к нулю. 10, В оценке суммы в равенстве (22). 11.
(сиз„) 1.-распределена, если ((/з) (2, 2й — 1)-распределена. 12. Примените теорему В с /(хп, ..,кь) = [к<игах(хм... „хь) <е[, 18. Пусть рь = Рг(с (/ начинается серия длиной й — 1) =Рг((';-, 8 [о "Ф), Г Ф[о,.д), ..., У.е. Ф[о,.Ф), и„„-, б[о,.,з)) =р (1-р) Остается преобразовать зто выражение в вероятность того, что /(и) — /(и — 1) = й.
Пусть иь(н) = (число у < и с /0) — /(/ — 1) = й); пусть рь(п) = (чигло у < и с Ц— началом серии длиной й — 1) и пусть р(п) также равно числу 1 < у < и с Ц б [и., Д. Подучим рь(/(и)) = иь(п), д(/(и)) = и. Когда и -+ оо, мы должны получить /(и) -~ оо. Следовательно, иь(п)/и = (рь(/(и))//(я)) (/(и)/д(/(и))) -з рь/р = р(1 — р) [Здесь используется только тот факт, что последовательность (й + 1)-распределена.[ 14. Пусть р» = Рг(П начало серии длиной й) =Рг(П, ~ >К,< .<('„~ь, >Паз) ((й+2) ~й+1) (й+2~ ~й+ 2),) й й+1 (й+ 1)! (й+ 2)! (см, упр, З.З.2-12).
Сейчас поступим, как а предыдущем упражнении, чтобы преобразовать это выражение в Рг(/(и) — /(и — 1) = й). [Только нужно предположить, что последовательность (й + 2)-распределенная.[ 1$, Пусть для е, ! > О рм = 1 г(Х»-и-3 =Х»-т«-3 1«Х»-т«-«1«' ' ' 1«Х»-«и Л» =' ' = ~»+ 1«Х»+а««) 2-«-м-з, для ! > 0 пуст«о« = Рг(Х,-м-т ж Х -м-«ф . 1«Х» ~) =2 и '. Согласно упр. 7 Рг(Х„не начало множества купонов) = 2,',> 4« = 3«, Рг(Х начало множества кУпонов длинон е+ 2) = 2 >оРм = 1 2 ' Поступим, как в упр. 13.
36. (Решение Р. П. Стенли (В. Р. 8«ш«!еу),) Всякий раз, когда появляется подпоследова- тельность Я = (Ь вЂ” 1), (Ь вЂ” 2), ..., 1. О, О, 1, ..., (Ь вЂ” 2), (Ь вЂ” 1), множество купонов должно закончиться в правой части Я, так как некоторое множество купонов находится полностью в первой половине Я, Вычислим вероятность того, что множество купонов начинается с позиции и, яспользуя вероятность, что последнее предшествующее появление Я произошло на позицкн и — 1, и — 2 и т. д., как в упр. 13.
18. Поступите, как в доказательстве теоремы Л, чтобы вычислить Рг и Рг, 19. (Решение Т. Герцога (Т. Пегхоб).) Да. Например, примените упр. 33 к последователь- ности (У! ггб), когда (У„) удовлетворяет определению В4 (илн даже его слабой версии). 20. (а) 2 и 3«. (когда и возрасщет, разделаем !н! пополам). (Ь) Каждая новая точка разделяет один интервал на две части.
Допустим, р равно шах«е((в+ Ь)1~ «). Тогда 1 = ~ «, !» ! < ~ ", е 1~'~«< ~ „""' р/(и+ Ь) = р1в2+ 0(1/и). Так что для бесконечного множества т выполняетсв т(,!О > 1/1и 2+ 0(1/ш). (с) Чтобы проверить указание, предположим, что !т» выбирается нз интервала с !«! конечными точками У и У,„, и положим а« = шах(ш — п,ш' — п,1). Тогда, если р = ш1~4, ««г !! ~, 1 = 2 ««", !тг"„~ > Е~~", «/(п+ в«) > 28Е„"», 1/(и+ Ь); следовательно, 2р < 1/(Нэ — Н ) = 1/!в 2+ О(1/и). (с!) 3(ы получим 4ц,..., 1~"~) = (!8 ~'-,!8 $Й,...,18 — „'", ), так как (и + 1)- « ~о~ив всегда делит наибольший кнтеРвал на ннтеРвалы длиной !8 т»тт1 и 18 3~-т3.
(1лг(айа«!оввз Маей. 13 (1040), 14-17.) 21. (а) Нет! Мы получим Рг()т'„< 1) > !(шзцр„и((2" «7 1))/!'2" '~ ) = 2 — «72 и Р1(И~» < ~1) < 1пп!и(„.,»» и(2")/2» ж «/2 — 1, поскольку и((2» нт'!) = и(2") ж (2«т«7«2«) + С(п) (Ь,с) См. 1вдалабовез МаИ, 40 (1978), 327-341. 22. Если последовательность Ь-распределена, то предел равен нулю согласно теореме В и значению интеграла. Обратно, заметим„что если /(хц..., х«) разлагается в абсолютно сходвшийся ряд Фурье а(с„...,с«)ехр(2л1(с«х«+ +с«х«)), /(хц, ..,х«) = -»»<ю,...,»«с»» то мы получим Ип«л л 2 о<» л/(!7,...,У ~~ ~)=а(0,...,0)+е„где !е,) < ~ ~)а(см.,.,с«)1, тех!)ю!,...,!««Д!» так что е, можно сделать произвольно малым.
Следовательно, прелвл равен г' г« а(0,...,0) = / ° / /(лц...,х«) «(вь .. Йх« о о и (8) выполнветсв для всех достаточно гладких функций Х, Осталось доказать, что функцию в (9) можно аппроксимировать гладкими функциями с любой требуемой точностью. 23. (а) Немедленно следует из упр. 22. (Ь) Аналогнчным путем используйте дискретное преобразование Фурье; см. П. Е. КписЬ, ААХМ уб (1968), 260-264. 24. (а) Пусть с — любое не равное нулю целое число. Покажем согласно упр. 22, что к-) 2 ~~<У А' — 7 е 'и~" -э О при А'-г со. <=е Это выполняется потому, что если К вЂ” любое положительное целое число, то получим ~"~~ 1) „'" 'ез<™"+' = К) о'сэ""с" +О(Кз).
Следовательно, понеравенству Коши к-1к-~ =о э=о к — 1 <=о к-1 к-1 з К вЂ” е~ы~~"+* + С( — ) к-1 хо<э<э<к =о 25. Если последовательность раанораспределена, то знаменатель в следствии Б приближается к —,', а числитель — к значению, полученному в этом упражнении. 26.
См. Магб. Согпр. 1у (1963), 50-54, [Рассмотрим также следующий пример А. Дж. Вотермена (А. С. ЪЧасегшап): пусть (П ) — раанораспределенная (О .. 1)-последовательность и (Х ) — оо-распределенная двоичнав последовательность. Пусть (в ы У~„„.1 или 1 — У~„<1 соответственно, когда Х равно 0 или 1, Тогда (1' ) равнораспределена и белая, однако Рг(1< = 1'+~) = 1. Пусть В' = (К, — < ) шод 1, где (< ) — любая убывающая монотонно к О последовательность, тогда ()т' ) равнораспределена и белая, однако Рг(14', < Игп+1) = 1 ) 28. Пусть (сг<) оо-распределена. Рассмотрите последовательность (-„'(Х„+ У„)).
Она З-распределена, если использова~ь тот факт, что (С ) (НЬ З)-распределена. 29. Если х = х1хз... х~ — любое двоичное число, то можно рассмотреть число и (п) к случаев, когда Лр... Хрэ, 1 = х, где 1 < р < и и р четное. Аналогично пусты, (и)— о число случаев, когда р нечетное. Пусть ва(п) + и~(п) = и,(п). Тогда иев(п) = ~' ио, ° (и) ~' к.о *(п) )' и, о, *(и) ~' у,, о(п), (Ь) Когда 4 = 1, то нз упр. 22 следует, что ((о1п+ ос) шой 1) равнораспределена тогда и только тогда, когда о1 -- иррациональное число, Прн И > 1 можно воспользоваться (а) и инлукцией по Ы.
(Асса ЗХасЬ. 56 (1931), 373-456. Результат в (Ь) ранее был получен более сложным методом Г. Вэйлом (Н. ЪЧеу1, ХХасйг. Сеэейз<Лауг бег 15мз. Сбгйпбеп, МаСЬ,-РЬуз. КЬ (1914), 234-244). С помощью подобных аргументов доказыиается, что полиномиальпая последовательность равиораспределена, если по крайней мере один из коэффициентов цю ..., сп — иррациональное число.) где ю в зтях суммах имеют 2х нижних индексов, 2х — 1 из которых — звездочки (обозначающие, что по ним суммируют — каждая сумма берется по 2гь ' комбинаций нулей и единиц), и где " " означает приближенное равенство (за исключением ошибки самое болыпее 2х вследствие условий на концах), Поэтому находим, что -„'2хке (и) = ~~ (2 г о ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
