AOP_Tom3 (1021738), страница 160
Текст из файла (страница 160)
(МЯЗ) Пусть ск(й) — общее количество списков длиной?г, сформированных при помощи алгоритма С, который применен ко всем Мм хеш-последовательностям (35) . Найдите рекуррентное соотношение между числами сгг(1г), позволяющее определить простую формулу для суммы Яп = ~( )см(Й). Каким обраэолг Як связано с числом проб при неудачном поиске по алгоритму С? 40. (МЯЯ) Формула (15) дает среднее количество проб, выполняемое алгоритмом С при неудачном поиске.
Чему равна дисперсия этого числа нроб? 41. (М40] Проанализируйте Тк, среднее количество уменьшения индекса Н на 1 при вставке (ЛХ+ 1)-го элемента по алгоритму С. ь 42. (МЯЯ) Выводите (17), вероятность того, что первая проба алгоритма С оказалась успешной. 43. ~НМ44) Проанализируйте модификацию алгоритма С, в которой используется таблица размером ЛХ' > ЛХ Для хеширования используются только первые М позиций, так что первые М' — ЛХ пустых узлов., найденных на гнаге С5, будут находиться в дополнительных поэипиях таблицы.
Какой в случае фиксированного зиачегшя ЛХ' выбор 1 < М < ЛХ' приведет к наивысшей производительностит 44. [м4Я) (слу гайьме аробъг с ешоричнай кяастариааспгеа.) Цель данного уира>ниенна состоит в определении ожидаемого количества проб в схеме с открытой адресацией с погтедовательностью проб й(К), (й(К) чрг) шос1 М, (Л(К) +рг) гпог1 М, ..., (Ь(К) + рм — г) шос1 М, где рг рг... рм г — случайно выбранная перестановка множества (1, 2,, М вЂ” 1), зависящая от й(К). Другими словами, все клгочи с одинаковыми значениями й(К) следуют одной и той же последовательности опробований и все (М вЂ” 1)ьм возможных выборов М послодовательностей проб равновероятны.
Эта ситуация может бьгп точно смоделирована с помощью следующей экспериментальной цропедуры, выполняемой над первоначально пустым линейным массивом размером т. Выполните приведенные ниже операции и раз. 'С вероятностьнэ р займите крайнюю слева пустую позицию. В противном случае (т. е. с вероятностью Ч = 1 — Р) выберите любую позицию таблицы, за исключением крайней слева, причем все т — 1 позиций должны быть равновероятными. Ешги выбранная позиция пуста, займите ее; иначе выберите любую пустую позицию (включая крайнюю слева) и займите ее (все пустые позиции рассматриваются как равновероятные)" Например, при т = 5 и и = 3 конфигурационный массив (занято, занято, пусто, запито, ггусго) после выполнения этой процедуры образуется с вероятностью гзгЧЧЧ+ зРЧЧ Ь еЧРЧ+ ыЧЧР+ зРРЧ+ зРЧР зЧРР (Данная процедура соответствует случайному исследованию с вторичной кластеризацией при Р =- 1/т, поскольку можно перенумеровать элементы таблицы так, что некоторая пошгедоватачьность щгоб будет равна О, 1, 2, ..., в то время как все остальные окажутся случайными.) Найдите формулу для среднего количества занятых позиций иа левом конце массива (в приведенном примере — 2).
Найдите также асимптотическое значение этой величииьг прир —. Цт, п=п(т41) и та со. 45. (М43] Выполните упр. 44, но с третичной кластеризацией, когда последовательность проб начинается с йг(К), ((Нг(К) + Иг(К)) гпог1 ЛН а дальнейшие пробы выбираются случайным образом в зависимости только от йг(К) и Иг(К). (Таким образом, (М вЂ” 2)г ц~ возможных выборов Л1(Ы вЂ” 1) последовательностей проб с этим свойством расслгатрнваются как равновероятные.) Является лн зта процедура асимптотическим эквивалентом равномерного нсследованияг 46.
(Мза( ОпРеделите Са н Сн дла метода откРытой адРесации, использУющего последовательность проб 6(К), О, 1, ..., 6(К) — 1, 6(Н) + 1, ..., М вЂ” 1. 47. (М25( Найдите среднее количество проб, необходимых при открытой адресации для последовательности проб 5(К), 5(К) — 1, Н(К) + 1, 5(К) - 2, Л(К) + 2, . Эта пос гедовательность проб была однажды предложена в связи с тем, что все расстояния между гюследовательнымн пробамн различны при четном М. [Указание. Небольшой трюк — н задача становится очень простой.) ь 48. (М21] Проанализируйте метод открытой адресации, позиции проб которого Ьг(К), Иг(К), 1гз(К), - .. представляют собой бесконечную последовательность взаимно независимых случайных хеш-4гункцийг (Н (И )).
В этом случае возможно опробование одной н той же позиции дважды, например, если /м(К) = )гг(И), но такое совпадение крайне редко, пока таблица не станет близка к заполненной. 49. (НЛ124) Определите среднее количество проб (обрапгений к внешней памяти) Сн и Сл для цепочек с раздельными списками, предполагая, что список, содержащий гг злементон, требует шах(1, й — Ь+ 1) проб при неудачном запуске. Вместо точной вероятности Рть, как в упр. 34, воспользуйтесь приблггженисм Пуассона справедливым для Ж = РЛ1 и й < ьгМ при М -г оо, выведите формулы (57) и (58). 50. [М20] Покажите, что О1(ЛХ, ЛХ) = М вЂ” (М вЂ” ЛХ вЂ” 1)Оо(М, Н) в обозначениях упр. 42.
[Указание. Сначала докажите, что О1(ЛХ, Н) = (Л + 1) 1хо (ЛХ. ЛХ) — Ж1зе (М, Н вЂ” 1).] 51. [НМХ7] Выразите функцию Н(п, и), определенную в (56), через функцию Оо, определенную в (42). 52. [НМ20] Докажите, что ('„1р(М,ЛХ) = [' е '(1+1/ЛХ)ай. 53. [НМ20] Докажите, что функция Н(й, и) может быть выражена через неполные гамма- функции, и используйте результат упр 1.2 11.3 — 9 для нахождения асимптотического значения Н(о, и) с точностью 0(и ) при и — э сс для фиксированного а < 1. 54. [НЛХ22] Покажите, что при Ь = 1 формула (61) эквивалентна (23).
Указание. Имеем 1.(о) = Е ( — 1)" 1 > ( — гиг) и! о а т(т — 1) (т — и — 1)! > 55. [НМ49) Обобщите модель Шея-Спрута, обсуждавшуюся после теоремы Р, для ЛХ блоков размером Ь. Докажите, что С(з) раино О(з)/(В( ) — з~), где О(з) —. полинам степени Ь и О(1) = О. Покажите, что среднее число проб составляот ЛХ,, 1/ 1 1 1В"(1) — Ь(Ь-1)1 где дм ..., дз 1 — корни фз)/(з — 1).
Заменив биномиальное распределение вероятностей В(з) приближением Пуассона Р(з) = е~ *, где о = ЛХ/ЛХЬ, и использовав формулу з ( — и обращения Лагранжа (см. 2.3 44-(9) н упр. 4.7<8), приведите ответ к виду (61) 56. [НМ49] Обобщите теорему К, получив точный анализ линейного исследования при блоках размером Ь Чему равно асимптотическое число проб в случае успешного поиска при заполненной таблице (Н = МЬ)? 57. [М47] Дает ли назначение одинаковых вероятностей последовательностям проб минимальное значение Ся среди всех методов открытой адресации? 58. [М21] (С. К.
Джонсон (Б. С. Лобпэон).) Найдите десять перестановок множества (О, 1, 2, 3, 4), которые эквивалентны равномерному исследованию в смысле теоремы С 59. [М29] Докажите, что если назначение вероятностей перестановкам эквивалентно равномерному исследованию в смыг ~е теоремы 11, то при достаточно большом М число перестановок с ненулевыми вероятностями превосходит М' для любого фиксированного показателя степени а. 60. [М47] Будем говорить, что схема открытой алресапни включает единственное хеширование, если в ней используется в точности М последовательностей проб, начинающихся со всех возможных значений И(К), каждое из которых встречается с вероятностью 1/М.
Якляетгя ли наилучшая схема единственного хеширования (я гмыгле минимума Си) асимптотически лучше случайных схем, описанных в [29)? В частности, справедливо ли С м > 1 + з а + з а + 0(о ) при ЛХ э сс? 61. [М40] Является ли метод, анализировавшийся в упр. 46, наихудшей возможной схемой с единственным хешированием в смысле упр. 60? 62.
[М49] Схема с единственным хешированием называется циклическая, если увеличения 21 рз .. рм-) (в обозначениях упр 44) фиксированы при всех К. (Примерами такого метода являются линейное исследование и последовательности, рассмотренные в упр. 20 и 47.) Оигиимальиой схемой с единственным хешированием является та, значение См которой минимально среди всех (М-1)!' схеме единственным хешированием приданном ЛХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
