Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 37
Текст из файла (страница 37)
[66) Разработайте эффективиый алгоритм, который может применяться для построения дерева, используемого методом "Патриция", или для вставки новой ссылки на ТЕХТ в существующее дерево. Ваш алгоритм вставки должен обращатыя к массиву ТЕХТ не более двух раз.
16. [66) Почему в алгоритме "'Патрипия" требуется, чтобы один ключ не стужил началом другого? 1Т. [М35) Как выразить решение рекурреитпого соотношения хе = х1 = О, х„=а„+ги' ) ~™1(ги — 1)" ьхы и > 2, 1Й/ с помощью биномиальных преобразований, обобщая метод упр. 5.2.2-36? 16. [МЕХ] Используя результат упр. 1?, выразите решения уравнений (4) и (5) через функции У„и Р„аналогичные определенным в упр. 5.2,2-38.
19. [ЖУЕМ[ Найдите асимптотическое значение функции с точностью О(1) прк и -+ оо для фиксированных значеиий э > 0 и гп > 1. [Случай для е = 0 рассматривался в упр. 5.2.2-50, а случай для з = 1, ит = 2 — в упр, 5.2.2-43.[ ° 20. [М80) Рассмотрим М-ариую "лучевую" память, в которой используется последовательный поиск по достижении пыдерева яз з или меньшего колкчества лучей (алгоритм Т представляет собой частный случай цри в = 1).
Примените результаты предыдуших упражнений для анализа а) среднего количества узлов луча; Ь) среднего количества проверок цифр или символов при успешном гюиске; с) среднего количества сравнений, выполняемых при успешном поиске. Сформулируйте ответы на вопросы в виде есимптотических формул при Ф -ь оо для фиксироваипых М и е; ответ для (а) дцтжеи быть даи с точностью до О(1), а для (Ь) и (с) — до О(й?"'), [При М = 2 втот аиализ примеивм н модифицироваииому матоду обменной порез» ридной сортировки, в котором подфайлы размером < е сортяруютси посредством вставок.) 21.
[МЕЕ[ Сколько узлов случайиого М-ариого луча с Ф ключами имеют в качестве нулевой компоненты пустую ссылку? (Например, 9 из 12 узлов в табл, 1 имеют пустую ссылку в ~ох~пик "о'! "Случайиостьи в даииом упрежиеиии, как обычио, озиачает, что цифры ключей равиомерио распределены мажлу 0 и М вЂ” 1,) 22.
[МЕЕ) Сколько узлов находится в случайном М-арном луче с К ключами на уровне ( ((ж 0,1,2,...)? 26. [МЕ6) Скозько проверок цифр выполняется в среднем в процессе иеуспешиого поиска в М-аркам луче, содержащем?т' случайных ключей? 24. [М30) Рассмотрите М-ариый луч.
представленный в виде леса (см. рис. 31). Найдите точные и асимптотические выражении для а) среднего количества узлов в лесу; Ь) среднего количества присвоений»Р +- 55152(Р)» в процессе случайного успешного поиска. ь 25. [МЗХ) Математический вывод асимптотических значений в этом разделе весьма сложен (использовалась даже теория функций комплексного переменного). Дело в том, что мы не хотели ограничиться одним членом асимптотической формулы, а вывод второго члена действительно сложен. Назначение данного упражнения — показать, что элементарных методов достаточно для вывода некоторых (пусть и ослабленных) результатов.
а) Докажите по индукции, что решение (4) удовлетворяет неравенству Ал < 5Х(М— Ц/(ЛХ вЂ” Ц. Ь) Пусть Вн = Сл — Х!ХНн-!,!)п,М, где Сл определяется формулой (5). Докажите, что Вл — — 0(М)., следовательно, Сл = Ж1обм Ж+ 0(К). [Указание. ИспользУйте (а) и теорему 1.2.?А ) 26. [23) Определите значение бесконечного произведения с точностью до пяти значащих цифр непосредственным вычислением. [Указание.
См, упр. 5.1.1-1б.) 27. [ХХМЯХ) Чему с точностью до 0(Ц равно асямнтотическое значение Сн из (14)? 25. [НМ26) Найдите асимптотическое среднее количество проверок цифр прп выполнении в случайном ЛХ-арион дереве цифрового поиска при М > 2. Рассмотрите случай как успешного, так и неудачного поиска; дайте ответ с точностью до О(!!Х ').
29. [ХХМХР! Чему равно асимптотическое среднее количество узлов в ЛХ-арион дереве пифрового поиска, все ссылки которых пусты? (Можно было бы сэкономить память, исключая такие узлы; см. упр. 13.) ЗО. [М24) Покажите, что производящая функция алгоритма»Патриция" 5 (з), определенная в (15), может быть выражена в совершенно увшсном виде: и — 1 1 ),а!,...,а / (2"! — Ц(2"!+»! — Ц..,(2'!+ '+" — Ц >! а!+. +» = ~ — ! »!,,а >! (Таким образом, если бы имелась простая формула для Ь»( ), можно было бы упростить это громоздкое выражение.) З1. [МЗХ) Решяте рекуррентное соотношение (1б).
З2. [ЗХЗХ) Чему равно среднее значение суммы всех полей ЗКХР в случайном дереве алгоритма "Патриция" с Х!' — 1 внутренним узлом? ЗЗ. [МЗО) Докажите, что (15) представляет собой решение рекуррептного соотношения (17). [Указание. РассмотРите пРоизводЯщУю фУнкцию А(з) = 2 „>е а» е»/и!.) ЗЛ. [ХХМХО) Назначение данного упражнения — поиск асимптотического поведения формулы (18). а) Докажите, что при и > 2 и <-» 15/2"-' — 1 2Х!»-П и г<йь<» !>! Ь) Покажите, что слагаемые в правой части (а) приближенно равны 1/(е* — Ц -1/к+ 1?2, где х м и/2!; получающаяся при этом сумма отличается от первоначальной ив О(п ').
с) Покажите, что 1 1 1 1 à — - — + — ж —, / ~(е) Г(е) х бл для действительного х > О. 21/ ~,.„ б) Следовательио, рассматриваемая сумма равна 2к1/ г„, 2 ' — 1 Оцените этот иптеграл. ь 36, [М80] Какова вероятность того, что дерево алгоритма "Патриция" с питью ключами имеет вид причем в полях 3КУР содержатся а, Ь, с, 6, как показано па рисуикеу (Считаем, что ключи имеют независимые случайные биты; ответ должен иметь вид функции от а, Ь, с и Ы.) 36, [МЙБ) Имеется пять бинарных деревьев с тремя внутренними узлами в каждом.
Если рассмотреть, как часто каждое из них служит деревом поиска в различных алгоритмах при случайных данных, то получатся следующие различные вероятности. 1 6 1 8 1 7 (Заметим, что дерево цифрового поиска будет сбалансировано чаще других.) В упр. 6.2.2-5 приведена формула для вероятиосги в случае поиска по дереву: [ [ [1/е(к)), где произведение берется по всем внутренним узлам х, а е(к) — число внутреиних узлов в поддереве, корнем которого является х.
Найдите аналогичные фориулы для вероятиосги в случае (а) алгоритма 1) и (Ь) алгоритма Р. ь 37. [М82) Рассмотрите бинарное дерево, иа уровне( которого имеется Ь| внешних узлов. В тексте указывалось, что время неудачного покска в деревьях цифрового поиска ке связана с длиной виешиего пути 2, 1Ь| непосредствеиио, а пропорционально модифицированной длике еиешиего пути 2 !Ь|2 . Докажите или опровергните следующее утверждение: среди всех деревьев с Р7 виешиими узлами наименьшую модифицированную длину внешнего пути имеет то дерево, все внешние узлы которого расположены ие более чем яа двух смежиых уровпях (см. упр.
5.3.1-20). Поиск по дереву 1 (алгоритм 6.2.2Т) 6 Цифровой поиск по дереву 1 (алгоритм П) 8 Метод "Патриция" 1 (алгоритм Р) 7 1 6 1 8 1 7 1 3 1 2 3 7 1 6 1 8 1 7 33. [МЬВ] Разработайте алгоритм поиска дерева с и узлами, имеющего минимальное значение величины и (длина внутреннего ггути)+)у (модифицированная длина внешнего пути), где и и  — некоторые числа (см, упр. 37). 39. [Ьгеу] Разработайте алгоритм поиска оптимальных деревьев цифрового поиска, аналогичных оптимальным бинарным деревьям поиска, которые рассматривались в разделе 6.2.2. ь 40. [23] Пусть оеагаз.
— зто периодическая бинарная последовательность, в которой олэь — — оь для всех Ь > О. Покажите, что любая фиксированная последовательность такого типа может быть представлена в 0(Х) ячейках памяти так, что следующая операция могкет быть выполнена за 0(Н) шагов. Определите для данной цепочки битов Ье Ьг... Ь„ сколько раз она встречается в периоде (т, е. найдите, сколько существует таких значений р, при которых О < р < гу и Ьь = арье для О < Ь < и). Предполагается, что каждан ячейка памяти достаточно велика, чтобы содержать любое целое число от О до Н. [Указание.
См. упр. 141 41. [НЫ38] (Приложение к теории групп.) Пусть С вЂ” свободная группа над символами (а„..., а„), т. е. множество всех строк гэ = Ьг... Ь„где каждый Ь, представляет собой либо а;, либо а и не имеется смежных пар а о,. или а„а, Обратным к а элементом является Ь, ... Ь, . Перемножим две такие строки путем их конкатенации и сокращения смежных обратных пар. Пусть Н вЂ” - подгруппа группы С, порожденная строками (,9г,...,Д ), т.
е. множество всех элементов С, которые могут быть зшгисаны в виде произведений В и обратных им элементов. Согласно широкоизвестной теореме Якоба Нильсена (уайоЬ Х!е!зев) [см. МашЬа!! На11, ТЬе ТЬеогу ог" Сгоирз (Меж г'огйз Маспп!1ав. 1959), СЬ. 7] всегда можно найти образующие Вг,, В для Н, пг < р, обладающие тем свойством, что средний символ В, (или, по крайней мере, один из центральных символов В„если ето длина четна) никогда не сокращается в выражениях В,В," или В;В,, е = ж1. за исключением случая у = ! и е = — 1. Из этого свойства следует, что существует простой алгоритм проверки принадлежности некоторого элемента С подгруппе Н: запишем 2пг ключей В,,...,В В,,...,В в дерево, ориентированное на поиск по символам, с помощью 2п букв а,,...,а„, а,,...,о„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
