|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[216] нии любой вершины из V \ V оно перестаёт быть независимым. Не следует смешивать задачу нахождения такого множества с гораздо более сложной задачей нахождения независимого множества наибольшей мощности (каковое, конечно, является максимальным - но обратное неверно). Для произвольного графа последняя задача является NP-полной (см. главу 36, задача 36.1). Для га-элементного списка независимое множество максимальной мощности состоит из [га/2] объектов - достаточно взять объекты через один, начиная с первого. Это множество, как и соответствующая 2-раскраска, может быть найде)о с помощью параллельной обработки префиксов за время О (lgra). Заметьте, что в случае списка любое максимальное множество вершин содержит не меньше га/3 элементов. Действительно, из любых трёх подряд идущих объектов хотя бы один должен входить в множество - иначе средний из этих трёх можно добавить, сохранив независимость. Ниже будет показано, как за время 0(1) построить максимальное независимое множество по 0(1)-раскраске. 30.5.2. Вычисление 6-раскраски Укажем алгоритм, находящий 6-раскраску списка. Мы считаем, что за каждым элементом х списка закреплён процессор процессор, номер которого (известный процессору) есть Р(х) G {0,1,... , га - !}• Алгоритм последовательно строит раскраски Со, С\,... , Ст, постепенно уменьшая число цветов. Начальная раскраска Со является га-раскраской, а Ст - 6-раскраской. На к-ош шаге по раскраске Ск вычисляется раскраска Ck+i- Число шагов т есть 0(lg* га). Начальная раскраска Со тривиальна: Со[ж] = Р(х) (цвет вершины есть номер соответствующего ей процессора). Поскольку номера процессоров различны, это отображение действительно является раскраской. (Заметьте, что каждый цвет кодируется [lgra] битами и может храниться в памяти, занимая не слишком много места.) Опишем теперь процесс построения раскраски Ck+i по Ск (см. рис. 30.11). Мы считаем, что каждый цвет кодируется битовой строкой фиксированной (для данной раскраски) длины. Переход от Ck к Cfc+i уменьшает эту длину. Итак, пусть цвета раскраски С\ записываются г битами и соседние объекты х и next[x] имеют цвета С[ж] = а и С[гаеж£[г]] = Ь, где а = (ar i, ar-2j • • • , ао), b = (br i, frr-2j • • • , bo). Цвета эти различны, поэтому щ ф bi для некоторого г от 0 до г - 1. Мы объявим пару (г, щ) цветом элемента х в новой раскраске (закодировав её последовательностью битов). Цветом последнего элемента в новой Рис. 30.11 30.11. Построение 6-раскраски и соответствующего максимального независимого множества. Алгоритм использует п процессоров и работает за время 0(lg* п). Вначале список из п = 20 объектов раскрашен в 20 цветов (что требует пяти битов). За два шага эта раскраска сводится к 6-раскраске. Элементы MIS показаны чёрным цветом. раскраске мы будем считать пару (0,ао)> если (ar i, ar-2j • • • , ао) было его цветом в старой раскраске. Остаётся понять, почему в новой раскраске цвета соседних вершин будут различны и сколько битов нужно для кодирования её цветов. Начнём с первого; рассмотрим два соседних элемента ж и у = пежж] в нашем списке. Раньше они имели цвета а = (ar i, аг 2, • • • , ао), Ь = (br i, Ьг 2,... , Ьо)> которые различались в бите г, и новый цвет ж есть пара (г,аг-), причём аг- ф Ь{. Пусть новый цвет у есть пара (j, bj). Видно, что пары эти различны: если различны их первые члены, то и доказывать нечего, если же первые члены совпадают [г = j), то различны вторые bj равно bi и не равно аг-. Теперь о количестве битов: если на к-ом шаге цвета записывались г битами, то на (к А- 1)-ом шаге они будут записываться всего [lg г] + 1 битами. Если г 4, то при этом число битов уменьшается. Если же г = 3, то два цвета могут различаться в разрядах 0, 1 или 2, поэтому на следующем шаге номер любого цвета будет начинаться с (00), (01) или (10) и оканчиваться нулём либо единицей. При этом из восьми цветов получается не более шести, так что мы приходит к 6-раскраске. Если предположить, что операция поиска может найти нужный индекс и совершить левый сдвиг за время 0(1), то каждый шаг занимает время 0(1). Алгоритм можно реализовать на EREW-машине, так как каждому процессору необходим доступ лишь к двум объектам - ж и next[x]. Покажем теперь, что число шагов до получения 6-раскраски составляет 0(lg* гг). Напомним, что lg* п определялось как число применений к п функции lg, после которых результат будет не больше 1. Более точно, если через lgW п обозначить г-кратное применение логарифма, то lg* п = min г 0 : lgW п <i 1 j В нашем случае число битов на каждом шаге тоже логарифмируется, но затем округляется (с избытком) и увеличивается на 1. Проверим, что всё равно число шагов есть 0(lg* п). Пусть г\ - число битов, которыми записываются цвета перед г-м шагом. Мы докажем по индукции, что гг- [lg та] + 2 при [lgW гг] 2 Изначально r\ [lg гг]. Пусть утверждение верно для [г - 1)-го шага. Поскольку гг- = [~lgr8 i] + 1, имеем г,- = rig-il +1 rig(rig(, 1) Ч + 2)1 +1 rig(ig(,-1) п + 3)1 +1 \Ы2- п)] + 1= rig(lg( 1) п) + 1] + 1 = [lgW га] + 2 Четвёртое неравенство получается так: если [lg га] 2, то "lg(8 1) га~ так что увеличение на 3 можно заменить умножением на 2. Поэтому для т = lg* га - 1 имеем rm ~lg(m 1)] + 24, так как lg(m+1) в 1 и lg(m) п 2 по определению lg* га. Значит, rm+i 3, и ещё через шаг процесс закончится. Таким образом, общее количество шагов составляет 0(lg* га). 30.5.3. Получение максимального независимого множества из 6-раскраски Пусть дан список из га объектов и его раскраска С в с цветов. Опишем EREW-алгоритм, который позволяет найти по этой раскраске максимальное независимое множество (MIS) за время 0(c). В частности, зная 6-раскраску, можно найти максимальное независимое множество за время 0(1). Идея алгоритма показана на рис. 30.11 (шесть правых колонок). Для каждого объекта х соответствующий процессор хранит бит alive[x]. При этом alive[x] = TRUE означает, что элемент х ещё имеет шанс попасть в MIS. Вначале alive[x] = TRUE для всех объектов х. Алгоритм на каждом шаге рассматривает элементы одного цвета. Пусть текущий цвет равен г. Каждый процессор проверяет для своего элемента х условия С[х] = г и alive[x] = TRUE. Если оба условия выполнены, то элемент х включается в MIS, а alive-бнты соседних с ним элементов (следующего и предыдущего) устанавливаются равными FALSE (эти элементы нельзя включать в MIS). После с шагов каждый объект либо включён в MIS, либо имеет alive-бнт, равный FALSE. Покажем, что полученное множество действительно является независимым и максимальным. Предположим, что в множество попали два соседних объекта. В силу свойств раскраски они имеют разные цвета, поэтому включены на разных шагах. Но включённый первым объект должен был установить alive-бнт второго в положение FALSE, и второй элемент уже не мог быть включён. Максимальность множества очевидна. Действительно, если элемент х не включён в множество, то alive[x] = FALSE, поэтому в множество включён один из его соседей. Поэтому при добавлении элемента х множество перестанет быть независимым. Каждый шаг алгоритма требует времени 0(1). Алгоритм может быть реализован на EREW-машине, поскольку каждый процессор обращается только к трём объектам - своему и его соседям. Вместе |
Среды: 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 | ||