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


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




[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 га). Чуть поз-



[стр.Начало] [стр.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]