|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[215] число удаляемых? Для этого нужно, чтобы на этапе 2 он был помечен (вероятность 1/2) и чтобы чтобы объект next[i] не был помечен (это независимое событие, имеющее вероятность не меньше 1/2 - лишь один процессор может пометить next[i], и с вероятностью 1/2 он бездействует). Таким образом, вероятность удаления объекта г нее меньше 1/4. Таким образом, ситуацию можно описать так. Имеется га/lgra групп по lg га элементов в каждой (для простоты мы будем считать, что элементы делятся на группы без остатка). На каждом шаге число элементов в группе может уменьшится на 1 или остаться прежним, при этом вероятность уменьшения не менее 1/4. Уменьшения в разных группах на одном шаге могут не быть независимыми, но уменьшения на разных шагах в одной группе независимы. Нам надо доказать, что математическое ожидание времени полного исчезновения всех групп есть О (lg га). Анализа для одной группы тут недостаточно, поскольку даже один долго работающий процессор уже увеличивает общее время работы. Мы покажем, что с вероятностью не менее 1 - 1/га список станет пустым через время с lgra для некоторой константы с. Полное доказательство оценки в (lgra) для математического ожидания времени работы оставляется читателю (упр. 30.4-4 и 30.4-5). Поскольку нас интересует верхняя оценка времени, когда список станет пустым, будем считать, что вероятность уменьшения данной группы на каждом шаге в точности равна 1/4 (хотя на самом деле она может быть больше); формальное обоснование законности такого допущения даётся в упр. 6.4-8 и 6.4-9. Рассмотрим ситуацию для одной фиксированной группы. Взяв какое-то значение с, посмотрим на вероятность того, что среди с lgra независимых испытаний с вероятностью успеха 1/4 в каждом будет меньше lg га успехов. (Это и будет вероятностью того, что группа останется непустой после с lgra испытаний.) Обозначив число успехов через X, оценим вероятность события {X < lgra} с помощью следствия 6.3: Р{А < lgra} <С СХптУЫп-Ып ()Sn(3/4)(c-1)1 = (ec(3/4)c-1)lgn (1/4) (последнее неравенство верно при с 20; второе неравенство следует из (6.9)). Таким образом, вероятность того, что через с lgra шагов не все объекты данного процессора исключены, не превышает 1/га2. Всего имеется га/lgra процессоров, поэтому вероятность «неудачи» (остаются неудалённые) одного процессора надо ещё умножить на га/lgra, (неравенство Буля, 6.22) получается не больше га 1 1 ]---2 " lg га пг га Поэтому с вероятностью не менее 1 - 1/га алгоритм закончит работу за время 0(lg га). Константа 20 не отражает реального быстродействия алгоритма - на самом деле наша оценки довольно грубые, и среднее время значительно меньше. 30.4.4. Упражнения 30.4-1. Нарисуйте пример, показывающий, почему нельзя исключать из списка два соседних объекта. 30.4-2*. Вероятностный алгоритм можно слегка изменить так, чтобы время работы в худшем случае составляло О (га). Как? Докажите, что математическое ожидание времени работы модифицированного алгоритма равно О (lgra). 30.4-3*. Измените вероятностный алгоритм так, чтобы он использовал 0(п/р) памяти (в расчёте на один процессор) независимо от глубины рекурсии. 30.4-4*. Докажите, что для любого к 1 найдётся такая константа с, что время работы алгоритма меньше с lgra с вероятностью 1 - 1/пк или больше. Как зависит константа с от к? 30.4-5*. Докажите, используя предыдущее упражнение, что математическое ожидание времени работы вероятностного алгоритма есть 0(lgга). 30.5. Нарушение симметрии (детерминированный алгоритм) Рассмотрим ситуацию, когда два процессора одновременно хотят получить доступ к объекту. При отсутствии механизма одновременного доступа к памяти один из процессоров должен получить доступ первым - но какой? Задача выбора ровно одного из двух процессоров является частным случаем задачи о нарушении симметрии (symmetry breaking). Именно с такой задачей столкнулись Чичиков и Манилов, уступая друг другу дорогу. Подобные задачи постоянно возникают при реализации параллельных алгоритмов. Для решения такой задачи можно просто бросать монетку (использовать случайные числа). Например, в случае двух процессоров каждый из них бросает монетку, и доступ получает тот, у кого орёл (если два орла или две решки - бросают ещё раз). При этом симметрия будет нарушена за время 0(1) (имеется в виду математическое ожидание, см. упр. 30.5-1). Использование случайности часто оказывается полезным - мы видели, что вероятностном алгоритме обработки префиксов (раздел 30.4) использование случайности позволяет выбрать достаточ- но много объектов, гарантировать, что соседние не выбраны и при этом правило выбора локально (зависит только от ситуации у двух соседних объектов). В этом разделе рассматривается детерминированный метод нарушения симметрии. Он основан не на бросании монеты, а на использовании номеров процессоров (или адресов в памяти). Например, в случае двух процессоров можно предоставить доступ процессору с меньшим номером. При этом задача решается за постоянное время. Мы используем ту же идею для решения более сложной задачи: как выделить (достаточно большую) часть объектов списка, если нельзя выделять два соседних объекта. Для этой задачи будет построен параллельный алгоритм (в EREW-модели), время работы которого составляет 0(lg* п), если номера процессоров берутся из промежутка 1..п. Поскольку lg* п 5 при п 265536, на практике время работы этого алгоритма можно считать постоянным (см. стр. 00). Алгоритм состоит из двух частей. Сначала за время 0(lg* п) мы находим «6-раскраску» списка. Затем (за время 0(1)) мы получаем из неё «максимальное независимое подмножество»списка; оно содержит не менее трети объектов списка и не содержит соседних объектов. 30.5.1. Раскраски и максимальные независимые множества Раскраской (coloring) неориентированного графа G = (V, Е) называется отображение С : V -> N, для которого С (и) ф С (у) при (и, v) G Е. Если называть С [у) цветом вершины v, то можно сказать, что концы любого ребра должны иметь разные цвета. Мы ищем 6-раскраску списка, то есть хотим поставить в соответствие каждой вершине некоторый цвет из множества {0,1,2,3,4,5}, причём так, что соседние в списке вершины имеют разные цвета. Такая раскраска существует; более того, ясно, что достаточно двух цветов. В самом деле, можно покрасить все чётные вершины в один цвет, а все нечётные - в другой. Но находясь в середине списка, не так просто понять, чётная вершина или нечётная - для этого нужно отсчитать её номер от начала списка, что можно сделать за время O(lgra) (раздел 30.1). Разрешив больше цветов (как мы увидим, достаточно 6), раскраску можно построить быстрее - за время 0(lg*ra), при этом алгоритм остаётся детерминированным. Множество V С V вершин графа G = (V, Е) назовём независимым множеством (independent set), если никакие две вершины из V не соединены ребром. Независимое множество V называется максимальным (maximal independent set, MIS), если при добавле- |
Среды: 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 | ||