|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[288] тем самым ответ алгоритма (который заведомо не меньше этого z) будет не меньше (1 - е/п)пу. Нам осталость только убедиться, что (1 - е/п)п (1-е). В саом деле, продифферецировав (1-е/и)и по и, убеждаемся, что это выражение возрастает как функция от и; остаются сравнить его значения при и = 1 и и = га. [Это легко понять и без производных: в убывающей последоваль-ности 1,(1 -5), (1-5)2,..., (1-5)" второй член меньше первого (на 8), третий член меньше второго и т.п. Разности между соседними членами убывают, так как составляют фиксированную долю от уменьшаемого. Поэтому общее изменение при переходе от первого члена к последнему не превосходит п8 и (1 - 8)п 1 - п8. Остаётся положить 8 = е/п.] Теперь оценим время работы нашего алгоритма, для чего надо оценить длину списков Li. После сокращения списка соседние его элементы отличаются как минимум в 1/(1 - е/п) раз. При этом максимальный оставляемый в списке элемент не превосходит t, а второй элемент (первый равен нулю) не меньше 1. Отсюда видно, что число элементов в списке не больше 1°6i/(Wn)t + 2=ln(11°tg/n)+2 £ (Мы использовали неравенство (2.10) на последнем шаге.) Эта оценка полиномиальна, так как lg 4 примерно равно числу битов в записи числа t. Осталось заметить, что время работы алгоритма Approx-Subset-Sum ограничивается полиномом от га и от длины списков Li. Упражнения 37.4-1 Докажите равенство (37.11). 37.4-2 Докажите неравенства (37.12) и (37.13). 37.4-3 Как следует изменить схему приближения, описанную в этом разделе, если мы рассматриваем все суммы, составленные из элементов заданного списка, не меньшие заданного числа t, и хотим найти минимальную из них (с заданной относительной ошибкой)? Задачи 37-1 Упаковка в язики Имеется га объектов, причём г-ый объект имеет размер s8-, где 0 < s4- < 1. Мы хотим упаковать их в минимальное число ящиков единичного размера (каждый из которых может вместить любое число объектов, суммарный размер которых не превосходит 1). a.Доказите, что задача нахождения минимально необходимого числа ящиков является NP-трудной. (Указание. Сведите к ней задачу о сумме подмножества.) b.Пусть SI 2~}jLi si - суммарный размер всех предметов. Покажите, что необходимо по крайней мере \S] ящиков. Эвристика первого подходящего предлагает рассматривать все предметы по очереди и помещать их в первый (в некотором порядке) ящик, в который они ещё помещаются. c.Покажите, что при таком подходе не более чем один ящик будет заполнен менее чем наполовину. d.Докажите, что исло использованных ящиков при этом будет не более \2S]. e.Докажите, что эта эвристика даёт решение, не более чем в 2 раза худшее оптимального. f.Придумать эффективную реализацию этого подхода, и оценить время работы получившегося алгоритма. 37-2 Размер максимальной клини и приближённые алгоритмы Пусть G = (V, Е) - неориентированный граф. Определим его к-ую степенькак неориентированный граф (Vk\ Е), вер- шинами которого являются последовательности из к элементов V, причём две вершины (v\,v2,... ,Vk) и (w\, w2, , Wk) соединены ребром в том и только том случае, если при любом г вершины V{ и Wi соединены ребром в V или совпадают. a.Докажите, что размер максимальной клики в графе является &-ой степенью размера максимальной клики в графе G. b.Покажите, что если бы для задачи о клике существовал приближенный алгоритм с ошибкой не более в С раз (для некоторого фиксированного С), то для этой задачи существовала бы полностью полиномиальная схема приближения. [Как установлено в работе S. Arora and S. Safra, Approximating clique is NP-complete, in Proc. of the 33rd IEEE Symp. on Foundation of Computer Science, 1992, такое возможно, лишь если P=NP. Этот результат (и родственные ему) является одним из самых замечательных достижений в теории сложности вычислений за последнее десятилетие.] 37-3 Задача о покрытии множествами с весами Рассмотрим обощение задачи в покрытии множествами, в котором каждому множеству из семейства Т приписан некоторый вес. При этом весом покрытия считается суммарный вес входящих в него множеств, и мы хотим найти покрытие наименьшего веса. Покажите, что имеется естественное обобщение рассмотренного нами жадного алгоритма, которое позволяет решить эту задачу с ошибкой не более чем в Н(d) раз, где d - максимальный размер множеств покрытия. Замечания Литература, посвященная приближённым алгоритмам, обширна; для начала можно прочесть книгу Гэри и Джонсона [79]. Другое превосходное введение в предмет - Пападимитриу и Стайглиц [154]. Лоулер, Ленстра, Ринной-Кан и Шмойс [133] подробно рассматривают задачу о коммивояжёре. Согласно Пападимитриу и Стаглицу, алгоритм Approx-Vertex-Cover был предложен Гаврилом (F. Gavril) и Яннакаки-сом (М. Yannakakis). Алгоритм Approx-TSP-Tour приводится в замечательной работе Розенкранца, Стирна и Льюиса [170]. Теорема 37.3 заимствована из работы Сахни и Гонсалеса [172]. Анализ жадной эвристики для задачи о покрытии множествами представляет собой упрощённый вариант более общих рассуждений из работы Хватала [42]; само утверждение имеется в работах Джонсона [113] и Ловаса [141]. Алгоритм Approx-Subset-Sum и его анализ родственны алгоритмам для задачи о рюкзаке и сумме подмножества, рассмотренным в работе Ибарры и Кима [111]. |
Среды: 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 | ||