для некоторой функции /. Подставляя (xi,Хг,2:3,z4) = (х,ж, 1,0), (х,0,ж, 1), (х, 1,0,ж), (1,х,х,0), (1,х,0, х), (0,1,х,х), находим, что такой функции / не существует.

34. Да; доказав это, вы можете взяться за сеть, представленную на рис. 49, при п = 16 (если только вы просто не проверите это на всех двоичных векторах 2", воспользовавшись теоремой Z).

35. В противном случае перестановка, в которой только г и i + 1 находятся не на своих местах, никогда не была бы рассортирована. Пусть Dk - номера компараторов

в стандартной сети сортировки. Тогда Di + 2D2 + Ds > 2(n - 2), поскольку должно существовать два компаратора от {г, г+1} до {г+2, г+3} при 1 < г < п - 3 так же, как [1:2] и [п-1:п]. Аналогично Di +2D2+-+kDk + (к - l)Dk-i + + D2k-i > к{п-к). Эта формула предложена Дж. М. Поллардом (J. М. Pollard). Можно также доказать, что 2Di + D2 > Зп - 4. Если удалить первые компараторы вида [j:j+l] для всех j, то должен существовать, по меньшей мере, еще один компаратор, размещенный в пределах {г, г+1, г+2} при 1 < г < п-2. Аналогично fc£)i+(fc-l)£)2+- • +I>fc > S{k+l){n-k)+k{k-l).

36. (а) Каждое сравнение соседних элементов уменьшает число инверсий на О или 1, а (п, п-1,..., 1) имеет (2) инверсий. (Ь) Пусть а - [р:р+1] и будем рассуждать по индукции по длине а. Если р = г, то j > р + 1, и (х/9)р > (x/9)j, (x/9)p+i > (x/9)j; следовательно, {уР)р > {yP)j и (yf))p+i > {yP)j. Если р = г - 1, то либо (х/9)р, либо (х)р+1 > (x/3)j; следовательно, либо {уР)р, либо {у13)р+\ > {yP)j. Если р = j - 1 или j, рассуждения аналогичны. Для остальных р доказательство тривиально.

Замечание. Если а является сетью сортировки, то - тоже сеть сортировки (в ней компараторы расположены в обратном порядке). Более общий случай и другое доказательство (с) приведены в работе N. G. de Bruijn, Discrete MathemAtics 9 (1974), 333-339; Jndag-ationes JVfatJi. 45 (1983), 125-132. В этой статье докгеано, что примитивная сеть сортирует все перестановки мультимножества {ni • 1,..., Пт т} тогда и только тогда, когда она сортирует единственную перестановку т" ... I. Отношение х < у, определено для перестановок х п у таким образом, что означает существование стандартной сети а, такой, что X = г/а, и называется порядком Брюа; аналогичное отношение, но ограниченное только примитивом а, есть слабый порядок Брюа (см. ответ к упр. 5.2.1-44).

37. Достаточно показать, что если заменить каждый компаратор операцией взаимной перестановки, то получится отражающая сеть (reflection network), преобразующая (xi,..., Xn) в (xn,... ,xi). Но при такой интерпретации нетрудно проследить путь Xk. Обратите внимание на то, что перестановка тг = (1 2)(3 4)... (2п-1 2п)(2 3)(4 5)... (2п-2 2п-1) = (13 5 ... 2п-1 2п 2п-2 ... 2) удовлетворяет условию тг" = (1 2п)(2 2п-1)...(п-1 тг). Четно-нечетная сортировка с транспозициями была вскользь упомянута X. Сьювордом (И. Seward) в 1954 году; она была проанализирована в работах А. Grasselli, IRE Tr&ns. ЕС-11 (1962), 483, и Kautz, Levitt, Waksman, IEEE Trans. C-17 (1968), 443-451. Свойство отражения такой сети было придумано значительно раньше Г. Э. Дьюдени (Н. Е. Dudeney) в одной из его головоломок [см. Amusements in Mathematics (1917), 193].

38. Вставьте элементы ii, In в первоначально пустую диаграмму, воспользовавшись алгоритмом 5.1.41, но выполнив одно весьма существенное изменение: установите Pij •<- х, на шаге 13 только в том случае, если х; ф Ру 1). Можно доказать, что х; будет равно Р;у 1) на этом шаге, только если Xi + 1 = Pij, когда входы ii .. .ijv определяют примитивную сеть сортировки. (Заключенный в скобки комментарий придется соответственно модифицировать.) После того как ij будет вставлено в Р, установите Qst •<- j, как в теореме 5.1.4А. После N шагов диаграмма Р всегда будет содержать (г, г + 1,..., п - 1) в строке г, в то время как Q будет представлять собой диаграмму, из которой можно восстановить последовательность i\ ... iN, выполняя операции в обратном порядке.

Например, если п = 6, то последовательность n ветствует

Транспозиция Q соответствует дополняющей сети [n-ii :п-ii+l]... [п-глг :п-глг+1]-

[См. А. Lascoux, М. Р. Schiitzenberger, Comptes Rendus Acad. Sci. Paris {Tj 295 (1982), 629-633; R. P. Stanley, Eur. J. Combinatorics 5 (1984), 359-372; P. H. Edelman, C. Greene, Advances in JVfath. 63 (1987), 42-99.] Диаграммы примитивных сетей сортировки также соответствуют организации псевдолиний и других абстракций при двумерном представлении сложности сетей. Более подробно об этом речь идет в работе D. Е. Knuth, Lecture Notes in Сотр. Sci. 606 (1992).

39. Если, например, n = 8, то такая сеть должна включать показанные здесь компараторы. Все другие компараторы не будут задействованы в наборе 10101010. Тогда линии [п/3] .. [2п/3] = 3.. 6 сортируют 4 элемента, как и в упр. 37. (Это упражнение базируется на идее Дэвида Б. Уилсона (David В. Wilson).)

Замечание. Существует взаимно однозначное соответствие между примитивной сетью минимальной длины, которая сортирует данную цепочку битов, и диаграммами Юнга, вид которых ограничен зигзагообразным путем, определенным этой цепочкой битов. Таким образом, из упр. 38 следует взаимно однозначное соответствие между примитивной сетью из ("j) компараторов, которая сортирует (10)", и примитивной сетью из ("2) компараторов, которая сортирует п/2 + 1 произвольных чисел. Если примитивная сеть сортирует цепочку битов l/Q"/ можно сделать следующий вывод: все ее "половинки" состоящие из подсетей с линиями от /г до /г + п/2 включительно, также являются сетями сортировки при 1 < к < п/2. (См. также теорему де Брейна, которая цитируется в ответе к упр. 36.)

40. Это вытекает из применения неравенств относительно конечных членов интересующего нас построения, которые представлены в п. 7 статьи Н. Rost, Zeitsclirift fiir Walirscliein-liclikeitsttieorie und verwandte Gebiete 58 (1981), 41-53. В ней положено b = , a = \ a t = 4n -t- -/n In n.

Эксперименты показали, что ожидаемое время достижения любой примитивной сети сортировки - не обязательно по методу пузырька - очень близко к 2п. Кстати, Р. П. Стэнли (R. Р. Stanley) и С. В. Фомин доказали, что если компараторы [ifc:u-t-l] выбираются не с равной вероятностью, а таким образом, что ik = j возникает с вероятностью /(2), то соответствующее ожидаемое время становится точно равным {)Нпу

42. Должен существовать путь длиной [Ig п] или больще из некоторого входа в наиболь-щий выход (рассмотрите т„ в теореме А). Если поместить на этот вход оо, то поведение всех компараторов на этом пути будет предопределено, а оставшаяся сеть должна быть (п - 1)-сортировщиком. [IEEE Ъапз. оп Computers С-21 (1972), 612-613.]

45. После I уровней вход xi может оказаться в не более чем 2* разных местах. После заверщения слияния Xi может оказаться в п -Ь 1 разных местах.

46. [См. J. Algoritlims 3 (1982), 79-88; приведенное ниже доказательство предложено В. С. Гринбергом.] Можно предположить, что 1 < m < п и что на любой стадии выполняется m сравнений. Пусть I = 1{п - т)/2], и предположим, нужно выполнить слияние Xl < < Хт с 2/1 < • • < Уп- Противник может принудить выполнить [lg(ni -t- n)] стадий следующим образом: на первой стадии некоторое Xj сравнивается с элементом ук, причем

либо к < I, либо к > I + т. Противник решает, что Xj-i < yi и Xj+i > у„, а также, что Xj > Ук, если к < I, а Xj < Ук, если к > I + т. Остальная часть задачи - это, по сути, слияние Xj либо с Ук+i < • < Ун, либо с 2/1 < •• < ук-i- Таким образом, остается, по крайней мере, тт{п-к+1,к) > тт{п-1+1,1+тп) = [(т + п)/2] исходов. Отсюда следует, что необходимо не менее чем [lg[(m + п)/2]] = [lg(m + п)] - 1 последуюш;их стадий.

48. Пусть и - наименьший элемент среди (xa)j, а t/" - любой вектор из множества Dn, такой, что из {у-°)к = О следует, что {ха)к содержит элемент < и, а из {у-°)к = 1 следует, что {ха)к содержит элемент > и. Если а = Plp:q], то можно найти вектор 2/, удовлетворяюш;ий тому же условию, в котором а заменено элементом /З, и такой, что 2/[р:д] = 2/°. Начав с (г/"); = 1, (2/°) = О, мы, в конце концов, получим вектор У = 2/> УДОвлетворяюш;ий требуемому условию.

Ж. Воде (G. Baudet) и Д. Стивенсон (D. Stevenson) заметили, что из комбинации результатов упр. 37 и 48 следует простой метод параллельной сортировки с (nlnn)/fc + 0{п) циклами сравнения на к процессорах. Для этого следует сначала рассортировать к подфайлов размером < \п/к], а затем слить их за к проходов, используя "четно-нечетное слияние с транспозициями" порядка к. [ШЕЕ Trans. С-27 (1978), 84-87.]

49. Как (а; V 2/) ¥ , так и а; V (у ¥ 2) представляют собой наибольшие m элементов мультимножества хЬуЬг; {х у) Z а X {у z) представляют собой наименьшие m элементов. Если X = у = z = {0,1}, то (г А 2) ¥ (г/ А ) = (г А 2/) ¥ (а: А 2) ¥ (2/ ) = {0,0}, в то время как средние элементы в {О, 0,0,1,1,1} суть {0,1}. Из анализа сети сортировки для трех элементов и результатов упр. 48 следует, что средние элементы х\И уЫ z могут быть выражены либо как {{x\y)f\z)){xf\y), либо как i{xf\y)\z){x)y), либо с помош;ью любой другой формулы, получаемой путем перестановки переменных х, у, z в этих выражениях. (По-видимому, для средних элементов симметричной формулы не существует.)

50. Точно так, как в теореме Z, можно найти все тождества, удовлетворяемые операцией

а; ¥ 2/= и1ш(а;+2/, 1), а; 2/= niax(0, а;+2/-1)

на множестве рациональных чисел х, у в диапазоне [О.. 1]. [Это операция "переливания" как можно большего количества жидкости из одного стакана, в который налиты х, в другой, в который ранее были налиты у, что подмечено Дж. М. Поллардом (J. М. Pollard).] Все такого рода тождества можно получить из системы четырех аксиом и правила интерференции для многозначной логики Лукашевича (Lukasiewicz); см. также работу Rose, Rosser, H-ans. Amer. Math. Soc. 87 (1958), 1-53.

51. Пусть a = a[i:j], a к - произвольный индекс / Если {xa)i < {xa)k при всех X, то {xa)i < {ха)к; если {ха)к < {xa)i и {ха)к < ixa)j при всех х, тогда то же самое имеет место, если заменить а элементом а; если {ха)к < {xa)i при всех х, то {ха)к < {xa)j. Таким образом, мы видим, что для а существует, по крайней мере, столько же соотношений, сколько для а, плюс еще одно, если [i:j] не является избыточным. [Bell System Tech. J. 49 (1970), 1627-1644.]

52. (a) Будем рассматривать сортировку нулей и единиц. Пусть w = a;o-t-a;i-t-- • +а;лг. Сеть не выполнит работу тогда и только тогда, когда и» < t и а;о = 1, прежде чем завершится JV-сортировка. Если в этот момент а;о = 1, то в начале должна была быть единица и при 1 < j < п мы должны были в начале иметь либо X2j-i+2nk = 1 при О < А; < т, либо X2j+2nk = 1 при о < А; < т; таким образом, гу > 1 + (т + 1)п = t. Итак, отказ свидетельствует о том, что w = t и Xj = Xj+2nk при 1 < А; < m и X2j = X2i-i при 1 < j < п. Более того, специальная подсеть должна преобразовать эти входы таким образом, что

X2m+2n+i = 1 при 1 < J < т.