(1,7)

(1,5)

(1,5)

(1,4)

Рис. 54. Отделение четырех наибольших от четырех наименьших. (Числа над линиями используются в доказательстве теоремы А.)

Рис. 55. Иная интерпретация сети, изображенной на рис. 54.

Теперь дадим другую интерпретацию функционирования сети (рис. 55): предположим, что на всех входных прямых содержится нуль и каждый "компаратор" помещает теперь на верхнюю линию меньший из своих входов, а на нижнюю линию - больший вход плюс единицу. Получающиеся числа (mi,тг,... ,т„) обладают свойством

2"- > h (20)

в любом месте сети, так как это свойство первоначально справедливо и сохраняется каждым компаратором в силу (19). Кроме того, окончательное значение mi -Ьтг -Ь • • 4- т„ равно общему числу компараторов в сети, так как каждый компаратор добавляет к этой сумме единицу.

Если сеть выбирает наименьшие t чисел, то п - t из чисел li больше или равны t+1; следовательно, п - t из чисел mj должны быть > lg(t -Ь 1) . I

Нижняя оценка в теореме А оказывается точной, если t = 1 или t = 2 (см. упр. 19). В табл. 1 даны значения Ut{n), Щп) и Wt{n) для небольших tun. Эндрю Яо (Andrew Yao) [Ph. D. thesis, U. of IlUnois (1975)] исследовал асимптотическое поведение Ut{n) при фиксированном t и показал, что {/з(п) = 2п + \gn + 0{1) и Ut{n) - n[lg(t + 1)] + 0((logn)l-8*J) при n -> оо; минимальное время задержки равно Ign-b [IgtJ lglgn4-0(log log logn). В работе N. Pippenger, SICOMP 20 (1991), 878-887, доказано при помощи неконструктивного метода, что для любого б > О существует сеть выбора с Un/a]() £ (2 + e)nlgn, если только п достаточно велико (в зависимости от б).

Таблица 1

СРАВНЕНИЯ, НЕОБХОДИМЫЕ ДЛЯ СЕТЕЙ ВЫБОРА (Utin), Vt{n), Wt{n))

УПРАЖНЕНИЯ (часть 1)

Далее в нескольких упражнениях теория сетей сортировки рассматривается более детально, поэтому будет удобно ввести некоторые обозначения. Вместо модуля сравнения-обмена будем писать [i-j]- Сеть с п входами и г модулями компараторов обозначим через [ii -.ji] [h: ja]... [ir :Jt], где каждое из i и j меньше или равно п; для краткости будем называть ее п-сетью. Сеть называется стандартной, если г, < для 1 < q < г. Так, например, на рис. 44 приведена стандартная 4-сеть, обозначенная последовательностью компараторов [1:2][3:4][1:3][2:4][2:3].

Наши соглашения в тексте о графическом представлении диаграмм сетей позволяют рисовать только стандартные сети; все компараторы изображаются прямой линией от г к j, где г < j. Чтобы нарисовать нестандартную сеть, можно использовать стрелку от г к j, указывающую, что большее число направляется к острию стрелки. Например, на рис. 56 изображена нестандартная сеть для 16 элементов с компараторами [1;2][4:3][5:6][8:7] и т. д. В упр. 11 доказывается, что это сеть сортировки.

Стадия 1 Стадия 2

Стадия 3

Стадия 4

Рис. 56. Нестандартная сеть, основанная на битонной сортировке.

Если X = {xi,...,Xn) - это п-мерный вектор, а а - п-сеть, то обозначим через ха вектор чисел {{ха)\,..., {ха)п), порожденных сетью. Положим также для краткости а V 6 = тах(а,Ь), а АЬ = mm(a,b), а = 1 - а; тогда {x[i:j])i = Xi А xj, {x[i:j])j = xtV xj и

ix[i:j])k = Хк, когда i ф к ф j. Будем говорить, что а является сетью сортировки, если {xa)i < {xa)i+i для всех х и для 1 < г < п.

Символ е() обозначает вектор, в позиции i которого находится 1, а в остальных позициях - 0; таким образом, (e)j = 6ij. Символ Dn обозначает множество всех 2" п-мерных векторов из О и 1, а Рп - множество всех п! векторов, являющихся перестановками {1,2,..., п}. Мы будем использовать обозначения х t\y ж хУ у для векторов (хх 1\ух, - ,Хп 1\Уп) и (хх у ух, ,ХпУ Уп) и будем писать х < у, если х, < уг при всех г. Таким образом, х < у тогда и только тогда, когда х У у = у, либо тогда и только тогда, когда X А У = X. Если х и у лежат в Dn, то будем говорить, что х покрывает у, если я; = (у V е()) ф У при некотором г. Наконец, для всех х в Dn пусть и{х) будет числом единиц в я:, а ((х) - числом нулей; таким образом, и{х) + {х) = п.

1. [20] Нарисуйте диаграмму сети четно-нечетного слияния для m = 3 и п = 5.

2. [22] Покажите, что алгоритму сортировки В. Пратта (см. упр. 5.2.1-30) соответствует сеть сортировки п элементов, имеющая приблизительно (logj n)(log3 n) уровней задержки. Нарисуйте такую сеть для п = 12.

3. [М20] (К. Э. Бэтчер (К. Е. Batcher).) Найдите простое соотношение между С(т, m-1) и С(т, т).

► 4. [М23] Докажите, что Г(6) = 5.

5. [М1б] Докажите, что выражение (13) действительно определяет время задержки для сети сортировки, описанной соотношениями (10).

6. [28] Пусть Г(п) - минимальное число стадий, требуемых для сортировки п различных чисел посредством одновременного выполнения непересекающихся сравнений (без соблюдения сетевого ограничения); каждое такое множество сравнений может быть представлено узлом, содержащим множество пар {ix: Ji, га :j2,..., «V :>}, где все ix,jx,i2,J2, ,ir,> различны; от этого узла отходит вниз 2 ветвей, соответствующих случаям

(А",! < Kjj, Ki < Kj2, ..., Ki,. < Kj,.),

{Ki, > Kj,, K,2 <Kj,..., Ki,. < Kj,.) и т. д.

Докажите, что Г(5) = Г(6) = 5.

7. [25] Покажите, что если три последних компаратора сети для п = 10 на рис. 49 заменить "слабой" последовательностью [5:6] [4: 5] [6:7], то сеть по-прежнему будет выполнять сортировку.

8. [М20] Докажите, что М{тх+т2,пх+П2) > М{тх,пх) + М{т2,П2) + тахп{тх,П2) при тх,т2, пх,П2 > 0.

9. [М25] (Р. У. Флойд (R. W. Floyd).) Докажите, что М(3,3) = 6, М(4,4) = 9, М(5,5) = 13.

10. [М22] Докажите, что битонный сортировщик Бэтчера, определенный в разделе, который предшествует (15), действительно работает. [Указание. Достаточно доказать, что будут сортироваться все последовательности, состоящие из к единиц, за которыми следуют I нулей, за которыми следуют п - к - I единиц.]

11. [М23] Докажите, что битонный сортировщик Бэтчера порядка 2 будет сортировать не только последовательности (го, Zx,..., a-i), для которых «о > • • • > г*: < • • • < «з-ь но и все последовательности, для которых zo < • < Zk > > 231 i. [Как следствие этого сеть на рис. 56 будет сортировать 16 элементов, так как каждая стадия состоит из битонных сортировщиков или обращенных битонных сортировщиков, применяемых к последовательностям, которые были рассортированы в противоположных направлениях.]