Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 124
Текст из файла (страница 124)
21.4-1. 21.4-2. 2 1.4-3. Докажите лемму 21.4. Докажите, что ранг произвольного узла не превышает [1к и]. С учетом решения упражнения 21.4-2, сколько битов требуется для хра- нения поля гаик [х] узла х? 21.4-4. Используя решение упражнения 21.4-2, приведите простое доказательство того факта, что операции над лесом непересекающихся множеств с использованием объединения по рангу, но без сжатия пути, выполняются за время О (т 1я и).
Профессор полагает, что поскольку ранг узла строго возрастает вдоль пути к корню, уровни узлов должны монотонно возрастать вдоль этого пути. Другими словами, если гаик [х] ) 0 и р[х] — не корень, то 1ече1 (х) < 1ече1 (р [х]). Прав ли профессор? Рассмотрим функцию гг'(и) = ппп(й: Аь(1) > 1к(и+1)). Покажите, что для всех практических применений гг' (и) < 3. Покажите также, воспользовавшись решением упражнения 21.4-2, каким образом следует модифицировать аргумент потенциальной функции для доказательства того,что последовательность изтопераций Млке Янт,1)н1онирп и Бег, и из которых — операции Млнн Бнт, может быть выполнена над лесом непересекающихся множеств с использованием объединения по рангу и сжатия пути за время О (т гг' (и)) в наихудшем случае.
2 1.4-5. * 21.4-6. Задачи 21-1. Минимум в автономном режиме Задача лоиска минимума в автоаамиом режиме (ой-11ле пппппшп ргоЬ1еш) состоит в следующем. Пусть имеется динамическое множество Т с элементами из области определения (1,2,...,и), поддерживающее операции 1нзвкт и Ехтклсг Мпч. Задана последовательность Я из и Доказательство. Непосредственно следует из лемм 21.7, 21.10, 21.11 и 21.12. ° Упражнения Часть Ч. Сложные структуры данных 602 вызовов 1нзккт и т вызовов Ехтклст Мпч, в юторой каждый ключ из (1,2,...,п) вставляется ровно один раз.
Мы хотим определить, каюй ключ возвращается каждым вызовом Ехтклст Мпч, т.е. мы хотим заполнить массив ех$гас1ей [1..т], где ех~гасгей [г) (1 = 1, 2,..., т) представляет собой ключ, возвращаемый 1-м вызовом Ехтклст Мпч. Задача "автономна'* в том смысле, что перед тем как приступить к вычислениям, ей известна вся последовательность Я полностью. а) В следующей последовательности каждый вызов 1нзккг представлен вставляемым числом, а каждый вызов Ехтклст Мпч представлен буквой Е: 4, 8, Е, 3, Е, 9, 2, 6, Е, Е, Е, 1, 7, Е, 5. Заполните массив ехЬ асилей.
Для разработки алгоритма для решения этой задачи разобьем последовательность Е на гомогенные подпоследовательности, т.е. представим 8 в таюм виде: 1ы Е, 1з, Е, 1з,..., 1, Е, 1 +3 где каждая буква Е представляет один вызов Ехтклст Мпч, а 1 — последовательность (возможно, пустую) вызовов 1нзпкт. Для каждой подпоследовательности 1 мы сначала помещаем ключи, вставленные данными операциями, в множество К (которое является пустым, если подпоследовательность 1, пуста). Затем сделаем следующее: Огг 1пчн М~ммим[пз, и) 1 хогг' -1гоп 2 йо Определяем 3, таюе что г е Ку 3 113 от+1 4 гйеп ехгтас~ей Ц вЂ” ю' 5 Пусть 1 — наименьшее значение, большее 3 для которого существует множество К~ 6 К~ +- Ку 0 Кп уничтожаем К. 7 геФнгп ехйас1еИ б) Покажите корректность массива ех$гас1еа, возвращаемого процедурой Огг 1пчп Мммим.
в) Опишите, как эффективно реализовать процедуру Огг 1.!нв М~ммсм с использованием структур данных для непересекающихся множеств. Дайте точную оценку времени работы вашей реализации в наихудшем случае. Глава 21. Структуры данных для непересекающихся множеств 603 21-2. Определение глубины В задаче по определению глубины 1дердз-де1епшпа6оп ргоЫет) мы работаем с лесом Т = (Т;) корневых деревьев, в котором поддерживаются следующие три операции.
МАке Тнее(п) создает дерево, состоящее из единственного узла е. Р1НР РЕРТН(с) возвращает глубину узла и в его дереве. ОЕАет(т, е) ("прививка") делает узел г, являющийся корнем, дочерним по отношению к узлу с, который находится в дереве, корень которого отличен от г, но при этом не обязательно должен сам быть корнем. а) Предположим, что мы используем представление дерева такое же, как и в случае непересекающихся множеств: р [с] является родительским узлом с, и если о — корень, то р [с] = е.
Реализуем процедуру Оклет(г, и) путем присвоения р [т] + — и, а Р1нп Регтн(п) — как поиск пути к корню с подсчетом всех узлов (кроме п), встречающихся на этом пути. Покажите, что время работы последовательности из гп процедур Млке Ткее, Р!х0 РеРтн и Оклет в худшем случае равно г) Используя объединение по рангу и сжатие пути, мы можем снизить время работы в наихудшем случае. Воспользуемся лесом непересекающихся множеств 8 = (Яз), где каждое множество о1 (представляющее собой дерево) соответствует дереву Т; в лесу Т. Структура дерева в Яг не обязательно соответствует структуре дерева Т;.
Однако хотя реализация Яг не хранит точные отношения родитель-потомок, но тем не менее она позволяет нам определить глубину любого узла в Ть Ключевая идея состоит в хранении в каждом узле с "псевдодистанции" Ы [о], которая определена таким образом, что сумма псевдодистанций вдоль пути от е к корню его множества 51 равна глубине п в Т;; т.е. если путь от и к корню Яг представляет собой последовательность по,пм, еь, где по = сь и сь — корень Я;, то глубина е в Т, равна 2.з=о д [ьу]. б) Приведите реализацию процедуры МАКЕ ТНЕЕ.
в) Покажите, как следует изменить процедуру Р1 в Бет лля реализации процедуры Р1хп дегтя. Ваша реализация должна осуществлять сжатие пути, а время ее работы линейно зависеть от длины пути. Убедитесь в корректности обновления псевдодистанций вашей процедурой. 604 Часть Ч. Сложные структуры данных г) Покажите, как можно реализовать процедуру ОКАет(т, и), которая объединяет множества, содержащие т и и, модифицируя процедуры Бн1он и Ь1нк.
Убедитесь в корректности обновления псевдодистанций вашей процедурой. Не забывайте, что корень множества Я; не обязательно должен быть корнем соответствующего дерева Т,. д) Дайте точную оценку времени работы в наихудшем случае последовательности из тп операций МАке Ткее, Р1н0 1)еетн и ОЕАР, и из которых — операции МАке Ткее. 21-3.
Алгоритм Таржана для автономного поиска наименьшего общего предка наименыиий общий предок (1еам сопппоп апсез1ог) двух узлов и и и в корневом дереве Т представляет собой узел ю, который среди узлов, являющихся предками как и, так и и, имеет наибольшую глубину. В задаче автономного ноиска наименыиего общего предка (ой'-1ше !еаз1- сопппоп-апсез1ог ргоЫет) дано корневое дерево Т и произвольное множество Р = ((и, иЦ неупорядоченных пар узлов в Т. Для каждой пары узлов нз Р требуется найти их наименьшего общего предка.
Для решения задачи автономного поиска наименьшего общего предка осуществляется обход дерева Т путем вызова приведенной ниже процедуры 1 СА(тиос [Т]). Предполагается, что перед вызовом процедуры все узлы помечены как тин1те 1белые): 1.СА(и) 1 МАКЕ БЕТ(и) 2 апсевсот[Р1Х0 БЕТ(и)] — и 3 Рог (для) каждого и, дочернего по отношению к и 4 до ЬСА(и) 5 ЫН1ОН(и, и) 6 апсевтот[Р1Н0 БЕт[и)] + — и 7 со1от[и] — НЬАСК 8 1ог (для) каждого и, такого что (и, и) Е Р 9 Йо 11 со1от[и] = В1.АСК 1О Феп рпп1 "Наименьшим общим предком" и" и "и "является" апсев1от[Р1но бег[и)] а) Покажите, что строка 10 выполняется в точности по одному разу для каждой пары (и, и) Е Р.
б) Покажите, что при вызове ЬСА[и) количество множеств в структуре данных для непересекающихся множеств равно глубине и в Т. в) Докажите, что процедура 1.СА правильно выводит наименьших общих предков для каждой пары (и, и) Е Р. Глава 21. Структуры данных для непересекающихся множеств 605 г) Проанализируйте время работы процедуры ЬСА в предположении, что используется реализация непересекающихся множеств из раздела 21.3. Заключительные замечания Многие важные результаты о структурах данных для непересекающихся множеств в той или иной степени принадлежат Таржану (Таг1ап). В частности, именно им [290, 292) установлена точная верхняя граница с применением очень медленно растущей инверсии а (т, и) функции Аккермана (Аскеппапп). (Функция Аь (т'), используемая в разделе 21.4, подобна функции Аккермана, а функция ст (и) — ее инверсии.
Для всех мыслимых значений т и и как а (и), так и а (т, и) не превышают 4.) Верхняя граница О (т 1к' и) была доказана несколько ранее Хопкрофтом (Норсгой) и Ульманом ((Л1шап) (5, 155). Материал раздела 21.4 основан на более позднем анализе Таржана (294], который, в свою очередь, опирается на анализ Козена (Кохеп) [193]. Харфст (НагЫ) и Рейнгольд (КешяоЫ) [139] разработали версию доказательства полученных Таржаном оценок при помощи потенциалов. Таржан и ван Леувен (чап Ьееиттел) [295] рассмотрели разные варианты эвристики со сжатием пути, включая однопроходные варианты, которые эффективнее двухпроходных в силу меньшего постоянного множителя.
Позже Харфст и Рейнгольд [! 39] показали, какие (небольшие) изменения следует внести в потенциальную функцию для адаптации их анализа сжатия пути к однопроходному варианту Таржана. Габон (баЬотт) и Таржан [103] показали, что в некоторых приложениях операции над непересекающимися множествами могут выполняться за время О (т).
Таржан [291] показал, что для операций над произвольными структурами данных для непересекающихся множеств, удовлетворяющими определенным техническим условиям, нижняя граница времени работы равна П (та (т, и)). Позже эта нижняя граница была обобщена Фредманом (Ргейпап) и Саксом (Бака) [97], которые показали, что в наихудшем случае эти операции требуют обращения к П (т а (т, и) ) словам памяти длиной !к и битов. ЧАСТЬ У1 Алгоритмы для работы с графами Введение Графы представляют собой распространенные структуры в информатике, и алгоритмы для работы с графами очень важны.
Имеются сотни интересных вычислительных задач, сформулированных с использованием графов. В этой части мы коснемся только некоторых наиболее важных из них. В главе 22 рассматриваются вопросы представления графов в компьютере и обсуждаются алгоритмы, основанные на обходе графа в ширину и в глубину. Приведены два применения обхода в глубину — топологическая сортировка ориентированного ациклического графа и разложение ориентированного графа на сильно связные компоненты. В главе 23 описывается вычисление остовного дерева минимального веса. Такое дерево представляет собой набор ребер, связывающий все вершины графа с наименьшим возможным весом (каждое ребро обладает некоторым весом). Эта задача решается при помощи жадного алгоритма (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
