17. Если положить ао = ai = О, то

Хп = an + (")(-l)=a./(m*- - 1) = (?)(-l)*a.m*-V" - 1).

18. Для решения (4) необходимо преобразование an = [п> 1], а именно - Оп = [п = 0] - 1 + п; следовательно, для N > 2 получим An = 1 - Un + Vn, где Un = K{N,0, М) и Vn = K{N, 1,М) (в обозначениях из упр. 19). Аналогично для решения (5) нужно взять о„ = п - [п = 1] = а„ и получить Cn = N + Vn для N >2.

19. При 3 = 1 имеем Vn = К{п, 1,т) = n((lnn + 7)/lnm- -<Jo(n- 1))+ 0(1), а при s > 2 имеем K{n,s,m) = {-iyn(l/lnm + 5s-i(n - s))/s{s - 1) + 0(1), где

Ss{n) =-- yK(r(s - 27rifc/lnm)exp(27rifclog , n))

представляет собой периодическую функцию от log п. [В этом выводе использовался тот факт, что

Kin+s,s,m)li-l) . ) = 1,2 , )

Для малых m и S весьма малым является S (см. упр. 5.2.2-46). Обратите внимание на то, что Ss{n - о) = Sa{n) + 0{п~) при фиксированном о.]

20. Для случая (а) положим Оп = [п>«] = 1 - Et=o[" -li Д-"*" () - а„ = п -IZfc=o- в случае (с) требуется найти решение рекуррентного соотношения

(m-l)"-*!/, прип>8, при П< S.

Подставив Хп = Уп-п, получим рекуррентное соотношение рассмотренной в упр. 17 формы, где

a„ = (l-M-);()[n = fc].

Таким образом, используя обозначения из предыдуш;их упражнений, получаем следующие ответы: (а) I - К{М,0,М) + KiN,l,M)-----Ь (-l)-A:(Ar,s,M) = Ar/(slnM)-

N{S-i{N) + So{N -l) + Si{N- 2)/2Л + + S,-i{N - s)/s{s - 1)) + 0(1); (b) N-{N + K{N,l,M) - 2K(N,2,M) + + {-iy-hK{N,s,M)) = (lniV-1-7 - Hs-i)/lnM + 1/2 -(<Jo(iV -1)+ Si{N - 2)/l + + 5s-i{N - s)/{s - 1)) + 0{N-); (c) ЛГ->(лг + (1 - M) x EL2(-1)(2)W fc, M)) = 1 + i(l - M-)((s - l)/ln M + <J,(iV - 2) + • • + <J.-i(iV - s)) + 0(ЛГ-1).

21. Пусть всего имеется Адг узлов. Число непустых ссылок равно An - 1, а количество узлов без ссылок - N, так что общее количество пустых ссылок составляет MAn - An + 1 - N. Для получения среднего количества пустых ссылок в любом фиксированном узле следует разделить найденное значение на М. [Среднее значение An приведено в упр. 20, (а).]

22. Для каждой из М последовательностей лидирующих битов имеется такой узел, что, по меньшей мере, два ключа начинаются с этой последовательности. Вероятность того, что с нее начинается ровно fc ключей, составляет

()м-Чl-м-r-

так что среднее количество узлов луча на уровне I равно М(1-(1-М~))-ЛГ(1-М~)~.

23. Рассмотрим более общую задачу - случай для произвольного s (как в упр. 20). Если на уровне I имеется а; узлов, то в них содержится ai+i ссылок и Мщ - ai+i позиций, в которых поиск может быть неудачным. Таким образом, среднее количество проверок цифр составляет Y!,l>oi + ~ = J2i>o~4- Используя формулу для о; в случайном луче, получаем

KiN+l,l,M)-2KiN+l,2,M) + --- + i-iy{s+l)K(N+l,s+l,M)

in М Л 1 S

24. Необходимо найти решения рекуррентных соотношений xq = xi = уо = yi = О,

Xn=m- („ " „ ) ("1+-- + а:п„ + К/О])

для п > 2, где а„ = m(l - (1 - 1/m)") и Ь„ = (т - 1)п(1 - (1 - 1/т)" ). Согласно упр. 17 и 18 ответы таковы: {ъ) xn = iV + Vjv - f/Af - [iV = 1] = Лдг + iV - 1 (этот результат может быть получен непосредственно, поскольку количество узлов в лесу всегда на iV - 1 больше количества узлов в соответствующем луче!); (Ь) ум IN - \{М - \)Vn /N = (М - l)((lniV + 7)/1п М-\- 5o{N - 1)) + 0{N-).

25. (а) Пусть Лл = M{N - 1)/{М - 1) - En; тогда при iV > 2 имеем (1-М-)£;лг = М-1-M{l-1/Mf- +М- YoKkKN (fc)(M-l)-*£:*,. Поскольку М-1 >М(1-1/М)-\ по индукции находим, что En > 0. (b) По теореме 1.2.7А при х = 1/(М - l)Hn = iV - 1 находим Dn = ол+М- Xlt 0(M-1)-*D*,, гдео! =ОиО<алг < М(1-1/М)/1пМ < (М - If/M In М при iV > 2. Следовательно, О < Олг < (М - 1)Ллг/М In М < (М - l)(iV -1)/1пМ.

26. Приняв g = 5, г = -I во втором тождестве упр. 5.1.1-16, получим 1/3-1/(3-7) + 1/(3-7-15) -• • • = 0.28879; несколько удобнее использовать z = - и взять половину полученного результата. Можно также применить формулу Эйлера из упр. 5.1.1-14, включающую только отрицательные степени двойки. (Джон Ренч (John Wrench) вычислил это значение с точностью до 40 десятичных цифр: 0.28878 80950 86602 42127 88997 21929 23078 00889+.)

27. (Ради собственного удовольствия доведем точность решения до 0{N~).) В обозначениях из упр. 5.2.2-38 и 5.2.2-48 имеем

C=f/+jV-l + -aiV-/3 + (-l)"2-"("+"/-""

п;=,(1-2-)

а = 2/(1 • 1) - 4/(3 2,Л) + 8/(7 • 7 3 • 1) - 16/(15 • 15 • 7 • 3 • 1) -Ь • • •

а 1.60669 51524 15291 76378 33015 23190 92458 04806-,

а /3 = 2/(1 -за)- 4/(3 • 7 • 3 • 1) -Ь 8/(7 • 15 7 • 3 1)----а 0.60670. Эти численные оценки

приводят к выводу, что а = /3 -Ь 1, т. е. к факту, который нетрудно доказать. Значение

Х; (2-")"(l-2-") равно OCiV-") согласно упр. 5.2.2-46; & Vn+iI{N+1) = Un+i-Un.

m>0

Следовательно, Cn = Un+i - {a-l)N - a + 0{N-) = (iV+1) lg(iV4-1) + iV((7 - l)/ln 2+ I - Q + <J i(iV)) + I - l/ln4-a- <Ji(iV) + 0(iV-) согласно упр. 5.2.2-50.

Отклонение длины внутреннего пути дерева цифрового поиска было вычислено в работе Kirschenhofer, Prodinger, and Szpankowski, SICOMP 23 (1994), 598-616.

28. Выкладки в тексте и упр. 27 применимы для любого М > 2 - следует только подставить М вместо 2 в соответствующих, вполне очевидных местах. Следовательно, среднее количество проверок цифр при случайном успешном поиске составляет Cn /N = t/Ar+i-aM + l + 0(iV-i) = IogjvfiV+(7-l)/lnM + i-QM + <J-i(iV) + (logjvf iV)/iV + 0(iV-); при неудачном поиске оно равно Cn+i - Cn = Vn+2/{N + 2) - ам + 1 + 0(iV") = logjvf iV + 7/lnM + I - ам - So(N + 1) + O(iV-i). Здесь Ss{n) определена в упр. 19, a

ам = Y{-iyM+/{M+ - ifiM - 1)... (M - 1).

3>0

29. Флажоле (Flajolet) и Седгевик (Sedgewick) [SICOMP 15 (1986), 748-767] показали, что среднее количество таких узлов примерно равно 0.372iV при JVf = 2 и 0.689iV при М = 16. В работе Флажоле и Ричмонда [Random Structures and Algorithms 3 (1992), 305-320] приводится обобщение этого результата.

30. Итерируя рекуррентное соотнощение, получаем hn{z) в виде суммы всех возможных членов вида

31. hn(l) = Vn; см. упр. 5.2.2-36, (Ь). [Дополнительную информацию о дисперсии и предельных распределениях М-арных обобщений деревьев метода "Патриция" можно найти в работах Р. Kirschenhofer and Н. Prodinger, Lecture Notes in Сотр. Sci. 226 (1986), 177-185; W. Szpankowski, JACJW 37 (1990), 691-711; B. Rais, P. Jacquet, and W. Szpankowski, SMJW J. Discrete JVfath. 6 (1993), 197-213.]

32. Сумма полей SKIP равна количеству узлов в соответствующем бинарном дереве, поэтому ответом является величина An (см. упр. 20).

33. Вот как была получена формула (18). A{2z)-2A{z) = е-2е--1--Л(г)(е-1) может быть приведено к виду A(2z)/{e - 1) = (е - 1)/(е + 1) + А(г)/(е - 1). Следовательно, A{z) = (е - 1) E,>i(e/ - 1)/(е/ + 1). Теперь, если /(г) = Епг", то E,>i /(/2) = Есп2"/(2" - 1). В нащем случае /(г) = (е - 1)/(е + 1) = tanh(z/2), что эквивалентно 1 - 2z-\z/{e - 1) - 2г/(е" - 1)) = Е„>, B„+iz"(2"+ - 1)/(п + 1)!. Дальнейший вывод очевиден.

34. (а) Рассмотрим Ej>iElZlil)Bk/2-~>; согласно упр. 1.2.11.2-4 Г" + + {т-1)"-1 = {Вп{т)-Вп)/п. (Ь) Пусть Sn{m) = ET=ii~k/my и T„(m) = 1/(6"/" - 1). При fc < m/2 имеем g-*"/"" > exp(nln(l - к/т)) > exp(-fcn/m - кп/т") > e-*"/"(l - fcm). Значит, (1 - fc/m)" = g-*"/" -I- 0(e-*"/"fcn/m). Поскольку 5„(m) = ЕГ?(1 - fc/"*)" + 0(2-") и r„(m) = Erii e"*"/" + 0(e-"/), имеем S„(m) = T„(m)-bO(e-"/"n/m). Сумма членов 0{ещ>{-п/2)п/2) равна 0(n~), так как сумма при j < Ign имеет порядок п-(1 + 2/е + {2/ef а сумма при j > Ign - порядок п~(1 -Ь 1/4 -Ь (1/4)

(с) Доказательство аналогично доказательству, приведенному в разделе 5.2.2 при \х\ < 2п; затем используется аналитическое продолжение, (d) lg(n/7r) -Ь 7/(2 In 2) - -Ь S{n) + 2/п, где