|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[104] Рис. 16.3 Таблицы с и Ь, созданные алгоритмом LCS-LENGTH при X = (А, В, С, В, D, А, В) и Y = (В, D, С, А, В, А). В клетке с координатами записаны число с[г, j] и стрелка b[i,j]. Число 4 в правой нижней клетке есть длина НОП. При i,j > 0 значение с[г, j] определяется тем, равны ли х, и и вычисленными ранее значениями с[г - 1, j], c[i,j - 1] и с[г - 1, j - 1]. Путь по стрелкам, ведущий из с[7, 6], заштрихован. Каждая косая стрелка на этом пути соответствует элементу НОП (эти элементы выделены). LCS-Length(X, У)
На рис. 16.3 показана работа LCS-Length для X = (А, В, С, В, D,A,B)nY = (В, D, С, А, В, А). Алгоритм LCS-Length требует времени О (ran): на каждую клетку требуется 0(1) шагов. Построение НОП Таблица Ь, созданная процедурой LCS-Length, позволяет быстро найти НОП последовательностей X = (х\, ж2,..., хт) и Y = (у\, у2, , уп)- Для этого надо пройти по пути, указанному стрелками, начиная с Ь[т,п]. Пройденная стрелка \ в клетке (i,j) означает, что жг- = yj входит в наибольшую общую подпоследовательность. Вот как это реализовано в рекурсивной процедуре Print-LCS (НОП для X и Y печатается при вызове Print-LCS(6,X, length[X], length[Y})): print-LCS(6,X,i,j) 1if г = 0 или j = О 2then return 6elseif b [i, j] = <ф> 7then PRiNT-LCS(6,X,i-l,j) 8else PRiNT-LCS(6,X,i,j - 1) Будучи применённой к таблице рис. 16.3, эта процедура напечатает ВС В А. Время работы процедуры есть 0(m + ra), поскольку на каждом шаге хотя бы одно из чисел тип уменьшается. Улучшение алгоритма После того, как алгоритм разработан, нередко удаётся сделать его более экономным. В нашем примере можно обойтись без таблицы Ь. В самом деле, каждое из чисел c[i, j] зависит от с[г - 1, j], c[i,j - 1] и c[i - 1, j - 1]. Зная c[i, j], мы можем за время 0(1) выяснить, какая из этих трёх записей использовалась. Тем самым можно найти НОП за время О (то + га) с помощью одной только таблицы с (в упражнении 16.3-2 мы попросим вас это сделать). При этом мы экономим О(тога) памяти. (Впрочем, асимптотика не меняется: объём таблицы с есть также О (тога).) Если нас интересует только длина наибольшей общей подпоследовательности, то столько памяти не нужно: вычисление c[i,j] затрагивает только две строки с номерами г и г - 1 (это не предел экономии: можно обойтись памятью на одну строку таблицы с плюс ещё чуть-чуть, см. упражнение 16.3-4). При этом, однако, саму подпоследовательность найти (за время 0(то+ га)) не удаётся. 3 4 5 if Ь [г, j] = «\» then PRiNT-LCS(6,X,i напечатать жг- Упражнения 16.3-1 Найдите НОП последовательностей (1,0,0,1,0,1,0,1) и (0,1,0,1,1,0,1,1,0). 16.3-2 Разработайте алгоритм, строящий НОП для X = (жь ж2,..., хт) и У = (j/i, г/2, • • •, Уп) за время 0(т + га), исходя только из таблицы с. 16.3-3 Разработайте рекурсивный вариант алгоритма LCS-Length с запоминанием ответов, требующий времени О (ran). 16.3-4 Покажите, как можно вычислить длину НОП, используя память размера 2 тш(то, га) +0(1) и храня лишь часть таблицы с. А как это сделать, используя память тш(то, га) + 0(1)? 16.3-5 Разработайте алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из га чисел и работающий за время О (га2). 16.3-6* Разработайте алгоритм, решающий предыдущую задачу за время О (га log га). (Указание. Храним для каждого г наименьший из последних элементов возрастающих подпоследовательностей длины г. Как меняются эти числа при добавлении нового элемента?) 16.4. Оптимальная триангуляция многоугольника Несмотря на свою геометрическую формулировку, эта задача очень близка к задаче о перемножении матриц. Многоугольник (polygon) - это замкнутая кривая на плоскости, составленная из отрезков, называемых сторонами (sides) многоугольника. Точка, в которой сходятся две соседние стороны, называется вершиной (vertex). Несамопересекающийся многоугольник (только такие мы и будем, как правило, рассматривать) называется простым (simple). Множество точек плоскости, лежащих внутри простого многоугольника, называется внутренностью (interior) многоугольника, объединение его сторон называется его границей (boundary), а множество всех остальных точек плоскости называется его внешностью (exterior). Простой многоугольник называется выпуклым (convex), если для любых двух точек, лежащих внутри или на границе многоугольника, соединяющий их отрезок целиком лежит внутри или на границе многоугольника. Выпуклый многоугольник можно задать, перечислив его вершины против часовой стрелки: многоугольник Р = (vq, v\, ..., fra i) |
Среды: 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 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||