|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[197] Глубина D(n) сети BlTONlc-SoRTER[ra] даётся соотношением ГО,если га = 1, {> \ D(n/2) + l, если га = 2кик 1. из которого видно, что D(n) = lgra. Мы видим, что битонические последовательности нулей и единиц сортируются правильно, откуда следует (правило нуля и единицы для битонических последовательностей, упражнение 28.3-6), что и любые битонические последовательности сортируются правильно. Упражнения 28.3-1 Сколько всего существует раличных битонических последовательностей нулей и единиц длины га? 28.3-2 Докажите, что сеть BlTONlc-SoRTER[ra] содержит O(ralgra) компараторов (напомним, что га есть степень двойки). 28.3-3 Постройте битонический сортировщик с га входами глубины O(lgra) для случая, когда га не является степенью двойки. 28.3-4 Полуочиститель получает на вход произвольную битоническую последовательность. Докажите, что верхняя и нижняя половины выходной последовательности - битонические, а любой элемент верхней половины меньше любого элемента нижней (или равен ему). 28.3-5 Даны две последовательности нулей и единиц причем любой элемент первой меньше любого элемента второй или равен ему. Докажите, что хотя бы одна из последовательностей - чистая. 28.3-6 Докажите правило нуля и единицы для битонических последовательностей: если сеть компараторов упорядочивает все битонические последовательности нулей и единиц, то эта сеть упорядочивает любую битоническую последовательность. 28.4. Сливающая сеть Сливающей сетью (merging network) мы называем сеть компараторов, соединяющая две упорядоченые последовательности (половины входной последовательности) в одну упорядоченную последовательность. Такая сеть (мы назовём её MERGER[ra]) легко получается модификацией сети BlTONlc-SoRTER[ra]. Идея проста: для слияния двух упорядоченных последовательностей припишем (в обратном порядке) вторую последовательность Рис. 28.9 Входная часть сети Merger[8] (а) отличается от сети half-Cleaner[8] (b) тем, что нижние 4 провода перевёрнуты, (а) Входная часть сети merger преобразует две возрастающие последовательности (01,02,... ,anj2) и (an/2+i i an/2+21 • • • i ап) в две битонические последовательности (bi, Ьг, • • • ,Ь„/2) и (bn/2+i! b„/2+2! • • • in}- (b) Тот же процесс в обозначениях полуочистителя: битоническая входная последовательность (01,02,... , an/2i an/2+i, • • • преобразуется в две битонические последовательности (bi, Ьг, - - - ,Ь„/2) и {Ьп/2+l ! Ьп/2 + 2 ! • • • jbn}- Рис. 28.10 Сеть MERGER[n] соединяет две отсортированные последовательности в одну. Она получается из сети BlTONIC-SoRTER модификацией первого каскада: теперь сравниваются г-ые с начала и конца элементы, (а) Общая структура сети: первый каскад, затем два экземпляра сети BlTONIC-SoRTER[n/2]. (b) Полная схема сети (серые прямоугольники - структурные элементы, на рёбрах показаны значения для одного из возможных входов). к концу первой. При этом получится битоническая последовательность, которую уже можно упорядочить с помощью битоническо-го сортировщика. Например, для объединения X = 00000111 и Y = 00001111 мы приписываем к X перевёрнутую последовательность YR = 11110000 и получаем битоническую последовательность XYR = 0000011111110000. Осталось применить к XYR битонический сортировщик. Следуя этому плану, для построения сети MERGER[ra], сливающей последовательности (а\,... , ап/2) и (an/2+i> • • • > ап), следует так перестроить первый полуочиститель сети BlTONlc-SoRTER[ra], чтобы добиться эффекта «переворачивания» второй последовательности. В обычном полуочистителе вход аг- сравнивается со входом an/2+ii (при г = 1,2,... , п/2), поэтому теперь мы будем аг- со входом ага г 1. На рис. 28.10 показан перестроенный полуочиститель в сравнении с обычным - разница в том, что провода в нижней его половине переставлены в обратном порядке. При этом верхняя и нижняя половины выходов по-прежнему обладают свойствами, указанными в лемме 28.3 (битоническая последовательность, записанная в обратном порядке, остаётся битонической). Для завершения слияния остаётся упорядочить обе половины при помощи двух копий сети BlTONlc-SoRTER[n]. Полученая сеть Merger[k] показана на рис. 28.11. Её глубина такая же, как у сети BiTONic-SoRTER[ra], то есть lgra. Упражнения 28.4-1 Докажите следующий вариант правила нуля и единицы для сливающих сетей: если сеть компараторов правильно сливает любые две монотонные последовательности нулей и единиц, то она правильно сливает любые монотонные числовые последовательности. 28.4-2 Сколько тестовых последовательностей нулей и единиц необ- ходимо, чтобы проверить, что сеть компараторов действительно является сливающей? 28.4-3 Докажите, что любая сеть компараторов, умеющая правильно сливать один элемент (а\) с упорядоченной последовательностью длины п-1 (<22,аз,... ,ап) в упорядоченную последовательность длины п, имеет глубину как минимум lgra. 28.4-4* Пусть дана сливающая сеть со входами ai,...,an, которая сливает упорядоченные последовательности (а\, а3,... , ara-i) и (<22, й4, ... , ап) (предполагаем, что га - степень двойки). Покажите, что такая сеть содержит fi(ralgra) компараторов. Чем интересна эта нижняя оценка? (Указание. Разбейте множество компараторов на три части.) [ Что это за части? Какое значение вообще имеет порядок входов? Как решается этоа задача? ] 28.4-5* Докажите, что любая сеть, сливающая две упорядоченные последовательности длины га/2 в одну (разрешается распределить входы между первой и второй сливаемыми подпоследовательностями произвольным образом) содержит О (га lgra) компараторов. 28.5. Сортирующая сеть Теперь всё готово для построения сортирующей сети SoRTER[ra]8, реализующей алгоритм сортировки слиянием из раздела 1.3.1. Устройство сети показано на рисунке 28.12. Сеть SoRTER[ra] строится рекурсивно: две половины входной последовательности упорядочиваются сетями SoRTER[ra/2], а затем соединяются при помощи сети merger[ra]. В качестве Merger[2] используется компаратор. Схема построения показана на рис. 28.12 (а), на рис. 28.12 (Ь) она развёрнута, а на рис. 28.12 (с) показано внутреннее устройство сливающих сетей. Таким образом, сеть SoRTER[ra] состоит из lg га каскадов. Первый из них содержит га/2 копий сети Merger[2] параллельно сливающих пары одноэлементных последовательностей. Второй уровень состоит из га/4 экземпляров сети Merger[4], которые сливают пары полученых на первом уровне двухэлементных последовательностей, и т. д. На к-ом уровне (при к = 1,2,... , lgra) имеется п/2к Рис. 28.11 Сеть SoRTER[n] строится рекурсиво из сливающих сетей, (а) Рекурсивное описание сети SoRTER[n]. (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 | ||