Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 49
Текст из файла (страница 49)
29 количество решений равио (и+ 1)" ', а из упр. 2.3.4,4 — 22 известно, что это — число свободных деревьев иа и + 1 помеченной вершине! Найдите интересную связь между последоватючьиостью парковок и деревьями. 32. [М37] Докйжите, что система уравнений (44) имеет единственное решение, (се, см см-~), при любых целых иеотрицательных Ье, Ь»,...,Ь»г и сумма которых меньше ЛХ. Разработайте алгоритм для поиска етого решения. ь 33.
[Мйу] Объясните, почему (51) представляет собой только оценку истинного среднего количества проб, выполняемых алгоритмом Е. Что именно при выводе (51) привело к тому, что формула ие абсолютно точна? ь 34. [Мйу] Назначение етого упрюкиеиия заключается в исследоваиии среднего количе- ства проб в хеш-заблице с цепочками, когда списки остаются раздельными, как иа рис. 33. а) Чему равна Рт», вероятность того, что данный список имеет длину Ь, если все М' к хеш-последовательиости (35) равновероятиы? Ь) Найдите производящую функцию Р (в) = 2»>е Рл»з».
с) Выразите среднее количество проб для успешиога поиска через зту производящую функцию. " Пк»аты кз произведений В. Высоцкого в В. Токарева. врвсугстеующве в переводе данного в следующего увражненвй. в орвгввальном вздавив, коиечво же, отсутствуют. — Проис верее. б) Выведите среднее количество проб в случае иеудачиога поиска, рассматривая варианты структур данных, в которых используются следующие соглашения: (1) хеш-адрес указывает заголовок списка (см. рис. 38); (й) хеш-адрес указывает позицию в таблице (см. рис. 40), но все ключи, кроме первого в списке, попадают в отдельную область переполнения; (1а) хеш-адрес указывает позицию в таблице, и все элементы находятся в хеш-звблице, 35.
[М34] Продптжая упр. 34. найдите, чему равно среднее число проб при неудачном по- иске, когда отдельные списки упорядочены по значениям ключей? Рассмотрите структуры данных (1), (й) и (ш). 36. [МлУ] Продолжая упр. 34, (г)), найдите дисперсию числа проб при неудачном поиске с использованием структур данных (!) и (й), г 37. [М39] Формул» (19) дает среднее количество проб в случае успешного поиска по раздельным цепочкам. Чему равна дисперсия полученного числа проб? 38.
[МУЗ] (Хеширование с использованием дерееьее.) Способный программист может попытаться использовать вместо линейных списков бинарные деревья поиска в методе цепочек, тем самым комбинируя алгоритм 6.2.2Т с хешированием. Проанализируйте сред- нее число проб, которые требуюет:я для зикого комбинированного алгоритма как в случае успешнога, так и в случае неудачного поиска. [Указание.
См. 5.2.1-(15).] Зй. [МЗЗ] Пусть си(?г) — общее количества списков длиной Л, сформированных при помощи алгоритма С, который применен ко всем Мя хеш-последовательностям (35). Най- дите рекуррентнае соотншпение между числами си(?г), позволяющее определить простую формулу для суммы Як =~ ~ )сн(й). Каким образом Ян связано с чиглом проб при неудачном поиске по алгоритму С? 40. [МЯУ] Формула (15) дает среднее количество проб, выполняемое алгоритмом С при неудачном поиске. Чему равна дисперсия етого числа проб? 41. [М40) Проанализируйте Тн, среднее количество уменьшения индекса Н на 1 Ори вставке (?т' + 1)-го злементэ по алгоритму С. ° 43.
[М30] Выведите (17), вероятность гого, что первая проба алгоритма С оказалась успешной. 43. [НМ44) Проанализируйте модификацию алгоритма С, в которой используется таблица размером ЛХ" > М. Для хеширования используются только первые М позиций, так что первые М' — М пустых узлов, найденных на шаге С5, будут находиться в дополнительных позициях таблицы. Какой в случае фиксированного значения М' выбор 1 ( М < ЛХ' приведет к наивысшей производительности? 44. [м43] (сзрчаенме пробы с егааричной ялесшгризацигй.) Цель данного упражнения состоит в определении ожидаемого количества проб в схеме с открытой адресацией с последовательностью проб А(К), (Ь(К) +рг) шобЛХ, (Л(К) + рз) гпоб М,, (6(К)+ рм г) шос1 ЛХ, где рг рз...рм д — случайно выбранная перестановка множества (1, 2, ..., М вЂ” 1), зевисяшая от 6(К).
Другими словами, все ключи с одинаковымн значениями 6(К) следуют одной и той же последовательности опробований и все (М вЂ” 1)! возможных выборов М последовательностей проб равновероятны. Эта ситуация может быть точно смоделирована с помощью следуюагей зкспериментальпой процедуры, выполняемой нзд первоначально пустым линейным массивом размером ж.
Выполните приведенные ниже операции и раз, "С вероятностью р займите крайнюю слева пустую позицию, В противном случае (т, е, с вероятностью д = 1 — р) выберите любую позицию таблицы, за исключением крайней слева, причем все»п — 1 позиций должны быть равновероятными. Если выбранная позиция пуста, займите ее; иначе вь»берите любую пустую позицию (включая крайнюю слева) и займите ее (все пустые позиции рассматриваются как равновероятные)1 Например, при т = 5 и и =- 3 конфигурационный массив (занято, занято, пусто, занято, пусто) после выполнеш»я этой процедуры образуется с вероятностью »92»»»»»»+ БРч»»+ б»»Р»» + е»чт 311 т 1Р»»Р йчРР (Данная процедура соответствует случайному исследованию с вторичной кластеризацией при р = 1/»и, поскольку можно перенумеровать элементы таблицы так, что некоторая последовательность проб будет равна О, 1, 2,, в то время как все остальные окажутся случайными.) Найдите формулу для среднего количества занятых позиций на левом конце массива (в приведе»п»оь» примере — 2).
Найдите также асимптотическое значение этой величины прн р = 1/т, и = о(ш + 1) и ш -» оо. 45. (МЛЮ) Выполните упр. 44, но с»претихой квастперизоциец, когда последовательность проб начинается с Ь»(К), ((Ь»(К) + Ьз(К)) шо») ЛХ, а дальнейшие пробы выбираются случайным образом в зависимости только от Ь»(К) и Ьз(К).
(Таким образом, (М вЂ” 2)»~»~ возможных выборов М(М вЂ” 1) последовательностей проб с этны свойством рассматриваются как равновероятные.) Являетсв ли эта процедура асимптотическим эквивш»витом равномерного исследования? 46. (М42) Определите С~ и Сл для метода открытой алресацин, использующего последовательность проб ЦК), О, 1, ..., Ь(К) — 1, Ь(К) +1, ..., М вЂ” 1. 4Т. (М25) Найдите среднее количество проб, необходимых при открытой адресации ддя последовательности проб Ь(К), Ь(К) — 1, Ь(К) + 1, Ь(К) — 2, Ь(К) + 2, Эта последовательность проб была однажды предложена в связи с тем, что все расстояния между последавательнымн пробами различны при четном М. (Указание. Небольшой трюк — к задача становится очень простой.) ь 43.
(МЯ1) Пров»»алнзируйте метод открытой адресации, позиции проб которого Ь»(К), Ьз(К), Ьз(К),... представляют собой бесконечную последовательность взаимно ни»ависимых случайных хеп»-функций (Ь (К)). В этом случае возможно опробование одной и той же позиции дваждь», например, если Ь»(К) = Ьз(К)., но такое совпадение крайне редко, пока таблица не станет бланка к зшюлненной. 49. (НМЯ4) Определите среднее количество проб (обращений к внешней памяти) Сн н Сн для цепочек с раздельными списками, предполагая, что список, содержащий Ь элементов, требует шах(1, Ь вЂ” 5+ 1) проб при неудачном запуске. Вместо точной вероятности Ряы как в упр, 34, воспользуйтесь приблоз»сен»»ем Пуассона = —,~ (1 + 0(Ь /М)), справедливым для Л» = рЛХ и Ь (»/М цри Лй -» со; выведите формулы (57) и (58). 50.
[М20] Покажите, что Щ(ЛХ, Н) = М вЂ” (М вЂ” Ж вЂ” ЦЯе(ЛХ,Лэ) в обозначениях упр. 42. ээ Указание. Сначала докажите, что Цэ(М, Л) = (Л1 + Ц(эЭо(ЛХ Лэ) — Лэнде(М„К-Ц.] 51. [НМ17] Выразите функцию ХЬ(а, и), определенную в (55), через функцию (Хе, определенную в (42). 52. [НМ20] Докажите, что 1',Эе(ЛХ,Ю) = [ е '(1 ч-11'ЛХ)нэй. 53. [НЛХЮ0] Докажите, что функция Н(а, и) может быть выражена через непа;иые гамма- функции, и используйте результат упр. 1.2.11.3 — 9 для нахождения асимптотнческого значения Н(о, н) с точностью О(п э) при и -э со для фиксированного о < 1. 54. [НМ20] Покажите, что при Ь = 1 формула (бЦ зквнвалентна (23).
Указание. Имеем ( — ц" ' тэ ( — па) Ьв(о) = З эээ о г гл(эп — ц(эп — и — ц! 55. [НМ4У] Обобщите модель Шея-Спрута, обсуждавшуюся после теоремы Р, для АХ блоков размером Ь. Докажите, что С(в) равно ь((з)/(В(в) — г~), где Я(з) —. полипом степени Ь и эК(ц = О. Покажите, что среднее число проб составляет М 1 / 1 1 1+ — С'(Ц =1+ — [ + + Л' Ь (.1-йэ 1 — Оь-э 1В" (Ц вЂ” Ь(Ь- Ц) 2 В(Ц вЂ” Ь где оэ, ..., дэ э -- корни 1„э(х)/(з — Ц, заменив биномиальное распределение вероятностей В(з) приближением Пуассона Р(т) = с~'~' 'Э, где ээ = НХЛХЬ, и использовав формулу обраэцения Лагранжа (см.
2.3.4.4 — (9) и упр. 4.7-8), пршэедите ответ к виду (бЦ, 56. [НМ40] Обобщите теорему К„получив точный анализ линейного исследования при блоках размером Ь. Чему равно асимптотическое число проб в случае успешного поиска при заполненной таблице (ЛХ = ЛХЬ)? 57.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
