AOP_Tom3 (1021738), страница 69
Текст из файла (страница 69)
= 11 при 1 < 1' < й. Отсюда получаем ар(1ы...,1е) = ~~~ а,(1~ы...,1зь)...акр„...,1рь), ~м~..чзэс «=и 0 й+ ' "+г Р е =ц что эквивалентно искомому результату. В разделе 5.1.3 было проанализировано среднее значение Ьь — длины 1с-й серии при Р = 1 (эти значения приведены в табл. 5.1.3 — 2). Из теоремы К следует, что средняя длина й-й серии при любом Р в Р раз больше средней длины при Р = 1; она равна 1.ьР.
Дисперсия также в Р раз больше, так что стандартное отклонение длины серии пропорционально ИГР Эти результаты были впервые получены Б. Дж. Гэсснер (В. У. Саззпег) около 1958 года. Таким образом, .первая серия, полученная для случайных данных алгоритмом К, будет иметь длину, приближенно равную (е — 1)Р ск 1.718Р записей, вторая— (ез — 2с)Р кк 1.952Р, третья — 1.996Р; длина следующих серий будет очень близка к 2Р, пока мы не дойдем до последних двух серий (упр. 14 . Стандартное отклонение длины большинства этих серий приближенно равно (4е — 10)Р— 0.934 ГР [САСМ 6 (1963), 685 — 687). Кроме того, согласно упр.
5.1.3 — 10 сузьмарная длина первых?с серий будет довольно близка к (2?с — -') Р со стандартным отклонением (( зй?с + з ) Р) '1~. Производящие функции рл(з, з,..., к) и 9~(1,..., 1, з) выводятся в упр. 5.1.3-9 и 11. В приведенном выше анализе предполагалось, что исходный файл бесконечно длинный, но доказательство теоремы К показывает, что такая же вероятность а„(12,...,1ь) получилась бы при наличии любой случайной исходной последовательности, содержащей, оо крайней мере, 1~+ .+1ь РР элементов.
Значит, полученные результаты применимы для файла размером, скажем, Ю ) (29 + 1)Р в силу малой величины стандартного отклонения. В дальнейшем мы познакомимся с рядом приложений, в которых схема слияния требует, чтобы одни серии были восходящими, а другие — нисходящими. Поскольку остаток, накапливающийся в памяти у конца восходящей серии, как правило, содержит числа, в среднем меньшие, чем случайные данные, то изменение направления упорядочения приводит к уменьшению средней длины серий.
Рассмотрим, например, снегоочиститель, который должен разворачиваться каждый раз по достижении конца прямой дороги; он будет очень быстро передвигаться по только что очищенному участку. В случае изменяемого направления длина серий для случайных данных изменяется между 1.5Р и 2Р (см. упр. 24). УПРАЖНЕНИЯ 1.
[10) Каким будет шаг 4 в примере для четырехпутевого слияния, приведенном в начале этого раздела? 2. [1к) Какие изменения произошли бы в дереве на рис, 63, если бы ключ 661 был заменен ключом 612? 3. [16) (Э. Ф. Мур (Е. Г. Мооге).) Что получится в результате применения четырехпутевого выбора с замещением к последовательным словам приведенного ниже предложения: тавгвсоге аай ветен уеагв аба овг 1асЬегв ЬговЕЬс 1агсЬ оп Сйьв сопС> аевх а пев ваС1ев спасе>сей 1в 11Ьегеу авй йе61сасей са сье ргераэ>с1ов сьас а11 иев аге сгеасей еова1.
(Используйте обычный алфавитный иорндок, рассматривая каждое слово как адин ключ.) 4. [10] Примените четырехггутевой натуральный выбор к предложению из упр. 3, используя дополнительный буфер емкостью 4. б. [ОО) Верно ли, что выбор с замещением, использующий дерево, работает, толька если Р есть степень 2 или сумма двух степеней 2? 6. [15] В алгоритме К указывается, что Р должно быть > 2. Какие атносителыю небольшие изменения необходимо сделать в этом ал>т>рить>е, чтобы он правильна работал для всех Р > 1? 7.
[17) Чта делает алгоритм К в случае отсутствия исходной информации? Н. [50] Алгоритм К использует искусственный ключ "са", который должен Г>ыть больше, любога возможного ключа. Покажите, что ехли бы какой-нибудь реальный ключ оказался равным аа, то алгоритм мог бы ошибиться, и объясните, как изменить алгоритм в случае, когда реализация "настоящего" аа неудобна. 9. [50) Как бы вы изменили алгоритм К, чтобы он выводил одни заданные серии (в зависимости от НС) в порядке возрастания, а другие — в порядке убывания> 10. [Об] Начальная установка указателей 105ЕН на шаге К1 обычна не соответствует никакому действительному турниру, так как внешний узел Р ь 1' может не лежать в поддереве с вершигюй во внутреннем узле 1. Объясните, почему алгоритм К все равна работает.
[Указание. Будет ли работать алгоритм К, если множеству (10525(ЬОС(Х[0])),..., 105ЕН(ЬОС(Х[Р— 1)))) присваивается на шаге К1 произеольнал перестановка множества [ЬОС(Л [О)),...,100(Х[Р— 1)) )?] 11. [МЯб] Верно ли утверждение, что для случайных исходных данных вероятность того, что НЕТ(О) ( 115ТНЕТ на шаге К4, приГ>лиженно равна -'? 12. [М(б) Детально проанализируйте количество выполнений каждой части алгоритма К.
Например, как часто выполняется перестановка иа шаге Кб? 13. [10) Почему вторая серия, полученная при выборе с замещением, обычна длиннее первой? ь 14, [НМЕб] Используйте аналогию со снегоочистителем, чтобы оценить среднюю длину двух последних серий, которые получены при выборе с замещением, примененном к длинной последовательности исходных данных. 15. [ЯО] Верно ли, что погледняя серия, полученная ори выборе с замещением, никогда не содержит более Р записей? Проанализируйте свой ответ. 1Ь. [Мйб) Найдите "простое" необходимое и досгаточное углавие того, что файл К> К>... Ки будет полностью упорядочен за один проход Р-пу>евага выГюра с замещением. Какова вероятность этого события как функции Р и А>, если исходными дышыми служит случайная перестановка множества [1, 2,..., А>1? 17.
[50) Что получается в результате работы алгоритма К., когда исходные ключи представляют собой невазрастающую последовательность К» 1Г> » Кл? ° 19. [35) Чта произойдет, если вновь применить алгоритм К к файлу, полученному в результате работы ал> оритма К? 19. [НМОО] Используйте аналогию со снегоочистителем, чтобы доказать, что первая серия, полученная при выборе с замещением, имеет длину примерно (е — 1) Р записей.
20. (НМЯ4) Какую примерно длину имеет первая серия, полученная при натуральном выборе, когда Р = Р'? ь 21. (НМЕЗ) Определите приблизительную длину серий, полученных посредством натурального выбора при Р' < Р. 22, (НМ4 В) Целью этого упражнения является определение средней длины серий, получаемых при натуральном выборе при Р' > Р. Пусть к = 1+  — действительное число > 1, где й = 1к), а В = к гоос1 1. Рассмотрим функцию Г(к) = Рь(В), где Рь(В) — полиномы, определяемые производящей функцией Гь(В)х~ = е ~*/(1 — хе~ '). ьйо Таким образом, Го(В) = 1, Г~(В) = е — В, Рз(В) = ео — е — еВ+ 1В~ и т. д.
Предположим, что в момент времени О снегоочиститель начинает моделировать процесс натуральнога выбора, и допустим, что за Т единиц времени позади него упадут ровно Р снежинок. В этот момент второй снегоочиститель начинает тот же путь, занимая в момент времени 1+ Т то же положение, которое занимал первый снегоочиститель в момент й В конце концов, к моменту кТ позади первого снегоочистителя упадут ровно Р' шгежинок; второй снегоочиститель очищает остаток дороги и исчезает.
Используя эту модель для интерпретации иатуральнага выбора, покажите, что длина серии е~Г(к)Р получается при г?г=~ ° ° г( г( ) — Г'к -О). о=о 23. [НОВ] В предыдущем упражнении проанализирован натуральный выбор в том случае, когда записи из резервуара всегда читаются в там же порядке, в котором они записывались; "первым включается — первым исключается". Оцените длину серий, которая получилась бы, если бы содержимое резервуара, оставшееся от предыдущей серии, читалось в совершенно случайном порядке, как будто записи в резервуаре тщательно перемешивались между серинми.
24. (НМЮВ) Цель этага упражнения — анализ последствий, вызванных случайным изме- нением направления упорядочения серий в выборе с замещением. а) Пусть д~ (еп хю..., хь) — та же производящая функция, что и в теореме К, на для каждой из й серий определено, является ли она восходящей либо нисходящей. Например, мы можем считать, что все серии с нечетными номерами — восходящие, а с четными — нисходящие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
