d) Выведите среднее количество проб в случае неудачного поиска, рассматривая варианты структур данных, в которых используются следующие соглашения: (i) хеш-адрес указывает заголовок списка (см. рис. 38); (ii) хеш-адрес указывает позицию в таблице (см. рис. 40), но все ключи, кроме первого в списке, попадают в отдельную область переполнения; (iii) хеш-адрес указывает позицию в таблице, и все элементы находятся в хеш-таблице.

35. [М24] Продолжая упр. 34, найдите, чему равно среднее число проб при неудачном поиске, когда отдельные списки упорядочены по значениям ключей? Рассмотрите структуры данных (i), (ii) и (iii).

36. [М23] Продолжая упр. 34, (d), найдите дисперсию числа проб при неудачном поиске с использованием структур данных (i) и (ii).

► 37. [М29] Формула (19) дает среднее количество проб в случае успешного поиска по раздельным цепочкам. Чему равна дисперсия полученного числа проб?

38. [М32] {Хеширование с использованием деревьев.) Способный программист может попытаться использовать вместо линейных списков бинарные деревья поиска в методе цепочек, тем самым комбинируя алгоритм 6.2.2Т с хешированием. Проанализируйте среднее число проб, которые требуются для такого комбинированного алгоритма как в случае успешного, так и в случае неудачного поиска. [Указание. См. 5.2.1-(15).]

39. [М28] Пусть CA(fc) - общее количество списков длиной к, сформированных при помощи алгоритма С, который применен ко всем хеш-последовательностям (35). Найдите рекуррентное соотношение между числами cn{k), позволяющее определить простую формулу для суммы

Sn =£{2)cN{k).

Каким образом Sn связано с чистом проб при неудачном поиске по алгоритму С?

40. [МЗЗ] Формула (15) дает среднее количество проб, выполняемое алгоритмом С при неудачном поиске. Чему равна дисперсия этого числа проб?

41. [М40] Проанализируйте Tn, среднее количество уменьшения индекса Д на 1 при вставке (Л + 1)-го элемента по алгоритму С.

► 42. [М20] Выведите (17), вероятность гого, что первая проба алгоритма С оказалась успешной.

43. [НМ44 ] Проанализируйте модификацию алгоритма С, в которой используется таблица размером Af > М. Для хеширования используются только первые М позиций, так что первые М - М пустых узлов, найденных на шаге С5, будут находиться в дополнительных позициях таблицы. Какой в случае фиксированного значения М выбор 1 < М < М приведет к наивысшей производительности?

44. [М4З] {Случайные пробы с вторичной кластеризацией.) Цель данного упражнения состоит в определении ожидаемого количества проб в схеме с открытой адресацией с последовательностью проб

h{K), {h{K) + pi) mod М, {h{K) + Pi) mod М, {h{K) + рм-i) mod M,

где pi P2 -Pm-i - случайно выбранная перестановка множества {1,2,..., M-1}, зависящая от h{K). Другими словами, все ключи с одинаковыми значениями h{K) следуют одной и той же последовательности опробований и все {М - 1)! возможных выборов М последовательностей проб равновероятны.

Эта ситуация может быть точно смоделирована с помощью атедующей экспериментальной процедуры, выполняемой над первоначально пустым линейным массивом размером т. Выполните приведенные ниже операции п раз. "С вероятностью р займите

крайнюю слева пустую позицию. В противном случае (т. е. с вероятностью q = 1 - р) выберите любую позицию таблицы, за исключением крайней слева, причем все m - 1 позиций должны быть равновероятными. Если выбранная позиция пуста, займите ее; иначе выберите любую пустую позицию (включая крайнюю слева) и займите ее (все пустые позиции рассматриваются как равновероятные).

Например, при m = 5 и п = 3 конфигурационный массив (занято, занято, пусто, занято, пусто) после выполнения этой процедуры обрадуется с вероятностью

ткччч + \рчч +ът+ ыЧчр + Урч + \рчр + \чрр-

(Данная процедура соответствует случайному исследованию с вторичной кластеризацией при р = 1/m, поскольку можно перенумеровать элементы таблицы так, что некоторая последовательность проб будет равна О, 1, 2, ..., в то время как все остальные окажутся случайными.)

Найдите формулу для среднего количества занятых позиций на левом конце массива (в приведенном примере - 2). Найдите также асимптотическое значение этой величины при р = 1/m, п = а{т + 1) и m -> оо.

45. [М43] Выполните упр. 44, но с третичной кластеризацией, когда последовательность проб начинается с hi{K), {{hi{K) + h2{K)) modM, a дальнейшие пробы выбираются случайным образом в зависимости только от hi{K) и h2{K). (Таким образом, [М - 2)!(~i) возможных выборов М{М - 1) последовательностей проб с этим свойством рассматриваются как равновероятные.) Является ли эта процедура асимптотическим эквивалентом равномерного исследования?

46. [М42] Определите и Сд- для метода открытой адресации, использующего последовательность проб

ЦК), О, 1, h{K)-l, h{K) + l, М-1.

47. [М25] Найдите среднее количество проб, необходимых при открытой адресации для последовательности проб

h{K), h{K) - 1, h{K) + 1, h{K) - 2, h{K) -1-2, ....

Эта последовательность проб была однажды предложена в связи с тем, что все расстояния между последовательными пробами рмличны при четном М. [Указание. Небольшой трюк - и задача становится очень простой.]

► 48. [М21] Проанализируйте метод открытой адресации, позиции проб которого hi{K), h2{K), hi{K),... представляют собой бесконечную последовательность взаимно независимых случайных хеш-функций {hn{K)). В этом случае возможно опробование одной и той же позиции дважды, например, если h\{K) = h2(K), но такое совпадение крайне редко, пока таблица не станет близка к заполненной.

49. [НМ24] Определите среднее количество проб (обращений к внешней памяти) Сдг и С для цепочек с раздельными списками, предполагая, что список, содержащий к элементов, требует тах(1, к - Ь+1) проб при неудачном запуске. Вместо точной вероятности Рмк, как в упр. 34, воспользуйтесь приближением Пуассона

/iVX/lX*/. 1 XV- iViV-1 N-k + lr 1 1 \-* 1

V MVi V" iv iv- 1 N-k + ir M л M" )[m)[ m) ~m m " M V m) V m)

l + 0(fcVM)),

справедливым для Л = рМ и fc < \/М при М -> оо; выведите формулы (57) и (58).

50. [М20] Покажите, что Qi{M, N) = М - {М - N - l)Qo(M, Л) в обозначениях упр. 42. [Указание. Сначала докажите, что Qi{M,N) = {N + l)Qo{M,N) - NQo{M,N-l).]

51. [НМ17] Выразите функцию R{a, п), определенную в (55), через функцию Qo, определенную в (42).

52. [НМ20] Докажите, что Qo{M,N) = е-(1 + t/M)dt.

53. [НМ20] Докажите, что функция R(a, п) может быть выражена через неполные гамма-функции, и используйте результат упр. 1.2.11.3-9 для нахождения асимптотического значения R{a,n) с точностью 0{п~) при п -> оо для фиксированного а < 1.

54. [НМ28] Покажите, что при 6=1 формула (61) эквивалентна (23). Указание. Имеем

п\а т{т - 1){т - п - 1)Г

55. [ЕМ43\ Обобщите модель Шея-Спрута, обсуждавшуюся после теоремы Р, для М блоков размером Ь. Докажите, что C{z) равно Q{z)/{B{z) - г*"), где Q{z) - полином степени 6 и Q(l) = 0. Покажите, что среднее число проб составляет

, I 1 1Д"(1)-б(6-1)\

1 + -С(1) 1 + -( +---+1 д -2 В{1)-Ь )

где qi, ..., дь-1 - корни Q{z)/{z - 1). Заменив биномиальное распределение вероятностей B{z) приближением Пуассона Р(г) = е°""\ где а = N/Mb, и использовав формулу обращения Лагранжа (см. 2.3.4.4-(9) и упр. 4.7-8), приведите ответ к виду (61).

56. [НМ43] Обобщите теорему К, получив точный анализ линейного исследования при блоках рммером Ь. Чему равно асимптотическое число проб в случае успешного поиска при заполненной таблице (Л = Мб)?

57. Дает ли назначение одинаковых вероятностей последовательностям проб минимальное значение Cn среди всех методов открытой адресации?

58. [М21] (С. К. Джонсон (S. С. Johnson).) Найдите десять перестановок множества {0,1,2,3,4}, которые эквивалентны равномерному исследованию в смысле теоремы U.

59. [МЙ5] Докажите, что если назначение вероятностей перестановкам эквивалентно равномерному исследованию в смысле теоремы U, то при достаточно большом М число перестановок с ненулевыми вероятностями превосходит Л/" для любого фиксированного показателя степени а.

60. Будем говорить, что схема открытой адресации включает единственное хеширование, если в ней используется в точности М посчедовательностей проб, начинающихся со всех возможных значений h{K), каждое из которых встречается с вероятностью 1/М.

Является ли наилучшая схема единственного хеширования (в смысле минимума Cn) асимптотически лучше случайных схем, описанных в (29)? В частности, справедливо ли Сам > 1 + ia -Ь -Ь О(а) при М -> оо?

61. [М46] Является ли метод, анализировавшийся в упр. 46, наихудшей возможной схемой с единственным хешированием в смысле упр. 60?

62. [М49] Схема с единственным хешированием называется циклической, если увеличения Р1Р2 • • -Pm-i (в обозначениях упр. 44) фиксированы при всех К. (Примерами такого метода являются линейное исследование и последовательности, рассмотренные в упр. 20 и 47.) Оптимальной схемой с единственным хешированием является та, значение См которой минимально среди всех (М -1)! схем с единственным хешированием приданном М. При М <о наилучшая схема с единственным хешированием является циклической. Справедливо ли это для любого М?