c) Покажите, что

/-5+°°

d) Следовательно, рассматриваемая сумма равна

i H--az)riz)n- 1

mj.ii 2--1

2ni y i ioo Оцените этот интеграл. ► 35. Какова вероятность того, что дерево алгоритма "Патриция" с пятью ключами

имеет вид

причем в полях SKIP содержатся а, 6, с, d, как показано на рисунке? (Считаем, что ключи имеют независимые случайные биты; ответ должен иметь вид функции от а, 6, с и d.)

36. [М25] Имеется пять бинарных деревьев с тремя внутренними узлами в каждом. Если рассмотреть, как часто каждое из них служит деревом поиска в различных алгоритмах при случайных данных, то получатся следующие различные вероятности.

Поиск по дереву (алгоритм 6.2.2Т)

Цифровой поиск по дереву (алгоритм D) Метод "Патриция" (алгоритм Р)

(Заметим, что дерево цифрового поиска будет сбалансировано чаще других.) В упр. 6.2.2-5 приведена формула для вероятности в случае поиска по дереву: f(l/s(a;)), где произведение берется по все.м внутренним узлам х, а s{x) - число внутренних узлов в поддереве, корнем которого является х. Найдите аналогичные формулы для вероятности в случае (а) алгоритма D и (Ь) алгоритма Р. ► 37. [М22] Рассмотрите бинарное дерево, на уровне / которого имеется 6; внешних узлов. В тексте указывалось, что время неудачного поиска в деревьях цифрового поиска не связано с длиной внешнего пути Ibt непосредственно, а пропорционально модифицированной длине внешнего пути Yllbi2~. Докажите или опровергните следующее утверждение: среди всех деревьев с N внешними узлами наименьшую модифицированную длину внешнего пути имеет то дерево, все внешние узлы которого расположены не более чем на двух смежных уровнях (см. упр. 5.3.1-20).

-г--- т: - I С(г)Г(г):» dz для действительного X > 0.

-1 X 2 2niJ i i

38. [М40] Разработайте алгоритм поиска дерева с п узлами, имеющего минимальное значение величины а - (длина внутреннего пути)(модифицированная длина внешнего пути), где а и /3 - некоторые числа (см. упр. 37).

39. [М4З] Разработайте алгоритм поиска оптимальных деревьев цифрового поиска, аналогичных оптимальным бинарным деревьям поиска, которые рассматривались в разделе 6.2.2.

► 40. [25] Пусть ао ai аг ... - это периодическая бинарная последовательность, в которой a/v+fc = ак для всех А; > 0. Покажите, что любая фиксированная последовательность такого типа может быть представлена в 0{N) ячейках памяти так, что следующая операция может быть выполнена за 0{N) шагов. Определите для данной цепочки битов Ьо bi • • • bn-i, сколько раз она встречается в периоде (т. е. найдите, сколько существует таких значений р, при которых 0<р<МиЬк= Ор+А: ДЛЯ О < к < п). Предполагается, что каждая ячейка памяти достаточно велика, чтобы содержать любое целое число от О до N. [Указание. См. упр. 14.]

41. [НМ28] (Приложение к теории групп.) Пусть G - свободная группа над символами {ai,..., йп}, т. е. множество всех строк а = bi.. .br, где каждый bi представляет собой либо Oj, либо а~ и не имеется смежных пар aaj или a~aj. Обратным к а элементом является br .. bi. Перемножим две такие строки путем их конкатенации и сокращения смежных обратных пар. Пусть Н - подгруппа группы G, порожденная строками ... ,р}, т. е. множество всех элементов G, которые могут быть записаны в виде произведений /3 и обратных им элементов. Согласно широкоизвестной теореме Якоба Нильсена (Jakob Nielsen) [см. Marshall Hall, The Tiieory of Groups (New York: Macmillan, 1959), Ch. 7] всегда можно найти обрадующие вг,... ,вт для Н, т < р, обладающие тем свойством, что средний символ Oi (или, по крайней мере, один из центральных символов Oi, если его длина четна) никогда не сокращается в выражениях или е = ±1, за исключением случая

j = г и е = - 1. Из этого свойства следует, что существует простой алгоритм проверки принадлежности некоторого элемента G подгруппе Н: запишем 2т ключей вг,...,вт, вг ,.. ,вт в дерево, ориентированное на поиск по символам, с помощью 2п букв аг,... ,а„, аг ,. ,а~. Пусть а = Ь\.. .br - данный элемент из G; если г = О, то а, разумеется, принадлежит Н. В противном случае ищем а, определяя самый длинный префикс Ьг.. .Ьк, который соответствует ключу. Если имеется несколько ключей, начинающихся с bi... 6*,, то а не принадлежит Н. Иначе обозначим этот единственный ключ через Ьг.. .ЬкСг.. .ci = б и заменим а ключом в~а = cf . - Сг 6+1... . Если новое значение а длиннее старого (т. е. если / > А;), а не принадлежит Н\ в противном случае повторяем процесс с новым значением а. Из свойства Нильсена вытекает конечность этого алгоритма. Если а сводится к пустой строке, можно восстановить исходное представление а в виде произведений в. Например, пусть {в\,62,63} = {bbb, b~a~b~, ba~b} и а = bbabaab. Лес

вместе с описанным алгоритмом позволяет вывести, что а = вгвз в\вз 82 Реализуйте этот алгоритм, используя в качестве входных данных вашей программы di.

42. [23] {Сжатие спереди и сзади.) Если множество бинарных ключей используется в качестве индекса для разделения большого файла, можно не хранить полные ключи. Например, 16 ключей, показанных на рис. 34, могут быть урезаны справа так, чтобы

оставалось достаточное количество цифр для их однозначной идентификации: 0000, 0001, 00100, 00101, 010, 1110001. Такие урезанные ключи могут использоваться для разделения файла на 17 частей, и, например, в пятой части могут содержаться все ключи, начинающиеся с ООП или 010, а в последней части - ключи, начинающиеся с 111001, 11101 или 1111. Урезанные ключи можно представить в более компактной форме, если опустить все лидирующие цифры, совпадающие с цифрами предыдущего ключа: 0000, oool, oolOO, ooool, olO, ooooool. Бит, следующий за символом "о" всегда равен 1, поэтому он также может быть опущен. В большом файле будет содержаться много символов "о" и мы должны хранить только их количество и значения последующих битов.

Покажите, что общее количество битов в сжатом файле с исключенными символами "о" и последующим одним битом, всегда равно количеству узлов в бинарном луче с этими ключами.

(Следовательно, среднее общее количество таких битов во всем индексе составляет около N/\n2, 1.44 бит на ключ. Этот способ сжатия был показан автору Э. Геллером (А. Heller) и Р. Л. Джонсеном (R. L. Johnsen). Возможно и дальнейшее сжатие, поскольку нам необходимо только представление структуры луча; см. теорему 2.3.1А.)

43. [НМ42] Проанализируйте высоту случайного М-арного луча, имеющего N ключей и параметр обрезки s, как в упр. 20 (когда s = 1, эта величина представляет собой длину самого длинного общего префикса случайных слов длиной N в М-арном алфавите).

► 44. [30] (Дж. Л. Бентли (J. L. Bentley) и Р. Седгевик (R. Sedgewick).) Исследуйте тернарное представление лучей, при котором левая и правая ссылки соответствуют горизонтальным ветвям (2), в то время как средняя ссылка соответствует ветви, идущей вниз.

► 45. [М25] Если семь ключей, которые показаны на рис. 33, вставлены в случайном порядке с по.мощью алгоритма, описанного в упр. 15, то чему равна вероятность получения показанного дерева?