Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 24
Текст из файла (страница 24)
Посмотрите, ие окажется ли в дереве а„+~ ниже, чем а„.) Ь) Наг(лите простую формулу длв производящей функции С„(з) = 2 Р„ьз" и используйте ее для выражения Р„ь через числа Стирлинга. с) Чему равна дисперсол этого распределения? 7. [М85) (С. Р. Арора (5. Н. Агота) и В. Т. Дант (Ж. Т. 11епс),) Чему равно среднее количество сравнений, необходимое алгоритму Т для поиска ш-го наибольшего элемента по его ключу после вставки и элементов в случайном порядке в первоначально пустое дерево? й.
[МУК) Пусть р(п, я) — вероятность того, что полная длина внутреннего пути дерева, построенного по алгоритму Т из и случайным образом упорядоченных ключей, равна й (длина внутреннего пути дерева равна числу сравнений, производимых при сортировке путем вставки в дерево в процессе построения дерева). а) Найдите рехуррентное соотношение, которое определяет соответствующую производящую функцию. Ь) Вычислите дисперсию такого распределения.
(Прн выполнении этого упражнения могут оказаться полезными некоторые упражнения из раздела 1.2.7.) 9. [41) Мы доквзаян, что поиск по дереву и вставка требуют порядка 2 1п М сравнений при вставке ключей в случайном порядке. Однако на практике порядок вставки может быть не случайным. Праведнее. эмпирические исследования, чтобы выяснить, насколько хорошо вставка в дерево подходит для работы с реальными таблицами символов компилятора или ассемблера. Получится ли в результате вставки идентификаторов большой программы хорошо сбалансированное дерево поиска? ь 10. [32) (Р.
В. Флойд (Н. %. Р!оуд).) Предположим, нас не интересует порядок ключей в дереве поиска; однако ожидается, что данные будут вводиться в неслучайном порядке. Обдумайте методы, которые позволят сохранить эффективность поиска, делам входные данные кажущимися сэучайными. 11. [30) Чему равно максимальное число присвоений 3 +- 1Л.ХИК(й), выполняемых на шаге 03 при удалении узла из дерева размером № 12.
[Мйй) Как часто в среднем происходит переход от шага П1 к шагу В4 при случай- ном удалении из случайного дерева, состоящего нз А1 элементов? (См. доказательство теоремы Н.) ь 13. [МЗЗ) Если корень случайного дерева удаляется с помощью алгоритма П, останется ли получившееся в результате дерево случайным? ь 14. (ЙЙ) Докажите, что длина пути дерева, построенного согласно алгоритму П с допол- нительным шагом 011, никогда не превышает длину пути дерева, построенного без этого 2' 1 шага. В каком случае дополнительный шаг 01- уменьшает длину пути? 13.
[33) Пусть а~ аэ аз аэ — перестановка множества (1, 2, 3,4) и пусть 7 = 1, 2 или 3. Возьмем одноэлементное дерево с ключом ац выполним вставку элементов ам аэ по ал- горитму Т, уделим о, по алгоритму 0 и вставим аэ согласно алгоритму Т. Сколько деревьев из 4! х 3 возможных будут иметь вид 1, П, П1, 1Ч и Ъг соответственно (согласно классификации (13) )? ь 16. [33) Является ли операция удаления каммугаашоеной? Иначе говоря, получится ли одно и то же дерево, если с помощью алгоритма П будет сначала удален узел Х, а затем-- г'и сначала удален узел У, а затем — Л ? 17. [35) Покажите, что если в алгоритме Р полностью заменить "левое'" "правым', то его легко можно будет распространить на удаление данного узла из праеопрошишого дерева с сохранением необходимых нитей (см.
упр. 2), 18. [Мй?) Покажите, что., используя закон Зипфа, можно получить (12). 19. [Мйу] Чему равно приближенное среднее количество сравнений (11), если вероятности входных данных подчиняются закоиу "80-20"] определенному в б.1-(11)? 20. (Мйй] Предполохснм, что мы вставляем ключи в дерево в порядке уменьшения их частот р; > рт » . р . Не может ли такое дерево оказаться существенно хуже оптимального? 21. [МЗО] Если р, 4, г — случайно выбранные вероятности, такие, что 0+ 4+с = 1, чему равны вероятности того, что деревья 1, П, Ш, !Ч, У из (13) оптимальны? (Рассмотрите соотношения плсчцадей соответствующих областей на рис. 14.) 22. [Мйй] Докажите, что при выполнении шага К4 алгоритма К г[1,1-1] никогда не превышает с[1+1, Я. ь 23.
[М28] Найдите оптимальное бинарное дерево покска для случая М = 40 с весами р1 ы О, рз = рз = =1чо = 1, Яо = В = . = арго = 0 (не используя компьютер). 24. [МИ] Пусть р„= 4 = О, а все остальные веса иеотрнцательны. Докажите, что оптимальное ДеРево длЯ (РМ ..,,Рсн со,..., дь) может быть полУчено посРедством замены в любом оптимальном для (рм ., ., р„,; де,...,4„~) дереве. 25. [Мйй] Пусть А и  — непустые множества действительных чисел.
Определим, что А < В, если выполняется следующее: из (абА„ЬеВиЬ<а) следует (аЕВибйА). а) Докажите, что зто соотношение транзитнике иа иепустых множествак, Ъ) Докажите или опровергните, что А < В тогда и только тогда, когда А < А 11 В < В. 26. [Мйй] Пусть (рм...,р; де,..., о ) — неотрицательные веса и р„+д, = х. Докажите, что при х, изменяющемся от О до оо, и при постоянных (рм...,р„м 4о,,4 -~) цена с(0, и) оптимального бинарного дерева поиска является выпуклой, непрерывной, кусочполинейной функцией я с целымн угловыми козффициентвмн.
Другими аювами, докажите, что существуют положительные целые числ» 1е > 1~ > ° > 1ы н действительные константы О = хе < х~ < -" < х„, < х ь~ = оо н уе < р~ ° < р,, такие, что с(О, и) = рь + (лх при хь < к < хь~ и 0 < Ь < нь 2Т. [МУ?] Цель данного упражнения состоит в доказательстве того, что множестве корней И(1, 1) оптимальных бинарных деревьев удовлетворяет соотношению Н(1.,1' — 1) <)1(1,у) < Я(1+1,Я дляу — 1> 2, где отношение < введено в упр. 25 при неотрицательных весах (рм..., р; Оо, ., й ). Доказательство проводится по индукции по у — 1; наша задача состоит в том, чтобы доказать, что В(0, и — 1) < Я(О,н) при и > 2 в предположении справедливости соотношения при у — 1 < и.
(В силу симметрии отсюда следует, что В(О, и) < В(1, и).) а) Докажите, что В(0, и — 1) < В(О, и) при рь = 4 = О (см. Упр 24) Ъ) Пусть рь+ 0„=. х. Воспользуемся обозначениями упр. 26. Пусть Вь — множество оптимальных корней 1с(О,п) при кь < х < хьтм а )1ь — множество оптимальных корней для х = хл Докажите, что )Ц < Ве < )1', < В~ < .
< В,'„< Я Отсюда из п. (а) и упр. 25 следует, что Я(0, и-1) < Я(О,п) для всех а. (Уеиание. Рассмотрите случай х = хь в предположите, что деревья Ко,»-1) г(г,п) н г(0,$-1) г(з,п) Ена уровне 1' Я яа уровяе 1 р~Ф, рею, ..., р„Н) при )т' -> оо стремится к звтропии Н(рнрг,, р ). 35. [НМ22] Завершите доказательство теоремы В, доказав справедливость неравенства (24) ь ЗО. [Н 1135] (Клод Шеннон (С!апг1е БЬавпоп).) Пусть Х и У вЂ” случайные величины, принимающие конечные множества значений [хп..., х»,] и (ум ..,, 3„]. Введем обозна. чения р, = Рг(Х = хс), 01 = Рг(У = рг), гч = Рг(Х = хг и У = 01); кроме того, положим, что Н(Х) = Н(рн ..,,р, ) н Н(1 ) = Н(й~„...,а ) представляют собой энтропии Х н У оптималысм с е < г н 1 > 1'.
Воспользуйтесь предположением индукции для доказательства того, что существует оптимальное дерева с корнем Я, у которого ]и] располагается па уровне 1', а также оптимальное дерево с корнем ( еу и узлом Я на уровне 1.) 26. [3(] Используйте некоторый макроязык для определения макроса "оптимальный бинарный поиск", параметром которого является вложенная спецификация оптимального бинарного дерева. 20. [10] Каково наихудшее бинарное дерева поиска для 31 наиболее употребительного английского слова (этн слова представлены вместе с частотами мх появления на рис. 12)? 30.
[мЯз] докажите, что цена оптимальных бинарных деревьев поиска удовлетворяет "кввдрантному неравенству" с(11) — с(г„г-1) > с(г+1, 1) — с(1+1,1-1) при 2 ) г+2. 31. [МЮ5] (К. Ч. Тан (К. С. Тап).) Докажите, что среди всех распределений вероятностей (рн..., род аа,...,а,) (р~+ +р +аа+ +а = 1) дЕрЕВО С МИНИМаЛЬНОй цЕНОй Нанбапсв дорого прн р; = 0 для всех г, а1 = 0 для всех четных 1 н а1 = 1/[и/2] для всех нечетных 11 ь 32. [5125] Пусть и+1 = 2~+5, где 0 < й < 2™. Существует ровно [г„) бинарных деревьев, в которых все внешние узлы расположены ла уровнях гп и т+1.
Покажите, что среди всех зтих деревьев мы получим адно с минимальной ценой для весов (рн, р»; Ое,..., а„), если примбним алгоритм К к весам (рм..., р„,; М+Оа,..., М+д») при достаточно большом М. 33. [М41] Для нахождения бинарного дерева поиска, минимизирующего время работы программы Т, следует минимизировать величину ?С+ С1, а не просто какичеспю сравнений С. Разработайте алгоритм для поиска оптимальных бинарных деревьев поиска, когда левые и правые ветви дерева имеют разные цены.
(В случае, когда "правая" цена в два раза больше "левой", а частоты всех узлов одинаковы, оптимальными становятся деревья Фибоваччв [см. Ь. Е. Бгыг1е1,,7АСМ 17 (1970), 508-517].) На машинах, которые ие могут получать результат сравнения из трех возможных (больше, меньше, равно), програьгл~а, реалгь зующая алгоритм Т, вынуждена производить на шаге Т2 два сравнения — меньше и больше. Б. Шейл (В. Я)ге)1) и В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
