Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[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) Рекурсия развёрнута, (с) Показано внутреннее строение сливающих сетей. Указаны глубины проводов и значения на них (для одного из возможных вариантов входов).



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]