rqk + Qk-i, 0 < r < Ofc, к нечетно и О < s < qk, имеет левую границу {(s + t)e} и правую границу {вв}~. Любое положительное целое число п может быть единственным образом представлено в виде п = rqk + qk-i + s при /г>1, 1<г<а)сиО<в<д*;. В этих обозначениях перед вставкой точки {пв} имеется п интервалов:

первые S интервалов (с номерами О, ..., s - 1) длиной {{ - lirgk + gk-i)9}; первые n-qk интервалов (с номерами О, ..., п- qk - 1) длиной последние qk-s интервалов (с номерами s, ..., qk - 1) длиной {(-l)°((r-l)gfc

Операция вставки {пв} приводит к удалению интервала номер s третьего типа и его преобразованию в интервал номер s первого типа и номер п - qk второго типа.

9. [МЗО] При последовательной вставке точек {в}, {2в}, ... в отрезок [О.. 1] теорема S утверждает, что каждая новая точка всегда разбивает один из наибольших имеющихся интервалов. Если интервал [а .. с] разбит таким образом на две части, [а .. 6] и [6.. с], назовем разбиение плохим, если одна из частей более чем в два раза больше другой, т. е. если b - а > 2{с - Ь) или с - 6 > 2(Ь - а).

Докажите, что при некотором п точка {пв} дает плохое рмбиение, за исключением случаев в mod 1 = и в mod 1 = ф~, при которых никогда не бывает плохих разбиений.

10. [МЗЗ] (Р. Л. Грэхем (R. L. Graham).) Докажите, что если e,ai,... ,ad - действительные числа, причем ai = О, если ni,...,nd - положительные целые числа и если точки {пв + aj} вставлены в интервал [0.1] при О < п < hj и 1 < j < d, то щ + + Hd получающихся интервалов (возможно, пустых) имеют не более 3d различных длин.

11. [16] Как правило, поиск чаще завершается успешно, чем неудачно. Исходя из этого, насколько разумно заменить строки 12-13 программы С строками 10-11?

► 12. [21] Покажите, что программа С может быть переписана так, что во внутреннем цикле останется только один условный переход. Сравните время работы модифицированной и исходной программ.

► 13. [24] {Сокращенные ключи.) Пусть h(K) представляет собой хеш-функцию, а д{К) - функцию от К, такую, что К можно определить по данным h(K) и д{К). Например, в случае хеширования путем деления можно положить h{K) - mod М, а q{K) - [KjM\; при мультипликативном же хешировании в качестве h{K) можно взять старшие биты (.AK/w) mod 1, а в качеств д{К) - остальные биты.

Покажите, что при использовании цепочек без списков перекрытий достаточно хранить значение q{K) вместо К для каждой записи. (Это позволяет сэкономить пространство, необходимое для полей ссылок.) Измените алгоритм С, чтобы он позволял работать с такими сокращенными ключами и можно было избежать использования списков перекрытий и вспомогательной памяти для хранения переполняющих записей.

14. [24] (Э. В. Элькок (Е. W. Elcock).) Покажите, что большая хеш-таблица может разделять память с другими связанными списками. Пусть каждое адово области списка имеет двухбитовое поле TAG и два ссылочных поля (LINK и AUX), имеющих следующий смысл.

TAG(P) - О указывает на слово в списке свободного пространства, LINK(P) укмывает на следующий элемент в списке, а AUX(P) не используется.

TAG(P) = 1 указывает на используемое слово, где Р не является хеш-адресом никакого ключа из хеш-таблицы; другие поля слова в позиции Р могут иметь любой формат.

TAG(P) = 2 указывает, что Р представляет собой хеш-адрес, по меньшей мере, одного ключа, AUX(P) указывает на связанный список, определяемый всеми такими ключами, а LINK(P) указывает на другое слово в памяти списка. При каждом обращении к слову с TAG(P) := 2 во время обработки любого списка

мы присваиваем Р LINK(P) несколько раз до достижения слова с TAG(P) < 1. (Для эффективности можно также изменить предшествующие ссылки так, что не нужно будет пропускать одни и те же элементы снова и снова.)

Определите подходящий алгоритм для вставки и получения ключей из такой хеш-таблицы.

15. [16] Почему в алгоритмах L и D стоит сообщать о переполнении при Л = М - 1, а не при N = Ml

16. [10] В программе L говорится, что К не должно быть нулем. А вдруг на самом деле она работает при К = Q1

17. [15] Почему бы просто не определить h2{K) = hi{K) в (25) при hi{K) ф О?

► 18. [21] Что лучше использовать для замены строк 10-13 программы D - (31) или (30)? Дайте ответ на основании средних значений А, S1 и С.

19. [40] Проверьте эмпирически воздействие ограничения области значений h2(K) в алгоритме D, так что: (а) 1 < h2{K) < г при г = 1, 2, 3,..., 10; (Ь) 1 < к2{К) < рМ при

1 2 9

Р 10 10 • • 10

20. [М25] (Р. Крутар (R. Krutar).) Измените алгоритм D следующим образом для удаления хеш-функции h2{K): на шаге D3 установите с <- О, а в начале шага D4 установите с с -Ь 1. Докажите, что, если М = 2"*, соответствующая последовательность проб hi{K), {hi{K)-l)modM, {hi{K)- ()) mod М будет перестановкой {0,1,M-1}. Если такой метод "квадратичных проб" запрограммировать для компьютера MIX, как будет выглядеть полученная программа по сравнению с программами, показанными на рис. 42, в предположении, что алгоритм ведет себя, как при случайном опробовании с вторичной кластеризацией?

► 21. [20] Предположим, что необходимо удалить запись из таблицы, построенной согласно алгоритму D, помечая ее как удаленную, как было предложено в тексте. Следует ли при этом уменьшать значение переменной Л, используемой для управления алгоритмом D?

22. [27] Докажите, что алгоритм R оставляет таблицу в таком виде, как будто KEY [г] никогда не был вставлен.

► 23. [33] Разработайте алгоритм, аналогичный алгоритму R, для удаления элементов из хеш-таблицы с цепочками, построенной по алгоритму С.

24. [М20] Предположим, что множество всех возможных ключей имеет MP элементов, из которых ровно Р имеют некоторый данный хеш-адрес. (На практике Р очень велико; например, если ключи представляют собой произвольные десятизначные числа и если М = 10, то Р = 10.) Положим М >7 и N = 7. Если из множества всех возможных ключей выбраны семь различных, то чему будет равна точная вероятность того, что будет получена хеш-последовательность 1 2 6 2 1 6 1 (т. е. h{Ki) = 1, h{K2) = 2, ..., ЦКт) = 1)? Выразите ответ в виде функции от М и Р.

25. [Mi9] Объясните, почему верна формула (39).

26. [М20] Чему равно количество хеш-последовательностей ai02...a9, дающих при использовании линейного исследования картину занятых ячеек, приведенную в (21)?

27. [М27] Завершите доказательство теоремы К. (Указание. Пусть

s{n,x,y) = Y{l){x + к)+\у - кГ--{у - п);

для доказательства того, что s{n,x,y) = х{х + у)" + ns{n-l, х+1, у-1), используйте биномиальную теорему Абеля (1.2.6-(16)).)

28. [M5fl] "В те времена укромные, теперь почти былинные*", когда компьютеры были очень медлительными, по скорости мигания лампочек на панели можно было увидеть, насколько быстро работает алгоритм L. Когда таблица заполнялась почти до конца, можно было заметить, что одни данные обрабатывались очень быстро, а другие - очень медленно.

Эти наблюдения наталкивают на мысль о большом значении стандартного отклонения количества проб в случае неудачного поиска при использовании линейного исследования. Найдите формулу, выражаюш;ую дисперсию через функции Qr из теоремы К, и оцените ее значение при Л = аМ и М оо.

29. [M2i] (Задача о парковке.) Предположим, существует некоторая улица с односторонним движением, имеющая пг мест для парковки, пронумерованных от 1 до т. В автомобиле рядом с водителем дремлет его жена, которая вдруг просыпается и требует немедленно остановиться. Муж послушно выполняет требование жены и останавливается на первом свободном месте для парковки. Однако, если "нет нигде стоянки, Брайтон весь забит", т. е. впереди нет ни одного свободного места (жена проснулась в тот момент, когда автомобиль проезжал к-е место парковки, а все места к, к + 1, ..., т были заняты), законопослушность водителя перевешивает послушность жене и он, принеся свои извинения, едет дальше.

Предположим, что на одной улице окмалось п автомобилей с дремлющими женами, причем j-я жена (имеется в виду, конечно же, жена j-ro водителя. - Прим. перев.) просыпается напротив oj-ro места парковки. Сколько последовательностей ai... позволят всем автомобилям успешно припарковаться, если предположить, что первоначально улица была пуста и что ни один из припарковавшихся автомобилей не уехал. Например, при ш = п = 9иа1...09 = 314159265 автомобили будут припаркованы следующим образом.

<;:1Ъ <::1Ъ

[Указание. Воспользуйтесь анализом линейного исследования.]

30. [МЗЗ] Покажите, что в задаче о парковке из упр. 29 при п = т все машины припарковываются тогда и только тогда, когда существует перестановка pip2---Pn множества {1,2,..., п), такая, что aj < Pj для всех j.

31. [М40] При п = m в упр. 29 количество решений равно {п + 1)"", а из упр. 2.3.4.4-22 известно, что это - число свободных деревьев на п -Ь 1 помеченной вершине! Найдите интересную связь между последовательностью парковок и деревьями.

32. [М27] Докажите, что система уравнений (44) имеет единственное решение, (со, ci,..., CM-i), при любых целых неотрицательных Ьо, bi,..., бм-ь сумма которых меньше М. Разработайте алгоритм для поиска этого решения.

► 33. [М23] Объясните, почему (51) представляет собой только оценку истинного среднего количества проб, выполняемых алгоритмом L. Что именно при выводе (51) привело к тому, что формула не абсолютно точна?

► 34. [М23] Назначение этого упражнения заключается в исследовании среднего количества проб в хеш-таблице с цепочками, когда списки остаются раздельными, как на рис. 38.

a) Чему равна Pjvfc, вероятность того, что данный список имеет длину к, если все хеш-последовательности (35) равновероятны?

b) Найдите производящую функцию Pn{z) = Sfc>o-fjvfc2*.

c) Выразите среднее количество проб для успешного поиска через эту производящую функцию.

* Цитаты из произведений В. Высоцкого и В. Токарева, присутствующие в переводе данного и следующего упражнений, в оригинальном издании, конечно же, отсутствуют. - Прим. перев.