= 2) Yk>i (C(l + 27rifc/ln 2) exp(27rifc lg(n/7r)))/ cosh(7rfc/ln 2).

Дисперсия и высшие моменты были вычислены В. Шпанковским (W. Szpankowski), JACM S7 (1990), 691-711.

35. Ключи должны иметь вид {а0/30а)1,а0/31а)2,01700)3,Ql7l<J0a)4,Ql7l<Jla)5}, где а,/3,... есть строки из нулей и единиц; \а\ = о - 1, /3 = 6 - 1ит. д. Вероятность того, что пять случайных ключей имеют такой вид, равна 5\2--+-+-+-/2+++++++++++ = 512*°++++

36. Пусть п - число внутренних узлов, (а) {n\/2)Yl{l/s(x)) = n! n(l/2*"s(a;)), где / - длина внутреннего пути дерева. (Ь) {(п + 1)!/2") П(1/(2 - 1)). (Рассмотрите суммирование ответа к упр. 35 по всем о, 6, с, d > 1.)

37. Наименьшая модифицированная длина внешнего пути равна 2 - 1/2 и достигается только в случае вырожденного дерева (длина внешнего пути которого максимальна). (Можно доказать, что наибольшая модифицированная длина внешнего пути достигается тогда и только тогда, когда все внешние узлы расположены не более чем на двух смежных уровнях! Однако дерево с меньшей длиной внешнего пути не всегда имеет большую модифицированную длину внешнего пути.)

38. Рассмотрите подзадачу поиска деревьев с fc узлами с параметрами (q,/3), {а, 13),..., (а, 2*-"/?).

39. См. Miyakawa, Yuba, Sugito, and Hoshi, SICOMP 6 (1977), 201-234.

40. Пусть N/r - истинная длина периода последовательности. Построим дерево, подобное дереву метода "Патриция", с aooi... в качестве массива TEXT и с N/r ключами, начинающимися с позиций 0,1,..., N/r - 1. (В соответствии с выбором г ни один ключ не является началом другого.) Включим в каждый узел поле SIZE, в котором содержится количество помеченных полей ссылок в поддереве, лежащем ниже этого узла. Для выполнения указанной операции используйте алгоритм Р. Если поиск неудачен, ответ - 0; в случае успешного поиска и j < п ответ - г. И наконец, если поиск успешен и j > п, ответ равен г SIZE(P).

43. Ожидаемая высота асимптотически приближается к (1 -Ь l/s)log N с отклонением 0(1). [См. Н. Mendelson, IEEE Transactions SE-8 (1982), 611-619; P. Flajolet, Acta/nformat-ica 20 (1983), 345-369; L. Devroye, Acta /nformatica 21 (1984), 229-237; B. Pittel, Advances in Applied Probability 18 (1986), 139-155; W. Szpankowski, Algoritiimica 6 (1991), 256-277.]

Средняя высота случайного дерева цифрового поиска с JVf = 2 асимптотически приближается к Ig п -Ь v21gn [Aldous and Shields, Probability Theory and Related Fields 79 (1988), 509-542]; то же самое справедливо и для случайного дерева метода "Патриция" [Pittel and Rubin, Journal of Combinatorial Theory A55 (1990), 292-312].

44. Cm. SODA 8 (1997), 360-369; такая структура поиска тесно связана с алгоритмом быстрого многоключевого поиска, обсуждавшимся в ответе к упр. 5.2.2-30. Ж. Клемент (J. Clement), Ф. Флажоле (Р. Flajolet) и Б. Вали (В. Vallee) показали, что при тернарном представлении поиск по лучу выполняется примерно в три раза быстрее, чем при использовании бинарного представления (2), с учетом доступа к узлам [см. SODA 9 (1998), 531-539].

45. Вероятность {THAT, THE, THIS} перед {BUILT, HOUSE, IS, JACK}, {HOUSE, IS, JACK} перед {BUILT}, {HOUSE,IS} перед {JACK}, {IS} перед {HOUSE}, {THIS} перед {THAT,THE} и {THE} перед {THAT} равна

РАЗДЕЛ 6.4

1. -37 < rll < 46. Таким образом, в ячейках памяти, предшествующих TABLE и следующих за TABLE, не должны содержаться данные, которые соответствуют аргументу

(например, их первый байт мог бы быть нулевым). Очевидно, что было бы плохо хранить К в таком диапазоне! (Значит, можно сказать, что метод из упр. 6.3-4 использует меньшее пространство, поскольку границы той таблицы никогда не нарушаются.)

2. TOW (буксир). (В состоянии ли читатель найти десять слов из не более чем пяти букв, которые заполнят пустоты между -10 и 30?)

3. Коды символов удовлетворяют соотношениям A + T = I + N, B-E = 0-R, а потому получим либо /(AT) = /(IN), либо /(BE) = /(OR). Обратите внимание на то, как команды 4 и 5 из табл. 1 разрешают эту дилемму, оставляя гП в достаточно узком диапазоне.

4. Рассмотрим случай для к пар. Наименьшее п, такое, что

"--е(„!,)("Г)-<5 =

равно 88. Если вы пригласите 88 человек (включая себя), вероятность появления трио с одним днем рождения составит 0.511065; для 87 человек эта вероятность снижается до 0.499455. См. С. F. Pinzka, АММ 67 (I960), 830.

5. Эта хеш-функция плоха, поскольку она принимает не более 26 различных значений, причем некоторые из них будут встречаться явно чаще других. Даже при двойном хешировании (если предположить, например, что /12 (ЛГ) = 1 -(- второй байт К и М = 101) низкая скорость поиска превысит выигрыш от высокой скорости вычисления хеш-функции. Кроме того, поскольку в программах на языке FORTRAN часто встречается куда больше, чем 100 различных переменных, значение М = 100 явно мало.

6. Не на MIX-компьютере, поскольку почти всегда будет получаться арифметическое переполнение (слишком велико делимое). (Было бы неплохо иметь возможность вычислить (wK) mod М, в особенности для линейного исследования при с = 1, но, к сожалению, большинство компьютеров не предоставляют ее из-за переполнения частного.)

7. Если R{x) кратен Р(х), то Д(сг) = О в GF(2=) для всех j 6 S. Пусть R{x) = х" + •••-(- ж", где 01 > • • • > Oj > О и S < t. Выберем t - s значений Os+i,..., 0(, таких, что ai,..., 0( представляют собой различные неотрицательные числа, меньшие п. Матрица Вандермонда

.<ч

Q" ... a"

Va"" ... а""/

сингулярна, поскольку сумма ее первых s столбцов равна нулю. Однако это противоречит тому факту, что a,... ,0" - различные элементы GF(2°) (см. упр. 1.2.3-37).

(Первоначально идея полиномиального хеширования была предложена группой исследователей из IBM (М. Напап, S. Muroga, F. Р. Palermo, N. Raver, and G. Schay, IBM J. Research к Development 7 (1963), 121-129; см. также U. S. Patent 3311888 (1967)).)

8. По индукции. Сильная индуктивная гипотеза может быть дополнена тем фактом, что {(-l)=(rgfc + qk-i)e} = (-l)=(r(gfc6l - pk) + {qk-iO - Pk-i)) при 0 < г < оь "Рекордно низкие" значения {пв} достигаются для п = qi, qi + qi, 2q2 + qi, ..., 0292 + qi = Oq + qs, 94-1-93, . • , 0494 -(- 93 = O96 -(- 95, ..., "рекордно высокие" - для n = 90, 9i + 9o, . • •, 0191 -(- 90 = O93 -(-92, .... Это шаги, на которых формируется интервал с номером О новой длины. (Дальнейшая структура может быть выведена обобщением системы счисления Фибоначчи из упр. 1.2.8-34; см. L. Н. Ramshaw, J. Number Theory 13 (1981), 138-175.)

9. Имеем ф = 1,1,1,... и ф = 2,1,1,... . Пусть в = 01,02,... , вк = ofc+i, Ofc+2, и пусть Qk = 9fc +qk-i0k-2 в обозначениях из упр. 8. Если oi > 2, плохим является самое первое разбиение. Три размера интервалов в упр. 8 равны (1 - rek-i)/Qk,

Ok-ilQk и (l - (г - l)9ic-i)/Qk соответственно, так что отношение первых двух длин составляет (о - г) + 9k. Эта величина меньше i при г = и Ofc+i > 2; следовательно, чтобы не было плохих разбиений {о2,аз,...} должны быть равны 1. (Другие связанные с данной темой теоремы можно найти в работе R. L. Graham and J. Н. van Lint, Canadian J. Math. 20 (1968), 1020-1024, и в указанной в ней литературе.)

10. Вы найдете элегантное доказательство в работе F. М. Liang, Discrete Math. 28 (1979), 325-326.

11. Проблемы могут начаться при А" = 0. Если потребовать, чтобы все ключи были ненулевыми, как в программе L, такое изменение может иметь смысл; при этом можно было бы помечать пустые позиции нулевым значением.

12. Можно хранить К в КЕУ[0], заменив при этом строки 14-19 следующими строками.

STA TABLE (KEY) Л - 51 СМРА TABLE, 2 (KEY) С - 1 - 52

СМРА TABLE.2(KEY) Л - 51 JNE 2В С - 1 - 52

JE 3F Л-51 ЗН J2Z 5F Л - 51

2Н ENT1 0.2 С-1-52 ENT1 0,2 52

LD2 TABLE, 1 (LINK) С - 1 - 52 JMP SUCCESS 52

"Сохраненное" время составляет С-1-5А+5 + 451 единиц, что в результате оборачивается потерей, поскольку С очень редко превышает 5. (Оказывается, не всегда следует оптимизировать внутренние циклы!)

13. Пусть записи в таблице относятся к двум различным типам, как и в алгоритме С, с дополнительным однобитовым полем TAG [г] в каждой записи. В приведенном решении используются циклические списки, следуя предложению Аллена Ньювелла (Allen Newell), с установленным TAG [г] = 1 в первом слове каждого списка.

А1. [Инициализшгия.] Установить t •(- j •(- h(K) + 1, Q •(- q{K).

A2. [Это список?] Если TABLE [г] пуст, установить TAG [г] •(- 1 и перейти к шагу А8. В противном случае, если TAG [г] = О, перейти к шагу А7.

A3. [Сравнение.] Если Q = KEY [г], алгоритм успешно завершается.

А4. [Переход к следующему.] Если LINK [г] ф j, установить г •(- LINK [г] и вернуться к шагу A3.

А5. [Поиск пустого узла.] Уменьшить R один или несколько раз до тех пор, пока не будет найдено значение, такое, что TABLE [R] пуст. Если Д = О, алгоритм завершается после переполнения; в противном случае установить LINK [г] <- R.

А6. [Подготовка к вставке.] Установить i <- R, ТАС[Д] •(- О и перейти к шагу А8.

А7. [Перемещение записи.] Установить i •(- LINK [г] один или несколько раз, пока не

будет выполнено условие LINK [г] = j. Затем выполнить шаг А5 и установить

TABLED] <-TABLEШ, i j, TAGCj] <- 1.

A8. [Вставка нового ключа.] Пометить TABLE [г] как занятый узел с KEY[t] <- Q, LINK И I

(Заметьте, что, если TABLE [г] занят, можно определить соответствующий полный ключ К по данному значению г. Имеем q{K) = KEY[t] , а затем, несколько раз присвоив г <- LINK[i] до тех пор, пока не выполнится равенство TAG[i] == 1, получим h{K) = 1-1.)

14. Согласно указанным соглашениям запись "X AVAIL" из 2.2.3-(6) теперь означает следующее. "Установить X •(- AVAIL, присвоить X •(- LINK(X) нуль или несколько раз до X = Л (ошибка переполнения) или до TAG(X) = О и наконец установить AVAIL <- LINK(X)."

Для вставки нового ключа К: установить Q AVAIL, TAG(Q) <- 1 и сохранить К в этом слове. (Можно также, если все ключи коротки, опустить этот шаг и заменить