17. Ровно \N/P] серий. Все серии, кроме последней, имеют длину Р. (Наихудший случай.)

18. При втором проходе ничего не изменится, так как можно показать, что к-я запись какой-либо серии меньше, чем, по крайней мере, Р +1 - к записей предыдущей серии для 1 < к < Р. (Однако вряд ли существует простой способ охарактеризовать результат Р-путевого выбора с замещением, примененного после Р-путевого выбора с замещением при Р > Р.)

19. Так же, как при выводе (2), убеждаемся, что h{x, t) dx = KL dt, где на этот раз h{x, t) - I + Kt для всех ж и P = LI. Это влечет за собой x{t) = L\n({I + Kt)/I), так что, когда х(Г) = L, имеем КТ = (е - 1)7. Количество снега, упавшего с момента t = О, составляет, следовательно, (е - 1)LI = (е - 1)Р.

20. Как и в упр. 19, имеем (J + Kt) dx = K{L - х) dt; следовательно, x{t) = LKt/{I + Kt). Количество записей в резервуаре равно

и = Р = Р = гx{t)Kdt = LiKT - Пп{{1 + КТ)/1)); Jo

следовательно, КТ = al, где а « 2.14619 - корень уравнения 1 + а = е"~. Длина серии есть суммарное количество снега за время О <t <Т, а именно - LKT = аР.

21. Действуем, как описывалось в тексте раздела, но после каждой серии снегоочиститель, прежде чем вновь начать работу, ожидает, пока упадут Р - Р снежинок. Это означает, что h{x{t),t) стало теперь не KTi, а КТ, где Ti - Г есть время дополнительного падения снега. Длина серии равна LKTi, x{t) = L{l-e-), Р = LKTie и Р = Jx{t)Kdt = Р + LK{T - Tl). Другими словами, длина серии е*Р получится, если Р = (1 - (1 - в)е)Р при О < е < 1.

22. При О < t < (к - 1)Г имеем dx h = Kdt {x{t + Т) - x{t)), a при {к - 1)Т < t < Т имеем dx h = Kdt{L - x{t)), где h, как можно видеть, постоянно равна КТ в той точке, в которой находится снегоочиститель. Отсюда следует, что при 0<j<k, 0<и<1и t = (« - j - и)Т будем иметь x{t) = L(l - еFj{u)/F{k)). Длина серии есть LKT - количество снега, падающего между моментами, когда снегоочистители в установившемся режиме последовательно выходят из точки 0; Р есть количество убранного снега в конце последнего участка каждого снегоочистителя, а именно - KT{L-x{kT)) = LKTe~jF{k); можно показать, что Р = J x{t)K dt и имеет требуемый вид.

Замечания. Оказывается, что эта формула справедлива также и для к = 0. При к > I число элементов каждой серии, попадающих в резервуар дважды, равно Р" = 1о~x{t)Kdt и можно легко показать, что (длина серии) - Р + Р" = (е - 1)Р. Это свойство отметили Фрэйзер и Вонг. Является ли случайным совпадением то, что производящая функция для Fk{e) так похожа на функцию из упр. 5.1.3-11?

23. Пусть Р = рР aq = 1-р. В течение первых Ti единиц времени падающий снег берется из числа qP элементов, оставшихся в резервуаре после того, как вначале были удалены первые рР элементов в случайном порядке. Когда старый резервуар станет пустым, снег снова начнет падать равномерно. Мы выбираем Гг так, чтобы LKTi = qP. При О <t <Ti имеем h{x, t) ~ {p + qt/Ti)g(x), где д{х) - вес снега, помещаемого в резервуар из точки ж; при Tl <t <Т имеем h{x,t) = д{х) + {t - Ti)K. При О < t < Ti имеем, что g{x{t)) есть {q{Ti - t)/Ti)g{x{t)) + (Г - Ti)K, а при Tl < t < Т имеем g{x{t)) = (Г - t)K. Таким образом, h{x{t), t) = {Т - Ti)K при О < t < Г и x{t) = L(l - exp{-t/{T - Ti))). Общая длина серии составляет LK{T - Ti); общее число элементов, повторно возвращающихся в резервуар, равно LKTi (см. упр. 22); общее количество снега, счищаемого после момента Г, ecTbP=:A:r(L-a:(r)).

Таким образом, в условиях, заданных для этого упражнения, получаются серии длиной {e/s)P, если размер резервуара - (1 4- (s - l)e/s)P. Это значительно хуже результатов упр. 22, поскольку там содержимое резервуара используется рациональнее.

(Тот факт, что h(x{t),t) есть величина постоянная в таком большом числе задач, не удивителен, ведь он эквивалентен утверждению, что элементы каждой серии, получаемой в установившемся режиме системы, распределены равномерно.)

24. (а) Работает, по существу, то же доказательство; в каждой последовательности имеются серии того же направления, что и выводные серии. (Ь) Вероятность, о которой говорится в указании, есть вероятность того, что серия имеет длину n-t-1 и за ней следует у; она равна (1 - а;)"/п!, если х > у, ш {1 - а;)"/п! - {у - х)/п], если х <у. (с) Доказывается по индукции. Например, если п-я серия - восходящая, то (п - 1)-я была нисходящей с вероятностью р, так что применяется первый интеграл, (d) Находим, что f{x) = f{x) - c-pf{l - x) - qf{x); тогда /"(ж) = -2рс, что, в конце концов, приводит к f{x) = с(1 - qx - рх), с = 6/(3 + р). (е) Если р > eq, то ре + де~ монотонно возрастает при о < а; < 1 и /оре + qe" - e/l dx = (р - q){e- - 1) < 0.43. Если q < р < eq, то ре" + qe" -лежит между 2y/pqe и p+qe, т&кчто f\pe+qe~-(p+qe+2y/pqe)\ dx < {y/p-y/qef < 0.4, и если р < q, можно использовать "симметричное" рассуждение. Таким образом, для всех р и q существует константа С, такая, что /о ре + qe"" -C\dx< 0.43. Пусть <J„(x) - f„{x) - f{x). Тогда 5n+i{y) = {1-еУ-) Jipe" +qe- -C)6n{x)dx+pJ- ey-+4„{x)dx + qJ e-5n{x)dx. Следовательно, если S„{y) < an, \Sn+i{y)\ < (1 -e~) • 1.43q„ < 0.91q„. (f) При всех n > о величина (1 - x)"/n! есть вероятность того, что длина серий превышает п. (g) Jgipe" + ge-)/(x)dx-6/(3+p).

26. (а) Рассмотрите число перестановок из п -Ь г -Ь 1 элементов с п левосторонними минимумами, причем крайний справа элемент не является наименьшим. (Ь) Используйте свойство

„ г t

l<fc<n

п-г- и

по определению чисел Стирлинга в приложении Б. (с) Добавьте к средней длине г + 1, используя для получения равенства Еп>о["п](" + )/( + г + 1)! = 1 тот факт, что

Е„>о["Г]/(" + --1)!-

Формула в (Ь) получена в работе Р. Appell, Archiv der Math, und Physilc 65 (1880), 171-175. Соответственно имеем [[[]] = (г + fc)! [xz] e где f{z) = z/2 + z/3 + = -z~ ln(l - z) - 1; следовательно, Cr = [z] (r + 1 + f{z))e\ Число неупорядоченностей n объектов, которые имеют к циклов, иногда обозначаемое как [2]~,2 ра-вно [["]]; см. J. Riordan, An Introduction to Combinatorial Analysis (Wiley, 1958), §4.4. (Имеется русский перевод: Риордан Дж. Введение в комбинаторный анализ. - М.: Изд-во иностр. лит., 1963.)

27. Если при о < е < 1 Р/Р = 2(е"*-1 + в)/{1-2е + е + 2ве~), то средняя длина серии в установившемся режиме будет равна 2Р/(1 - 26 + + 2ве~). [См. Information Processing Letters 21 (1985), 239-243.]

Добосевич обратил также внимание на то, что можно продолжать использование механизма выбора с замещением, поскольку можно вводить данные из начала очереди во вспомогательном буфере и одновременно выводить их с конца этой очереди. Например, если Р = .5Р и продолжается выбор с замещением до тех пор, пока текущая серия не будет содержать .209Р записей, средняя длина серии при такой модификации возрастает от примерно 2.55Р до примерно 2.61Р. Если же Р = Р и продолжается выполнение выбора с замещением до тех пор, пока в текущей серии не останется только .314Р записей, то средняя длина серии возрастает от еР до примерно 3.034Р. [См. Сотр. J. 27

(1984), 334-339, где представлен даже более эффективный метод, названный "слиянием с замещением".]

28. Для многопутевого слияния эта проблема относительна проста, поскольку Р остается постоянным и записи обрабатываются последовательно в каждом файле. Однако при формировании начальных серий предпочтительнее изменять число записей в памяти в зависимости от их длин. Можно было бы применить пирамиду из такого числа записей, которые помещаются в памяти, используя динамическое распределение памяти, как описано в разделе 2.5. В работе М. А. Goetz, Ргос. AFIPS Joint Computer Conf. 25 (1964), 602-604, предложен другой подход: разбить каждую запись на части фиксированного размера, которые связаны между собой (они располагаются в листьях деревьев, и только "головная" часть участвует в турнире).

29. Верхние 2* узлов проигравших переходят на соответствующие позиции основных узлов. Оставшиеся узлы проигравших образуют 2* поддеревьев с 2" - 1 узлами в каждом; они подключаются к основным узлам в симметричном порядке: крайнее слева do дерево - к крайнему слева основному узлу и т. д. [См. К. Efe, N. Eleser, Acta Informatica 34 (1997), 429-447.]

30. Предположим, что к t основным узлам подключен 2"-узловой подграф полного 2"""*-узлового дерева проигравших. В этом дереве имеется один узел на уровне О и 2~ узлов на уровне I при 1 < I < п + к. Поддерево с корнем на уровне I > 1 имеет 2"+°+" - 1 узлов. Таким образом, все корни t несвязанных 2"-узловых деревьев должны находиться на уровнях < к. Каждое из этих поддеревьев должно содержать минимум один узел на уровне к, поскольку существует только 2*" < 2" узлов на уровнях < к. Отсюда

следует, что t < 2*

Но количество ребер основного графа равно, по меньшей ме-

ре, t + 2(2 - t) - 1, как следует из (ii) и (iii), поскольку существует не меньше этого количества узлов проигравших, родитель которых имеет отличную картину в основном графе.

[Необходимо предполагать, что п > к: если п = fc - 1, то существует соответствующий основной граф с 2* -Ь 2*" - 2 ребрами.]

РАЗДЕЛ 5.4.2 1.

2. После первой фазы слияния все оставшиеся фиктивные серии будут находиться на ленте Г и их будет самое большее Оп - On-i < On-i. Следовательно, все они исчезнут в течение второй фазы слияния.

3. Имеем (D[1],D[2],... ,0[Г]) = {an-an-p,an-a„-p+i,.. .,ап-ап), так что выполнение интересующего нас условия следует из того, что последовательность а неубывающая. Это