AOP_Tom3 (1021738), страница 126
Текст из файла (страница 126)
ь 36. (НМ25] (Клод Шенноя (С!апбе ЯЬаппоп).) Пусть Л и У . случайные величины, принимающие конечные мяожества значений (хп...,х,) и (ум,у„). Введем обозначения р, = Рг(Л = х,), д, = Рг(У = уз), го = Рг(Х = х; и У = у,); кроме того, положим, что Н(Х) = Н(рп...,р ) и Н(У) = Н(дм...,д„) представляют собой энтропии Х и У оптимальны с з < г и ! > !'. Воспользуйтесь предположением индукции лля доказательства того, что суШествует оптимазьное дерево с корнем Я, у которого Я располагается на уровне !', а также оптимальное дерево с корнем (з) и узлом Я на уровне !.) 28. ]24] Используйте некоторый макроязык для определения макроса "оптимальный бинарный поиск", параметром которого является вложенная спецификация оптимального бинарного дерева.
29. (40] Каково наихудшее бинарное дерево поиска для 31 наиболее употребительного английского слова (эти слова представлены вместе с частотами их появления на рис. 12)7 30. ]МУ4'] Докажите, что цена оптимальных бинарных деревьев поиска удовлетворяет »квадрантному неравенству» с(0 у) — с(~,. 2-1) > с(~+1,7) — с(1+1, 1 — 1) при ! > 1+ 2. 31.
]МУЗ] (К. Ч, Тан (К. С. Тап).) Докажите, что среди всех распределений вероятнсютей (ры.; р; до:,д ) (р~+ +р»+до+ +д» = 1) дерево с минимальной ценой наиболее дорого при р, = 0 для всех 1, д = 0 для всех четных 1 и дз = 1/(и/2] для всех нечетных 11 ь 32. ]М25] Пусть я+1 = 2м+15 гдеО < )г < 2 . Сушествует ровно (~„) бинарныхдеревьев, в которых все внешние узлы расположены яа уровнях т и т+ 1. Покажите, что среди всех этих деревьев мы получим одна с минимальной ценой для весов (рн, .., р»н до,..., д„), если примбним алгоритм К к весам (рн.,., р; И+де,, М+д») при достаточно большом М. ЗЗ. (М41] Для нахождения бинарного дерева поиска, минимизирующего вреия работы программы Т, следует минимизировать величину 7С + С1, а не просто количество сравнений С.
Разработайте алгоритм для поиска оптимальных бинарных деревьев поиска, когда левые и правые ветви дерева имеют разные цены. (В случае, когда "правая" цена в два раза болыпе "левой", а частоты всех узлов одинаковы, оптимвльнымн становятся деревья Фибоначчи ]ем Ь. В. Ясап(е), »АСМ 17 (1970), 508 — 517].) На машинах, которые не могут получать результат сравнения из трех возможных (больше, меньше, равно), программа, реализуюшая алгоритм Т, вынуждена производить на шаге Т2 два сравнения — меньше и больше. Б.
Шейл (В. Зйе)!) и В. Р. Пратт (У. К. Ргагс) обнаружили, что эти сравнения не требуют одного и того же ключа и может оказаться предпочтительным бинарное дерево, внутренние узлы которого определяют либо проверку равенства, либо проверку "меньше, чем", но не обе Такая ситуация может оказаться интересной альтернативой поставленной задаче. 34. (НМ2! ] Покажите, что асимптотическое значение полиномиального коэффициента па отдельности, а Н(ХУ) = Н(гсс,..., г„„,) — энтропия их совместного распределения.
Докажите, что Н(Х) < Н(ХУ) < Н(Х)+Н(1.), (Указание. Если 1 — вогнутая функция, то Е) (Х) < )'(Е Х).) 37. [НМ26] (П. Дж. Байер (Р. 1. Вауег), 1975.) Предположим, что (Рс,, Р ) представляет собой случайное распределение вероятностей, а именно — с.лучайную точку в (и — 1)-мерном симплексе, определенную величинами Рь > О, 1 < й < и, где Рс + . + Р, = 1 (или, чта то же самое, (Рс,..., Р„) представляют собой множество случайных ссровсслсуиское, о которых говорилось в упр. 3 3.2-.2б). Чему равно ожидаемое значение энтропии Н (Рс,, Р ) 7 38.
[М20] Поясните, почему теорема М справедлива в общем случае, хотя мы доказали ее только для случаи во < вс < вв « в„ Я 39. [М25] Пусть сос, ..., ш„представляют собой неотрицательные веса (сос+ +ш = 1). Докажите, что взвешенная длина пути дерева Хаффмана, построенного в разделе 2.3.4.5, меньше, чем Н(сон ..,, ш„) + 1, (Указание. Обратитесь к доказательству теоремы М.) 40. [М26] Завернсите доказательства леммы Е. 41.
[21] На рис. 18 показано строение весьма запутаннога бинарного дерева. Перечислите ега листья в порядке слева направо. 42. (2Я! Обьясните, почему в подпрограмме С сохранаяетгя справедливость условия (31). 43. [26] Поясните, как эффективна реализовать фазу 2 алгоритма Гарсия-Вача. ь 44. [25] Поясните, как эффективно реализовать фазу 3 алгоритма Гарсия-Вача. построй- те бинарное дерево с уровнями 1о, 1с, ..., („ листьев в симметричном порядке. ь 43.
[УО] Поясните, как реализовать подпрограмму С так, чтобы общее врелся работы алгоритма Гарсия-Вача не превышало 0(и!об и). 46. [МУО] (Ч. К Вонг (С. К, 17оп8) и Ши-Куо Чанг (ЯЬ1-Ксса СЬассй).) Рассмотрим схему, в которой бинарное дерево поиска строится согласно алгоритму Т, но, когда количество узлов достигает значений вида 2" — 1, дерево реорганизуется в идеально сбалансированное дерево с 2" узлами иа уровне )с, 0 < 1с < и. Докавсите,что общее количество сравнений, выполненных при построении такого дерева, в среднем равно Н 18 Ас + Г)(Н). (Нетрудно показать,что время, необходимое для реорсвнизации дерева, составляет 0(Н) ) 47. [М4О] Обобщите теоремы В и М для 1-арных деревьев.
По возможности рассмотрите случай, когда цены ветвей неодинаковы, как в упр ЗЗ. 48. [М47] Проведите точный анализ устойчивого состояния бинарного дерева поиска при случайных вставках и удалениях 49. [НМ42] Проанализируйте среднюю высоту бинарного дерева поиска. б.2.3. Сбалансированные деревья Алгоритм вставки в дерево, который мы только что изучили, дает хорошие результаты при использовании случайных входных данных, на все же существует неприятная возможность того, что при этом будет построено вырожденное дерево. Можно было бы разработать влсаритм, поддержинающий дерево в оптимальном состоянии все время, однако это, к сожалению, очень сложная задача.
Другая идея заключается в том. чтобы хранить общую длину цуги и полностью реорганизовывать дерево, когда ана превьппает, наприлсер, ЗН!8 Н, Тем не менее при таком подходе потребовалось бы поРЯдка зссУ/2 РеоРганизаций деРева в пРоцессе ега постРоениЯ. Очень красивое решение проблемы поддержания дерева поиска в хорошем состоянии было открыто в 1962 году двумя советскими математиками — Г.
М. АдельсонВельским и Е, М. Ландисом (ДАН СССР 146 (1962), 263-266; английский перевод Яоч1ее Май. 3, 1259-1263]. Их метод требует всего лишь двух дополнительных битов иа узел и никогда не использует более 0(!ой!У) операций для поиска по дереву или вставки элемента. Предложенный подход также дает общую технологию представления линейных списков длиной Х таким образом, что любая из следующих операций может быть выполнена за время 0(!ойдо).
1) поиск элемента по заданному ключу; й) поиск и-го элемента по заданному к: ш) вставка элемента в определенное место; 1ч) удаление определенного элемента. При последовательном расположении элементов линейных списков операции (1) и (й) выполняются очень эффективно, в то время как операции (ш) и (1ч) требуют порядка !У шагов. С другой стороны, при использовании связанных элементов эффективно будут выполняться операции (ш) и (1ч), а операции (1) и (й) потребуют порядка Ж шагов. Представление линейных списков в виде дерева позволяет выполнить есе чешмре операции за 0(1о81ч') шагов.
При этом можно более или менее эффективно выполнять и другие операции, например сцепление списка из М элементов со списком из Х элементов за 0(1ой(М + 1Ч)) шагов. Метод, предоставляющий все эти преимущества, будем называть сбалансированными деревьями (многие авторы используют термин А ч'Ь-деревья — по первым буквам фамилий авторов). Предыдущий абзац служит рекламой сбалансированных деревьев — эдакой панацеи от всех бед. Имея в руках такой мощный метод, можно смело выбросить на помойку все прочие методы! Однако не торопитесь - сначала сбвлаисируйте свое отношение к сбалансированным деревьям. Ведь.
например, если все четыре операции не нужны, нас может удовлетворить менее универсальный, ио более быстрый (для данного конкретного случая) и проще программируемый метод. Кроме того, сбалансированные деревья хороши при наличии большого количества элементов. Судите сами: егзи есть эффективный метод, который требует 64 1е Х единиц времени. и неэффективный, которому необходимо 2!У единиц, то при 1ч' ( 256 следует использовать неэффективный метод, который при этом становится более эффективным... С другой стороны, при очень больших Х хранение данных во внутренней памяти становится невозможным, а при использовании внешних файлов с прямым доступом более эффективны другие методы, о которых речь пойдет в рюзделе 6.2.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
