AOP_Tom3 (1021738), страница 192
Текст из файла (страница 192)
(Оба ключа принадлежат одной подпоследовательности из доказательства теоремы К.) 13. После завершения первой серии в памяти обычно остаются ключи, меньшие срелнего, так как именно из-за своей малой величины они не полю»и в первую серию. Поэтому во вторую серию выводится большее количество меньших ключей. 14. Предположил», что снег внезапно прекращается, когда снегоочистнтезь находится в случайной точке и, О < и < 1 (после достижения установившегося состояния). Тогда предпогледняя серия содержит (14-2»» — и') Р записей, а последняя — и Р.
интегрирование по йо дает среднее количество записей (2 — -') Р в предпоследней серии и -,'Р - — в последней. 15. Неверно. Последняя серия может быть сколь угодно длинной, но только в сравнительно редком случае, когда в момент исчерпания исходных данных все записи в памяти принадлежат одной серии. 16. Тогда и талька тогда, когда каждый элемент имеет меньше Р инверсий. (См. разделы 5.1.1 и 5.4.6.) Рассматривая таблицу инверсий, находил» вероятность, которая равна 1 при А» < Р и Р'л ~Р!//»»! при»»' > Р. (Практически, однако, сортировка за один проход не такое уж редкое явление, поскольку люди часто в целях предосторожности склонны сортировать файл при малейшем подозрении, что порядок в нем нарушен.) 1?.
Ровно [?4/Р) серий. Все серии, кроме последней, имеют длину Р. (Наихудший случай.) 13. При втором проходе ничего не изменится, так как можно показать, что к-я запись камой-либо серии меньше, чем, по крайней мере, Р+ 1 — ?г записей предыдущей серии для 1 < А < Р. (Однако врал ли существует простой способ охарактеризовать результат Р'- путевого выбора с замещением, примененного после Р-путевого выбора с замещением при Р' > Р.) 19. Также, как при выводе (2), убеждаемся, что б(х,г) ох = Кбо1, где на этот раз Л(х, 1) = /+ К1 дчя всех х и Р = П. Это влечет за собой х(г) = Е!о((/+ Кг)/1), так что, когда х(Т) = Е, имеем КТ = (е — 1)й Количество снега, упавшего с момента 1 = О, составляет, следовательно, (е — 1)Е1 = (е — 1)Р.
20. Как и в упр, 19, имеем (1+ К1) Их = К(Š— х) йй следовательно, х(С) = ЙК1/(1+ К1). Количество записей в резервуаре равно гг бу = Р = Р' = // (1)К 31 = Цкт — 11о((Т+ КТ)/Т)); о следовательно, КТ = ау, где о 2.14б19 — корень уравнения 1+ а = е" '. Длина серии есть суммарное количество снега эа время 0 < 1 < Т, а именно — ЙКТ = оР. 21. Действуем, как описывалось в тексте раздела, но после каждой серии снегоочиститель, прежде чем вновь начать работу, ожидает, пока упадут Р— Р' снежинок.
Это означает, что 6(х(1), 1) стало теперь не КТм а КТ, где Т, — Т есть время дополнительного падения снега. Длинасерии равна йКТц х(Г) = Е(1 — е Ыг), Р = ХКТ~е ~?П и Р = / х(Г)К ог= Р+ Х К(Т вЂ” Т~ ). Другими словами, длина серии е Р получится, если Р' = (1 — (1 — д) е )Р приб<д<1. 22. При 0 < 1 < (к — 1)Т имеем ох 6 = К01 (х(1+ Т) — х(1)), а при (к — 1)Т < Ь < Т имеем лх л = ко1(е — х(г)), где б, как можно видеть, постоянно равна кт в той точке, в которой находится снегоочиститель. Отсюда следует, что прн 0 < д < к, 0 < и < 1 и Г = (к — у — и)Т будем иметь х(1) = ь(1 — е" ~Г,(и)/Г(к)).
Длина серии есть АКТ количество снега, падающего между моментами, когда снегоочистители в установившемся режиме последовательно выходят из точки 0; Р есть количества убранного снещ в конце последнего участка каждого снегоочистителя, а именно — КТ(ь — х(аТ)) = т КТе /Р(к)' можно показать, что Р' = /е" х(1)Ко1 и имеет требуемый вид. Замечания. Оказывается, что эта формула справедлива также и для?г = О.
При Й > 1 число элементов каждой серии, попадающих в резервуар делягам, равно Р" (е" х(1)Кой и можно легко показать, что (длина серии) — Р'+ Р" = (е — 1)Р. Это свойство отметили Фрейзер и Вонг. Является ли случайным совпадением то, что производящая Функция для Рь(д) так похожа на функцию из упр. 3.1.3 — 11? 23. Пусть Р = рР' и д = 1 — р. В течение первых Т~ единиц времени падакнций снег берется из числа дР' элементов, оставшихся в резервуаре после того, как вначале были удалены первые рР' элементов в случайном порядке. Когда старый резервуар станет пустым, снег снова начнет падать равномерно.
э1ы выбираем Т~ так, чтобы 1КТь = дР' При 0 < 1 < Т~ имеем 6(х,г) = (р 4-91/Г~)д(х), где д(х) — вес снега, помещаемого в резервуар иэ точки х; при Ть < 1 < Т имеем 6(х,1) = д(х) + (à — Т~)К. При 0 < г < Т~ имеем, что д(х(Г)) есть (д(Тв — 1)/Ть)д(х(Г)) + (Т вЂ” Ть)К, а при Т~ < 1 < Т имеем д(х(1)) = (Т вЂ” 1)К. Таким обдаэом й(х(1), 1) = (Т вЂ” Т~)К при 0 < 1 < Т и х(1) = Е(1 — екр( — 1/(Т вЂ” Т~))). Общая длина серии составляет ЬК(Т вЂ” Т~ ): общее число элементов, повторно возвращающихся в резервуар, равно СКТ~ (см. упр.
22); общее количество снега, счищаемого после момента Т, есть Р = КТ(ь — х(Т)). Таким образом, в условиях, заданных для этого упражнения, получаются серии длиной (е'/з)Р, егти размер резервуара — (1+ (э — Це'/з)Р Это значительно хуже результатов упр. 22, поскольку там содержимое резервуара используется рациональнее. (Тот факт, что Ь(х(1), !) есть величина постоянная в таком большом числе задач, не удивителен, ведь он эквивалентен утверждению, что элементы каждой серии, получаемой в установившемся режиме системы, распределены равномерно.) 24.
(а) Работает, по существу, то же доказательство: в каждой пощ»едовательности имеются серии того же направления, что и выводные серии. (Ь) Вероятность, о которой говорится в указании, есть вероятность того, что серия имеет длину и+1 и за ней следует 9; она равна (1 — х)"/и?, если х > у, и (1 — х)"/»»! — (р — х)"/и!, если х < у. (с) Доказывается по индукции. Например, если и-я серия — восходящая, то (и — 1)-я была нисходящей с вероятностью р, так что применяется первый интеграл. (»!) Находим, что / (х) = У(х) — с-р/(1-х) -д/(х); тогда /»»(х) = — 2рс, что, в конце концов, приводит к /(х) = с(1 — дх — рх»), с = б/(3 + р).
(е) Если р > ед, то ре'+ де»" монотонно возрастает при 0 < х < 1 и (р]ре + дг' е»7»]»!х = (р — д)(ем» вЂ” 1)» < О 43, Егли д < р < ед, то ре'+ де' лежит между 2/рце и р+де, так что /е ]ре +де' — -,, '(р+де+2 /рде )]»4х <» (»/рр —,/де) < О 4, и если р < д, можно использовать "симметричное" рассуждение. Таким образом., для всех р и д существует константа С, такая, »то / ]ре* + де' * — С]»(х < 0.43.
Пусть 6 (х) = / (х) — /(х), Тогда 6„ь»(9) = (1 — е" ')/' (ре*+де' * — С)6„(х)»(х+р/е "е" 'э'6 (х)»1х+д/ е" *6„(х)»7х. Следовательно, если 6„(у) < а, ]6„т»(у)] < (1 — е" ') 1 43о„< 0.91о„, Н) При всех и > 0 величина (1 — х)"/и! есть вероятность того, что длина серий превышает и (8) ]„(ре + де' *)/(х)»!х = б/(3-!-р). 28. (а) Рассмотрите чиш»о перестановок из п + г + 1 элементов с и левосторонними минимумами, причем крайний справа элемент ие является наиченыним. (Ь) Используйте свойство по определению чисел Стирлинга в приложении Б.
(с) Добавьте к средней длине г + 1, используя для получения равенства Я„> [~."](»» -!- г)/(и -!- г + 1)! = 1 тот факт, что К..е[,. ]/(и + - 1)' Формула в (Ь) получена в работе Р. Арре!1, АгсЫт»1ег Масб. пл»! РЬуз!/» 85 (1880), 171-175, Соответственно имеем [[ь]] = (г+ й)([х"х"]е д 1, где /(х) = г/2+ х~/3-Ь. — х ' (п(1 — х) — 1; следовательно, с„= ]х" ] (г + 1 + /(г)) е~»*!. Число неупорядоченностей и объектов, которые имеют !» циклов, иногда обозначаемое как [ь] ~, равно [["„ь]]; см. Л. К!ог»!ап, Ап 1л»го»(всс»оп»о Сошб!пасох»а! Ава!узй (»»»!!еу, 1958), 34.4 (Имеется русский перевод: Риордан Дж.
Введение в комбинаторлый анализ. — Мз Изд-во иностр. лиг., 1953.) 27. Если при 0 < В < 1 Р /Р = 2(е — 1+В)/(1 — 29+ 6~+ 2Ве ~), то средняя длина серии в установившемся режиме будет равна 2Р/(1 — 2В+ В + 2Ве ~). [См. 1л/оппайол Ргосезгйвб Ъегсегз 21 (1985), 239 — 243.] Добосевич обратил также внимание на то, что можно продолжать использование механизма выбора с замещением, поскольку можно вводить данные из начала очереди во вс»»омогатель»»ол» буфере и одновременно выводить их с конца этой очереди.
Например, если Р' = .5Р и продолжается выбор с замещеииел» до тек пор, пока текущая серия не будет содержать .209Р записей, средняя длина серии при такой модификации возрастает от примерно 2.55Р до примерно 2.51Р. Если же Р' = Р и продолжается выполнение выбора с замещением до тек пор, пока в текущей серии не останется только .314Р записей, то средняя длина серии возрастает от еР до примерно 3,034Р. [См.
Со»пр. Х 27 (1984), 334 — 339, где представлен даже более эффективный метод, названный "слиянием с замещением".) 28. Дая многопутевого слияния эта проблема относительна проста, поскольку Р остается постоянным и записи обрабатываются последовательно в каждом файле. Однако при формировании начальных серий предпочтительнее изменять число записей в памяти в зависимости от их длин. Можно было бы применить пирамиду из такого числа записей, которые помещаются в памяти, используя динамическое распределениепамяти,как описано в разделе 2ть В работе М. А. Соегх, Ргос. АР1РБ Зотг Сотригег Сопб 25 (1964), 602 — 604, предложен другой подход: разбить каждую запись иа части фиксировшшого размера, которые связаны между собой (они располагаются в листьях деревьев, и только "головная" часть участвует в турнире).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
