|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[143] а.Профессор говорит, что данная процедура работает быстро, поскольку фактическое время исполнения строки 7 есть 0(1). Какое обстоятельство он упускает из виду? б.Оцените сверху время выполнения процедуры New-Delete для случая ж ф тгп[Н] в терминах degree[x] и числа с вызовов процедуры Cascading-Cut. в.Пусть Н - фибоначчиева куча, получающаяся в результате выполнения процедуры New-Delete (if, ж). Предполагая, что вершина ж не является корнем, оцените потенциал кучи Н в терминах величин degree[x], с, t[H] (число деревьев в корневом списке) и т[Н] (число отмеченных вершин). г.Получите оценку для учётной стоимости выполнения New-Delete для случая ж ф тгп[Н]. Будет ли она лучше прежней? 21-2 Дополнительные операции над фибоначчиевыми кучами Мы хотим реализовать ещё две операции, не меняя учётной стоимости ранее рассмотренных операций. а.Придумайте эффективную реализацию операции Fib-Heap-change-key(ii, ж, к) которая присваивает ключу вершины ж новое значение к. Оцените учётную стоимость этой операции (при вашей реализации) для случаев к < кеу[х], к = кеу[х], к > кеу[х]. б.Придумайте эффективную реализацию операции Fib-Heap-prune(ii, г) которая удаляет min(r, ra[ii]) вершин из Н (всё равно каких). Оцените учётную стоимость этой операции (для вашей реализации). (Указание: может потребоваться изменение структуры данных и потенциальной функции.) Замечания Фибоначчиевы кучи ввели Фредман и Тарьян [75]. В их статье описаны также приложения фибоначчиевых куч к задачам о кратчайших путях из одной вершины, о кратчайших путях для всех пар вершин, о паросочетаниях с весами и о минимальном покрывающем дереве. Впоследствии Дрисколл, Сарнак, Слеатор и Тарьян разработали структуру данных, называемую «relaxed heaps», как замену для фибоначчиевых куч. Есть две разновидности такой структуры данных. Одна из них даёт те же оценки учётной стоимости, что и фибоначчиевы кучи. Другая позволяет выполнять операцию Decrease-Key за время 0(1) в худшем случае (не учётное), а операции Extract-Min и Delete - за время О (lgra) в худшем случае. Эта структура данных имеет также некоторые преимущества (по сравнению с фибоначчиевыми кучами) при использовании в параллельных алгоритмах. 22Системы непересекающихся множеств В некоторых приложениях полезна следующая структура данных: п элементов разбиты в объединение непустых непересекающихся множеств, причем поддерживаются операции «объединение» (два данных множества заменяются на их объединение) и «найти множество» (по данному элементу выяснить, в каком из множеств он лежит). В этой главе рассказано, как можно реализовать такую структуру данных. В разделе 22.1 мы даём точное определение интересующей нас структуры данных и приводим простой пример ее применения. В разделе 22.2 обсуждается простейшая реализация с помощью списков. Раздел 22.3 посвящен более эффективной реализации с помощью леса. Для неё время выполнения то операций немного превосходит О (то) - настолько немного, что для всех практических целей можно считать, что время выполнения то операций есть О (то). Более точно, время выполнения то операций не превосходит С(то)то, где С(то) растёт с ростом то, но очень медленно: коэффициент С(то) можно оценить сверху с помощью так называемой «обратной функции Аккермана». Определение обратной функции Аккермана даётся в разделе 22.4. Там же доказывается более слабая (и более просто доказываемая) верхняя оценка времени работы. 22.1. Операции с непересекающимися множествами Система непересекающихся множеств (disjoint-set data structure) есть набор непересекающихся непустых множеств, в каждом из которых зафиксирован один из элементов - представитель (representative). При этом должны поддерживаться следующие операции: Make-Set(s) («создать множество»). Создаёт новое множество, единственным элементом (и тем самым представителем) которого является х. Поскольку множества не должны пересекаться, требуется, чтобы элемент х не лежал ни в одном из уже имеющихся множеств. |
Среды: 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 | ||