52. См. формулу 1.2.11.3-(9) и упр. 3.1-14.

53. Согласно 1.2.11.3-(8) получаем а{ап)"Ща,п) = е""7(п+1, an); следовательно, в соответствии с указанным упражнением R(a, п) = (1 - а)~ - (1 - а)~п~ + 0{п~). [Эта асимптотическая формула может быть получена непосредственно, с использованием метода (43), если заметить, что коэффициент при а в R{a, п) равен

В действительности согласно 1.2.9-(28) коэффициент при а* равен

B-.)--{-:r}j

54. Используя указание, а также формулы 1.2.б-(53) и 1.2.б-(49), получим

h (rn + l){rn)rnl\k)

Указание следует из хорошо известного гипергеометрического тождества Куммера

e-F{a;b;z) = F{b-a;b; -z),

поскольку (пЧ-1)!(„(а) = e"""(an)"F(2;п-I-2; an); см. СгеЛе 15 (1836), 39-83, 127-172, формула 26,4.

55. Если B{z)C(z) = J2 имеем со = so -I-----hSb, ci = Sb+i, сг = Sb+2, ; следовательно, B{z)C{z) = z>C{z) + Q{z). P(z) = z>> имеет b - 1 корень qj, где \qjl < 1, определяемые как решения уравнения е°~ = oj~qj, ш = e Для решения е"" = ш~д положим t = aq и Z - auje", так что t = ге. Согласно формуле Лагранжа получим

1-<?~ / (п-г)!

г>1 т>0 п>

По теореме Абеля о возможности перехода к пределу для степенного ряда, устремляя w -> 1 так, что ш находится внутри единичного круга, формулу можно привести к виду

т>2 п>0

Теперь, заменяя ш на и суммируя по 1 < j < 6, получаем 6-

т>2 \ п>1 /

откуда после небольших манипуляций с использованием указания к упр. 54 получается требуемый результат.

Начало этому анализу, применяемому при решении задач различных типов, было положено в работах N. Т. J. Bailey, J. Roy. Stat. Soc. B16 (1954), 80-87; M. Tainiter, JACJVf 10 (1963), 307-315; A. G. Konheim and B. Meister, JACJVf 19 (1972), 92-108.

56. См. Blake and Konheim, JACM 24 (1977), 591-606. Альфредо Виола (Alfredo Viola) и Патрицио Поблете (Patricio Poblete) [Aigorithraica 21 (1998), 37-71] показали, что

-iEC7)"-e(i:,)<-)""-"-

2Mb . .

j>2 • fc>l

= Vir + 36 + 6g(l- r(e-i/b-.)) + YaSWM где T - функция дерева из 2.3.4.4-(30).

58. 01234и02413 плюс аддитивные сдвиги 11111 mod 5, каждый с вероятностью j. Аналогично при М = б требуется 30 перестановок, и решение существует, начинаясь с

х 012345, х 013254, gLx 024315, х 023451, 5x 034125.

При М = 7 требуется 49 перестановок, и решение порождается из

х 0123456, Y§5 X 0153246, х 024351б, §5 X 0263145, х03б1425, Y55 X 0326415, 5 X 0315426.

59. Ни одна перестановка не может иметь большую вероятность, чем 1/(д2]) поэтому должно быть не менее {/2 ~ ехр(М1п2 4- O(logM)) перестановок с ненулевыми вероятностями.

60. Предварительные результаты получены в работе Ajtai, Komlos, and Szemeredi, Information Processing Letters 7 (1978), 270-273.

62. Cm. дискуссию в AMJVf 81 (1974), 323-343, где представлены наилучшие циклические последовательности хеширования для М <9.

63. МНм согласно упр. 3.3.2-8; стандартное отклонение составляет и жМ/\/б.

64. Среднее количество перемещений составляет {N-l)/M-\-l{N - l){N-2)/M-\-j{N -

1)(N - 2){N - 3)/М Ч----и - Ь 13- [Аналогичная задача решена в Сотр. J. 17

(1974), 139-140.]

65. Ключи могут храниться в отдельной таблице с последовательной организацией (предположим, что все удаления, если они производятся, соответствуют стековому представлению LIFO (last-in-first-out, "последним вставляется - первым удаляется"). Элементами хеш-таблицы являются указатели на эту "таблицу имен"; например, TABLE [г] может иметь вид

LiKEY[i],

где Li -- количество слов в ключе, хранящемся в позициях KEY [г] , KEY [г] -Ь 1,....

Остаток элементов хеш-таблицы может использоваться несколькими способами: (i) как ссылка для алгоритма С; (ii) как часть информации, связанной с ключом; (iii) как "вторичный хеш-код" Последняя идея, предложенная Робертом Моррисом (Robert Morris), иногда позволяет ускорить поиск (мы рассматриваем ключ KEY [г] только в том случае, когда значение некоторой функции hiiK) соответствует вторичному хеш-коду).

66. Да; при этом расположить записи можно лишь одним способом. Среднее количество проб при неудачном поиске снижается до Cjv-i, хотя и остается равным Сд- при вставке А-го элемента. Эта важная технология именуется упорядоченным хешированием. См. Сотр. J. 17 (1974), 135-142; D. Е. Knuth, Literate Programming (1992), 144-149, 216-217.

67. (а) Если в (44) Cj = О, оптимального расположения можно достичь, рассортировав а согласно невозрастающему "циклическому порядку", которым предполагается, что j - 1 > • • • > О > М - 1 > • • • > j. (b) Между шагами L2 и L3 поменяйте вставляемую запись и

TABLE[i], если последняя ближе к начальному положению, чем предыдущая. [Этот алгоритм, названный хешированием Робин Гуда (Robin Hood hashing) в работе Celis, Larson, and Munro, FOCS 26 (1985), 281-288, представляет собой вариант упорядоченного хеширования.] (с) Обозначим через /г(т, п, d) количество хеш-последовательностей, которые приводят к Со < d. Можно показать [Сотр. J. 17 (1974), 141], что {h{m,n,d) - h{m,n,d - 1))М - общее количество перемещений d > О по всем хеш-последовательностям и что можно записать h{M,N,d) = a{M,N,d + 1) - Na{M,N - l,d + 1), где a{m,n,d) = Efc=o {1){m + d - k)"~{k - d). Сложные вычисления с использованием методов из упр. 28 и 50 показывают, что среднее значение J2 d] равно

М- е diKM, N, d) - h{M, N,d- 1))

---f-S;-a--«(f-M)«".-)

при N = аМ. Если алгоритм не модифицирован (см. упр. 28), EJ2dj преобразуется в

y(02(M,iV) - Qi{M,N)) - (Qo(M,iV) - 1) + f

/ 1 1 1 1 a\

\3(1-а)з 3(1-a)2 2(l-a) 2 б

+ 0(1).

Если все записи имеют приблизительно одинаковое перемещение d и если успешный поиск осуществляется значительно чаще, чем неудачный, то выгодно начинать с позиции h = h{K) + d, & затем опробовать позиции /г - 1, /г Ч- 1, /г - 2 и т. д. П. В, Поблете (Р. V. Poblete), А. Виола (А. Viola) и Д. Я. Мунро (J. I. Munro) показали [Random Structures and Aigorithms 10 (1997), 221-255], что Yj может быть сделана столь же малой, как и в методе Робин Гуда, при помощи более простого подхода, называемого хешированием "последним пришел - первым обслужен" (last-come-first-served), при котором каждый вновь вставляемый ключ помещается в свою начальную позицию; все другие ключи перемещаются на один шаг, пока не будет найдено пустое место. Оба эти подхода применимы как к двойному хешированию, так и к линейному исследованию, но уменьшение количества проб не компенсирует увеличения времени, требуемого для одной пробы с учетом двойного хеширования, пока таблица не заполнится почти до отказа (см. Poblete and Munro, J. Algorithms 10 (1989), 228-248).

68. Среднее значение (di -I-----1- dw) равно

((M - Nf + (N + 3)(M - N) + {8N + 1)(M -N) + 5N + 4N-1

- {{M - Nf + 4(M - Nf + (6N + 3)(M -N)+ 8iV)Qo(M, N-l)),

как можно показать, рассмотрев связь между задачей о парковке и связанными графами, о которой упоминалось в упр. 31. Для получения дисперсии среднего количества проб в случае успешного поиска разделим эту величину на N и вычтем \{Qo{M,N - 1) - 1); асимптотически это равно j((l + 2а)/(1 - а) - l)/N + 0{N~). (См. Р. Flajolet, Р. V. Poblete, and А. Viola, Algorithmica. 22 (1998), 490-515; D. E. Knuth, Aigorithmica 22 (1998), 561-568. Вычисленная дисперсия должна отличаться от общей дисперсии, которая равна EX;d/iV - \ {Qo(M,N - 1) - l); см. ответы к упр. 37 и 67.)