AOP_Tom3 (1021738), страница 139
Текст из файла (страница 139)
с) "Случайные данные" в нашем случае означают, что М-ичные цифры равномерно распределены, как если бы ключи были действительными числами между 0 и 1, записанными в М-ичной системе счисления. Методы цифрового поиска не зависят от порядка, в котором ключи введены в файл (за исключением алгоритма П, который слабо чувствителен к порядку); однако они весьма чувствительны к распределению цифр. Например, если нулевые биты встречаются гораздо чаще единичных, деревья будут существенно более асимметричными по сравнению с деревьями, полученными для случайных данных (в упр.
5.2.2-53 приведен пример тога, что может случиться при таком смещении данных). элементы. как показано ниже. Позиция Элемент Позиция Элемент (Узлы (1), (2),..., (12) в табл. 1 начинаются соответственно в позициях 20, 19, 3, 14, 1, 17, 1, 7, 3, 20, 18, 4 этой сжатой таблицы.) Покажите, что, если сжатой таблицей заменить табл. 1, программа Т останется работоспособной, хотя и пе столь быстрой. 5. [Мбб] (Я. Н Патт (У. Н. Раж).) В деревьях иа рис.
31 содержатся буквы каждого семейства, упорядоченные ло алфавиту. Такое упорядочение не является необходимым, и, если переупорядочить узлы внутри каждого семейства перед построением дерева типа (2), поиск может ускориться. Какое переупорядочеиие представленного иа рис. 31 дерева приведет к оптямкчьиому с этой точки зрения результату? (Используйте частоты, приведенные на рис. 32, и найдите "лес"] который позволит минимизировать время успешного поиска, когда он представлен в виде бинарного дерева.) 6. [15] Какое дерево цифрового поиска получится при вставке 15 четырехбитовых бинарных ключей 0001, 0010, 0011,..., 1111 в порядке возрастания согласно алгоритму О? (Начните с ключа 0001 в корневом узле и выполните 14 вставок), ° 7.
[?ийб] Если 15 ключей из упр, б вставлены в другом порядке, может быть построено другое дерево. Какая перестановка этих ключей из всех 15! возл<ожных будет паохудшеб в том смысле, что опа породит дерево с наибольшей длиной виутреипего пути? 8. [80] Рассмотрим следующие изменения в алгоритме О, ведущие к исключению из него перемениой К': заменим "К'" на "К" &а шаге 02 и удалим операцию "К' +- К" иа шаге 131.
Будет ли полученный в результате этих действий алгоритм корректным, и можно ли с его помощью выполнять поиск и вставку? й. [81] Напишите 811-програмь<у для алгоритма 13 и сравните ее с программой б.2.2Т. Можете испольэовать бинарные операции, такие как 855 (бинарный сдвиг АХ влево), УЬЕ (переход при четном А) и дрб возможно, вам поможет упр.
8, 10. [83] Даи файл, все ключи которого представляют собой и-битовые двоичные числа, и дап аргумент поиска К = Ь< Ь<... Ь . Предположим, что необходимо найти максимальное значение /г, при котором в файле будет с<держаться ключ, начииающийся с Ь< Ьэ... Ьь. Как эффективно решить поставленную задачу, если файл представлен в виде а) бииариого дерева поиска (влгоритм б.2.2Т); Ь) бииариого луча (алгоритм Т); с) бинарного дерева цифрового поиска (алгоритм 11)? 11. [81] Можно ли использовать неизмененный алгоритм б.2,211 для удаления узла из дерева цифрового поиска? 12. [85] Вудет ли случайным дерево, .полученное путем удаления случайного элемента из случайиого дерева цифрового поиска, которое построено с помощью алгоритма В? (См.
упр. 11 и теорему б.2.2Н.) 13. [20] (М-орнмй цифровой поиск.) Объясните, как можно объединить алгоритмы Т и О в один обобщенный алгоритм, при М = 2 представляющий собой алгоритм О. Какие изменения следует внести в табл. 1 для использования алгоритма прн ЛТ = 30? ь 14. (Еб] Напишите эффективный алгоритм, который может быть выполнен сразу после успешного окончания алгоритма Р для нахождения всех мест, я которых ТЕХТ содержит К. 15. [30] Разработайте эффективный алгоритм, который может применяться для построения дерева, используемого методом "Патриция", или для вставки новой ссылки на ТЕХТ в существующее дерево.
Ваш алгоритм вставки должен обращаться к массиву ТЕХТ не более двух раз. 16. [ЕЕ] Почему в алгоритме "Патриция" требуется, чтобы адин ключ не служил началом другого? 1?. [Мйб] Как выразить решение рскуррентного соотношения хе=х1=0, х„=о +нл' "~ ( ](гл — 1)" хл, п>2, (к) с помощью биномиэльных преобразований, обобщая метод упр, 5.2.2-3бо 18.
[МЕТ] Используя результат упр. 17, выразите решения уравнений (4) и (5) через функции б'„и 1'„, аналогичные определенным в упр. 5.2.2 — 38. 19. [НМЕУ] Найдите асимптотическое значение функции К(н, в, пл) = ~ ( ) ( ) с точностью 0(1) при и -л ао для фиксированных значений в > О и пл > 1. [Случай для в = О рассматривался в упр, 5.2.2-50, а случай для в = 1, т = 2 — в упр.
5,2.2 — 48.) ь 20. [МЯ0] Рассмотрим М-арную "лучевую" память, в которой используется последовательный поиск по достижении поддерева из в илн меньшего количества лучей (алгоритм Т представляет собой частный случай при в = 1). Примените результаты предыдуших упражнений для анализа а) среднего количества узлов луча; Ь) среднего количества проверок цифр или сиыволов при успешном поиске; с) среднего количества сравнений, выполняемых при успешном поиске. Сформулируйте ответы на вопросы в виде всимптотичесних формул прн Лг -+ оо для фиксированных ЛТ и в; ответ для (а) должен быть дан с точностью до 0(1), а для (Ь) н (с) — до 0(Лг ').
[При М = 2 этот анализ применим к модифицированному методу обменной поразрядной сортировки, в котором подфайлы размером < в сортируются посредством вставок.) 21. [Мйб) Сколько узлов случайного М-арного луча * Н ключами имеют в качестве нулевой компоненты пустую ссылку? (Например, 9 иэ 12 узлов в табл. 1 имеют пустую ссылку в позиции "о". "Случайность" в данном упражнении, как обычно, означает, что цифры ключей равномерно распределены между 0 и М вЂ” 1.) 22. [МЕ5] Сколько узлов находится в случайном М-арном луче с гл' ключами на уровне ( () = О, 1,2,,)? 23.
[МЕ6] Сколько проверок цифр выполнкется в среднем в процессе неуспешного поиска в М-арном луче, содержащем Тл' случайных ключей? 24. (МЯ0] Рассмотрите М-арный луч, представленный в виде леса (см, рис. 31). Найдите точные и аснмптотическне выражения для а) среднего количества узлов в лесу; Ь) среднего количества присвоений "Р +- 8513К(Р)" в процессе случайного успешного поиска. ь 25.
[МЯЗ] Математический вывод асимптотнческих значений в этом разделе весьма сложен (использовалась даже теория функций комплексного переменного) Дело в том, что мы не хотели ограничиться одним членом асимптотической формулы, а вывод второго члена действительно сложен. Назначение данного упражнения — показать, что элементарных методов достаточно для вывода некоторых (пусть и ослабленных) результатов. а) Докажите по индукции, что решение (4) удовлетворяет неравенству Ая < М(Ж— Ц/(Лу — Ц. Ь) Пусть Рл = Сл — Л?Ни-1/1в ЛХ, где Ся определяется формулой (5). Докажите, что Вя = О(?У); следовательно.
Ся = Х)ойм Х+ 0(Х). [Указание. Используйте (а) и теорему 1.2.7А.] 28. [ЗУ] Определите значение бесконечного произведения с точностью до пяти значащих цифр непосредственным вычислением. [Укаэанве. См. упр 5.1.1-16.] 27. [НМУ1] Чему с точностью до 0(Ц равно асимптотическое значение Ся нз (14)? 28. ]НМЗО] Найдите асимптотическое среднее количество проверок цифр при выполнении в случайном М-арном дереве цифрового поиска при М > 2.
Рассмотрите случай как успешного, так и неудачного поиска, дайте ответ с точностью до 0(37 '), 29. [НМЗО] Чему равно асимптотическое среднее количество узлов в ЛХ-арном дереве цифрового поиска, все ссылки которых пусты? (Можно было бы сэкономить памятен исключая такие узлы; см. упр. 13.) ЗО. [ЛЩ] Покажите, что производящая функция алгоритма "Патриция" Ь„(х), определенная в (15), может быть выражена в совершенно ужасном виде: (Таким образом, если бы имелась простая формула для Ь (х), можно было бы упростить это громоздкое выражение ) 31.
[М81] Решите рекуррентное соотношение (16). 32. [МЯ1] Чему равно среднее значение суммы всех полей ЗК1Р в случайном дереве алгоритма "Патриция" с Х вЂ” 1 внутренним узлом? ЗЗ. [МОО] Докажите, что (18) представляет собой решение рекуррентного соотношения (17). [Указание. Рассмотрите производящую функцию А(х) = ~ „>е а„х"/ггЬ] 34. [НМЗО] Назначение данного упражнения — поиск асимптотического поведения формулья (18). а) Докажите, что при я > 2 п х (,ь-/2ь ' — 1 ~-'~ 2гв И п 2/' е<ь< зй1 Ь) Покажите, что слагаемые в правой части (а) приближенно равны 1/(е' — ц — 1/х+ 1/2, где х = и/2', получающаяся прн этом сумма отличается от первоначальной на 0(п ). с) Покажите, что Гз"™ — — + — = — / Ь(в)Г(в)х *г1с для действительного х > О.
е — 1 я 2 2я1/ т и) Следовательно, рассматриваемая сумма равна рЬ+'" ав)г(.)п-- „ 2л1,/ Ь ом 2-' — 1 Оцените этот интеграл. ° 35. (М20) Какова вероятность того, что дерево алгоритма "Патриции" с питью ключами имеет вид причем в полях 8812 содержатся а, Ь, с, 0, как показано на рисунке'? (Считаем, что ключи имеют независимые случайные биты; ответ должен иметь вид функции от а, Ь, с н 0.) 36. (М25) Имеется пять бинарных деревьев с тремя внутренними узлами в каждом. Если рассмотреть, как часто каждое из них служит деревом поиска в различных алгоритмах при случайных данных, то получатся следующие различные вероятности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
