|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[198] экземпляров сети MERGER[2fc], сливающих по две упорядоченные последовательности длины 2к~г. Индуктивное построение гарантирует, что сеть правильно упорядочивает последовательности нулей и единиц. Из правила нуля и единицы (теорема 28.2) следует правильность работы сети на произвольных числовых последовательностях. Глубина D(n) сети SoRTER[ra] равна сумме глубин сетей SoRTER[ra/2] и Merger[k] (две копии сети SoRTER[ra/2] работают параллельно). Глубина сети MERGER[ra] равна lgra, так что рекуррентная формула для D(n) такова: О, если га = 1, D(n/2) + lg га, если га = 2к и к 1. Из неё следует, что D(n) = 0(lg2 га. Таким образом, можно сказать, что параллельный алгоритм сортировки может упорядочить га чисел за время 0(lg2ra), используя сортирующие сети как модель параллельных вычислений. Упражнения 28.5-1 Сколько компараторов содержит сеть SoRTER[ra]? 28.5-2 Покажите, что глубина сети SoRTER[ra] в точности равна lgra(lgra+ 1)/2. (Число га есть степень двойки.) 28.5-3 Рассмотрим компараторы нового типа, получающие на два своих входа упорядоченные последовательности длины к, соединяющие их в одну последовательность и выдающие на верхний выход к меньших чисел, а на нижний - к больших чисел. (Таким образом, значениями на входах и выходах компараторов являются упорядоченные последовательности чисел длины к.) Покажите, что любая сортирующая сеть с га входами и выходами после замены компараторов на компараторы нового типа превращается в устройство, сливающее га упорядоченных последовательностей длины к в упорядоченную последовательности длины пк (разбитую на га частей длины к). 28.5-4 Пусть даны 2га чисел (а\,... , a2ra) и требуется разделить их на га меньших и га больших чисел (внутри этих двух групп порядок может быть любым). Докажите, что это можно сделать с помощью сети глубины 0(1), если известно, что входная последовательность состоит из двух отсортированных половин ai,... ,ап и ап1 + 1, • • • , а2п- 28.5-5* Пусть дана сортирующая сеть с к входами глубины S(k), а также сеть глубины М(к), сливающая две упорядоченные последо- вательности длины к в одну длины 2к. Постройте сеть глубины S(k) +2M(fc), упорядочивающую все последовательности длины га, в которых каждый элемент отстоит не далее чем на к мест от своего правильного положения. 28.5-6* С матрицей размера т X т выполняют такие действия: 1.Все нечетные строки упорядочивают по возрастанию. 2.Все нечетные строки упорядочивают по убыванию. 3.Упорядочить каждый столбец по возрастанию. Как будут отсортированы элементы матрицы после многократных повторений операции 1-3? Сколько повторений потребуется? Задачи 28.1Сортировка транспозициями. Говорят, что сортирующая сеть использует лишь транспозиции (is a transposition network), если каждый её компаратор соединяет две соседние прямые (рис. 28.3) a.Покажите, что любая такая сеть содержит Г2(га2) компараторов. b.Чтобы убедиться в правильности работы такой сети, достаточно проверить, что она правильноо сортирует последовательность (га, га - 1,... , 1). (Указание: Индуктивное рассуждение следует доказательству леммы 28.1) Чётно-нечётная сортирующая сеть (odd-even sorting network) для 8 входов показана на рис. 28.13. В общем случае она содержит га уровней компараторов: для г = 2, 3,.. .га - 1 и d = 1, 2,... , га прямая номер г на глубине d соединена компаратором с прямой номер г+(-iy+d c.Докажите, что действительно получается сортирующая сеть. 28.2Четно-нечетное слияние по Бэтчеру В разделе 28.4 сливающая сеть строилась на основе битонического сортировщика. В этой задаче рассматривается другой способ её построения - чётно-нечетная сливающая сеть (odd-even merging network). Будем считать, что га - степень двойки, и опишем сеть, сливающую две упорядоченые последовательности (ai,...,an) и (ага+1,... , а2п) в одну. Строится она рекурсивно. Возьмём две сети половинного размера и используем их для параллельного слияния двух пар последовательностей длины га/2: последовательность (аь а3 ... , an i) сливается с (ап+1,ап+3 ... , a2n-i), а (а2, а4 • • • ,ап) - с (ап+2, ап+4 ,а2п)- На последнем этапе стоят га компараторов, г-ый из которых сравнивает число на прямой 2г - 1 с числом на прямой 2г. a.Нарисуйте такую сеть для га = 4. b.Используя правило нуля и единицы, докажите правильность работы построенной сети для произвольного га, являющегося сте- пенью двойки. с Каковы размеры и глубина чётно-нечётной сливающей сети с 2га входами? 28.3 Сети коммутаторов Сеть коммутаторов (permutation network) с га входами и га выходами состоит из проводов и переключателей, позволяющих соединять входы с выходами всеми возможными га! способами. На рис. 28.14 (а) показана сеть коммутаторов Р2. Она состоит из единственного коммутатора, который имеет два положение: прямое и перекрёстное. a.Покажите, что если в любой сортирующей сети компараторы заменить на коммутаторы, то получается сеть, реализующая все перестановки: для любой перестановки тг можно установить коммутаторы в такие положения, что вход i соединён с выходом 7Г(г), при всех г = 1,2... , га. На рис. 28.14 (Ь), показана сеть коммутаторов Pg на 8 позиций, составленная из двух сетей Р4 и восьми отдельных коммутаторов. На рисунке сеть реализует перестановку тг = (4,7,3,5,1,6,8,2), при этом верхняя сеть Р4 реализует перестановку (4, 2, 3,1), а нижняя - (2,3,1,4). b.В какое состояние надо перевести коммутаторы и какие перестановки установить в верхней и нижней Рсетях, чтобы сеть Pg реализовала перестановку (5, 3, 4, 6,1, 8, 2, 7)? Пусть га - степень числа 2. Рассмотрим сеть Рп, построенную из двух сетей Рп/2 и отдельных коммутаторов аналогично сети Pg. c.Докажите, что сеть Рп способна реализовать любую перестановку и укажите алгоритм, который за время О (га) (время измеряется обычным образом, для последовательной машины с произвольным доступом) указывает положения коммутаторов и перестановки для подсетей, реализуюжие заданную перестановку для сети Рп. d.Каковы глубина и размер сети Рп1 Найдите общее время, за которое построенный в пункте b алгоритм рассчитает положения коммутаторов, включая коммутаторы для подсетей нижних уровней. e.Покажите, что любая сеть коммутаторов с га входами, реализующая все перестановки, неизбежно реализует какую-то перестановку по крайней мере двумя способами. Замечения Кнут[123] обсуждает свойства сортирующих сетей и их историю. Видимо, их впервые рассмотрели Армстронг (P.N. Armstrong), Нельсон (R.J. Nelson) и Коннор (D.J.OConnor) в 1954 году. В начале 1960-х годов Бэтчер (К.Е. Batcher) придумал сеть, сливающую две числовые последовательности длины га за время О (lgra), используя чётно-нечётное слиние (задача 28.2). Он также показал, как с помощью таких сетей упорядочить га чисел за время 0(lg2 га). Чуть поз- |
Среды: 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 | ||