|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[149] Find-Depth (v) Возвращает глубину (расстояние до корня) вершины v. Graft(t, v) («прививка»). Вершина г должна быть корнем одного из деревьев, вершина v должна принадлежать к какому-то другому дереву; дерево с корнем г «прививается» к дереву, содержащему v, при этом v становится родителем г. (а)Пусть мы реализовали эту структуру данных следующим образом. Деревья представляются как в лесе непересекающихся множеств (p[v] - родитель вершины v, если v - не корень, и p[v] = v, если v - корень), процедура Graft(t, v) состоит в присваивании p[r] <- v, процедура Make-Tree написана очевидным образом, и, наконец, для нахождения глубины (Find-Depth)) мы идем из v в корень и подсчитываем длину пути. Покажите, что при этом стоимость т операций Make-Tree, Graft и Find-Depth в худшем случае есть 0(то2). Алгоритм можно ускорить, если воспользоваться объединением по рангам и сжатием путей. Заметим, что структура дерева, нужного для сжатия путей, не обязана соответствовать структуре исходного дерева - важно лишь, чтобы можно было восстанавливать информацию о глубине (ребро нового дерева должно хранить информацию о разнице глубин концов ребра в старом дереве). (б)Реализуйте операцию Make-Tree. (в)Реализуйте операцию Find-Depth. Ваш алгоритм должен использовать сжатие путей, а его время работы должно быть пропорционально длине пути поиска. (г)Реализуйте операцию Graft (действуйте по аналогии с алгоритмами Union и Link; корень в строимом дереве не обязан быть корнем в старом смысле). (д)Дайте точную оценку на стоимость последовательности т операций Make-Tree, Graft и Find-Depth, п из которых - операции Make-Tree (для худшего случая). 22-3 Алгоритм Тарьяна для нахождения наименьшего общего предка в режиме off-line. Наименьший общий предок (least common ancestor, сокращённо LCA) вершин и и v корневого дерева Г есть, по определению, вершина наибольшей глубины среди вершин, являющихся предками как и, так и v. Задача о нахождении наименьших общих предка в режиме off-line (off-line least-common-ancestors problem) состоит в следующем. Дано корневое дерево Г и некоторое множество Р неупорядоченных пар его вершин. Требуется для каждой пары вершин (и, v) £ Р найти их наименьшего общего предка. Ниже приведён алгоритм LCA, решающий эту задачу (наименьшие общие предки всех пар (и, v) £ Р будут напечатаны в результате вызова LCA(root[T]); вначале все вершины дерева - белые). LCA(u) 1Make-Set(и) 2ancestor[Find-Set(и)] \gets и 3for (для) каждого $v$, являющегося реб\"~~а5нком $и$ 4do LCA(v) 5Union(u,v) 6ancestor[Find-Set(и)] \gets и 7покрасить и в ч\"~~а5рный цвет 8for (для) каждой вершины v такой, что $(u,v)\in Р$ 9do if вершина v ч\"~~а5рная 10then print (Наименьший общий предок $и$ и $v$ есть ancestor[Find-Set(v)] (а)Покажите, что строка 10 исполняется в точности один раз для каждой пары (и, v) £ Р. (б)Покажите, что в результате вызова LCA(root[T]) каждый из последующих вызовов ЬСА(и) происходит в тот момент, когда количество непересекающихся множеств равно глубине вершины и в дереве Т. (в)Покажите, что в результате вызова LCА(корень[Т]) будут напечатаны наименьшие общие предки для всех пар (и, v) £ Р. (г)Оцените время работы алгоритма LCA в предположении, что система непересекающихся множеств реализована с помощью леса с объединением по рангам и сжатием путей. Замечания Многие важные результаты о системах непересекающихся множеств в той или иной мере принадлежат Тарьяну. В частности, именно он установил оценку 0(ma(m, п)) [186, 188]. Более слабая оценка 0(m\g* п) была ранее получена Хопкрофтом и Ульманом [4, 103]. В работе [190] Тарьян и ван Леувен обсуждают различные варианты сжатия путей, в том числе алгоритмы, работающие «за один проход» (иногда они работают быстрее «двухпроходных»). Габов и Тарьян [76] показали, что в некоторых приложениях операции с непересекающимися множествами можно выполнить за время О (га). В работе [187] Тарьян показал, что при некоторых дополнительных условиях стоимость операций с непересекающимися множествами не может быть ниже, чем 0(ma(m, га)), какую реализацию мы бы ни избрали. Фредман и Сакс [74] показали, что, кроме того, в худшем случае эти операции требуют обращения к Q(ma(m, п)) словам длиною в lg га битов. Алгоритмы на графах Введение Графы встречаются в сотнях разных задач, и алгоритмы обработки графов очень важны. В этой части книги мы рассмотрим несколько основных алгоритмов обработки графов. В главе 23 рассматриваются способы представления графа в программе, а также различные варианты обхода графа (поиск в ширину и в глубину). Приводятся два применения поиска в глубину: топологическая сортировка ориентированного графа без циклов и разложение ориентированного графа в сумму сильно связных компонент. В главе 24 рассматривается задача о покрывающем дереве (наборе рёбер, связывающем все вершины графа) минимального веса. (Мы предполагаем, что каждое ребро графа имеет некоторый положительный вес.) Для этой задачи применимы жадные алгоритмы (см. главу 18). В главах 25 и 26 рассматривается задача о кратчайших путях. Вновь каждому ребру приписано некоторое число, но теперь оно называется длиной ребра. Требуется найти кратчайшие пути из одной вершины во все остальные (глава 25) или кратчайшие пути из каждой вершины в каждую (глава 26). Наконец, в главе 27 расматривается задаче о максимальном потоке вещества через сеть труб ограниченной пропускной способности. Каждое ребро рассматривается как труба некоторой пропускной способости. В некоторой вершине находится источник вещества, а в другой - потребитель. Спрашивается, какой поток вещества можно передавать от источника к потребителю, не превышая пропускной способности труб. Эта задача важна, поскольку к ней сводится многие интересные задачи. Мы будем оценивать время обработки заданного графа G = (V, Е) в зависимости от числа его вершин (С) и рёбер ((-Е1)); мы будем для краткости писать V и Е вместо \ V\ и \Е\. В программах множество вершин граф G мы будем обозначать С[С], а множество рёбер - E[G]. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||