|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[268] Задачи 813 правую половины можно за линейное время). Соответственно мы обязаны при рекурсивном вызове передавать множества Pl и Pr в отсортированном виде. Ясно, что это нетрудно сделать, проходя массив от начала к концу и раскладывая его элементы на две группы. В некотором смысле это действие обратно в процедуре Merge, использованной при сортировке слиянием (раздел 1.3.1). Осталось заметить, что начальная сортировка (presorting) выполняется всего один раз и потому не входит в рекуррентное соотношение - её время нужно просто добавить к времени работы рекурсивной процедуры. Время этой сортировки есть О (га lgra), так что общее время есть сумма двух слагаемых вида О (га lgra) и потому есть О (га lgra). Упражнения 35.4-1 Профессор предлагает усовершенствовать алгоритм поиска пары ближайших точек и проверять только 5 точек массива У. Он говорит следующее: «Будем относить точки, принадлежащие прямой /, к множеству Pr. В этом случае на прямой / не будет совпадающих точек, которые относятся одновременно к двум множествам Pl и Pr- Поэтому внутри прямоугольника 6x26 будет содержаться не более 6 точек.» Что неправильно в идее профессора? 35.4-2 Покажите, что (без изменения асимптотики времени работы алгоритма) можно подавать на вход алгоритма множество, не содержащее совпадающих точек. Покажите, что, если совпадающих точек в множестве нет, то для каждой точки массива У достаточно проверять 6 (а не 7) соседних точек. Объясните, почему нельзя обойтись 5 ближайшими точками. 35.4-3 Определим Ьт-расстояние (Lm-distance) между точками р\ и р2 плоскости формулой (ж! - Ж2т + 12/i - у2\т)1/т- Евклидово расстояние соответствует значению р = 2. Измените приведённый в этом разделе алгоритм так, чтобы он искал ближайшие точки в смысле Li-расстояния. 35.4-4 Определим Loo-расстояние между точками р\ и р2 как тах(ж! - ж21, г/1 - г/21) - Как приспособить алгоритм поиска ближайших точек к случаю Loo-расстояния? 35.5. Задачи 35-1 Выпуклые слои Определим етрйвыпуклые слои (convex layers) множества Q точек плоскости. Первый выпуклый слой Q содержит точки множе- ства Q, которые являются вершинами CH(Q). Выбросим эти эти точки и снова найдём выпуклую оболочку - её вершины образуют второй выпуклый слой. Выбросим и их; возьмём выпуклую оболочку остатка; её вершины образуют третий выпуклый слой и т.д. a.Придумать способ за время 0(п2) найти все выпуклые слои множества из га точек плоскости. b.Покажите, что задачу сортировки га вещественных чисел можно свести к задаче отыскания выпуклых слоев, и потому в любой модели, где сортировка требует времени \Omega(n\gn), та же оценка верна и для задачи отыскания выпуклых слоев. 35-2 Максимум-слои Будем говорить, что точка плоскости (ж, у) мажорирует (dominates) точку (ж, у), если ж ж и у у. Пусть Q - множество точек плоскости. Если для точки из множества Q нет других точек из Q, мажорирующих её, то такую точку будем называть максимальной (maximal) в множестве Q. Таких точек может быть несколько; множество таких точек называют первым максимум-слоем. Удалив все эти точки, повторим процесс с оставшимся множеством точек, получим второй максимум-слой, и будет это повторять до тех пор, пока точки не кончатся. Предположим, что множество Q имеет к непустых максимум слоев L\, L2, , Lk- Пусть уг- - ордината самой левой точки слоя Li для г = 1,2,...к. Будем предполагать, что в Q нет двух точек с совпадающими абсциссами или ординатами. a.Докажите, что у\ > у2 > ... > Ук- Пусть точка (ж, у) находится левее любой из точек Q, а её ордината у отлична от ординат всех точек множества Q. Пусть д = ди{(ж,у)}. b.Обозначим через j наименьший из индексов, для которых yj < у; если такого индекса нет (у < ук), положим j = к + 1. Покажите, что максимум-слои множества Ql устроены так: Если j к, то все максимум-слои Q совпадают с максимум-слоями Q, за исключением слоя Lj, в который добавилась точка (ж, у) (и стала самой левой точкой нового Lj). Если j = к + 1, то первые к максимум-слоев множества Q такие же, как у Q, но кроме них есть непустой (& + 1)-ый слой, состоящей из единственной точки (ж, у). c.Опишите алгоритм, вычисляющий все максимум-слои множества из п точек за время О (га lgra). (Указание. Двигайте прямую справа налево.) d.Какие сложности возникнут, если среди точек есть точки с равными абсциссами или ординатами, и как можно поступить в таком случае? 35-3 Роботы и призраки. Команда из га роботов сражается с га призраками. Каждый робот Задачи 815 вооружён протонным ружьём, луч которого уничтожает призрак. Луч движется по прямой и обрывается, встретив призрак. Тактика роботов такова: каждый выбирает себе призрак (при этом образуется га пар робот - призрак), а затем все роботы одновременно выпускают лучи каждый в свое приведение. При этом нельзя, чтобы выпускаемые роботами лучи пересеклись. Считаем, что положение каждого робота и каждого призрака - заданная точка плоскости, и никакие три из этих точек не лежат на одной прямой. a.Доказать, что всегда существует прямая, соединяющая одного из роботов с одним из призраков, для которой число роботов по одну сторону от неё совпадает с числом призраков с той же стороны. Придумайте, как найти такую прямую за время О (га lgra). b.Постройте алгоритм, за время О (га2 lg га) группирующий роботов и приведений в пары так, чтобы выпускаемые роботами лучи не пересекались. 35-4. Распределение с малой оболочкой. Пусть мы хотим построить выпуклую оболочку множества случайных точек плоскости, подчиняющихся некоторому распределению вероятностей (различные точки независимы). Для некоторых распределений математическое ожидание числа вершин выпуклой оболочки есть 0(га1 е) для некоторой константы е > 0 (здесь га - число точек). Такие распределения мы будем называть распределениями с малой оболочкой (sparse-hulled distributions). Вот примеры таких распределений: Точки равномерно распределены внутри круга единичного радиуса. Выпуклая оболочка имеет в среднем 0(га1/,э) вершин. Точки равномерно распределены внутри фиксированного выпуклого многоугольника. Выпуклая оболочка содержит в среднем O(lgra) вершин. (Константа зависит от числа вершин многоугольника.) Точки подчинены двумерному нормальному распределению. Выпуклая оболочка содержит в среднем Q(\/lg га) вершин. a.Даны два выпуклых многоугольника (возможно, пересекающихся) с п\ и п2 вершин. Придумайте способ построить выпуклую оболочку всех rai+ra2 вершин за время 0(щ-\-П2). (Многоугольники могут пересекаться.) b.Постройте алгоритм, который отыскивает выпуклую оболочку га независимых точек, подчинённых некоторому распределению с малой оболочкой. Математическое ожидание времени работы т алгоритма должно быть О (га). (Указание. Рекурсивно ищем выпуклую оболочку для двух половин множества, а затем соединяем эти выпуклые оболочки в одну.) Замечания В этой главе мы лишь слегка коснулись задач вычислительной геометрии. Книги по вычислительной геометрии написали Препа- |
Среды: 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 | ||