и законы идемпотентности х 1\ х = х\/ х = х, мы можем свести формулы в правой части этой сети соответственно к {а АЬ А с А d), (а Л 6 Л с) V (а Л 6 Л d) V (а Л с Л d) V (6 Л с Л d), (а Л 6) V (а Л с) V (а Л d) V (6 Л с) V (6 Л d) V (с Л d) и а V 6 V с V d.

Докажите, что в общем случае t-Pi в порядке убывания элемент из {a:i,..., я:п} задается "элементарной симметрической функцией"

at{xi,... ,Хп) = \j {xi, Axi2 А Axit I 1 < ii < «2 < • • • < if < n}.

[Здесь (") членов объединяются с помощью операции V. Таким образом, задача нахождения сети сортировки минимальной стоимости эквивалентна задаче вычисления элементарных симметрических функций с минимальным числом схем "и/или", где на каждом шаге величины фиф заменяются величинами ф Аф ш ф\/ ф]

29. [М20] Дано, что х\ < хг < хз и yi < у2 < уз < yi < уъ и что zi < Z2 < < z% - результат слияния хсу. Найдите выражения для каждого Zk в терминах Хку, используя операторы Л и V.

30. [НМ24] Докажите, что любая формула, содержащая Л и V и независимые переменные {a:i,... ,Хп}, может быть приведена с использованием тождеств из упр. 28 к каноническому виду ti V г2 V • • V rfe. Здесь А: > 1 и каждый п имеет вид Д {xj \ j in Si], где Si - подмножество {1, 2,..., n} и никакое множество Si не включается в 5,, если г ф j. Докажите также, что две такие канонические формы равны для всех х\,... ,Хп тогда и только тогда, когда они идентичны (с точностью до порядка).

31. [М24] (Р. Дедекинд (R. Dedekind), 1897.) Пусть (5п - число различных канонических форм от a;i,... ,я;п в смысле упр. 30. Так, Si = 1, = i и дз - 18. Чему равно Si?

32. [М28] (М. У. Грин (М. W. Green).) Пусть Gi = {00,01,11}; определим Gt+i как множество всех цепочек вффш, таких, что в, ф, ф, и; имеют длину 2" и вф, фи:, вф ш фко принадлежат Gt. Пусть а - сеть, состоящая из четырех первых уровней 16-элементного сортировщика, изображенного на рис. 49. Покажите, что Diqcx = Gi, и докажите, что это множество имеет в точности 5i + 2 элементов (см. упр. 31).

► 33. [М22] Не все Sn функций от (xi,... ,Хп) из упр. 31 могут встретиться в сетях компараторов. Докажите, что функция (xi Axi) V (жз Лжз) V {x3Axi) не может быть результатом работы никакой сети компараторов от (a:i,... ,а;п). 34. [23] Является ли следующая сеть сетью сортировки?

35. [20] Докажите, что в любой стандартной сети сортировки должен, по крайней мере, один раз встретиться каждый из соседних компараторов [г:г--1] при 1 < г < п.

► 36. [22] Сеть, представленная на рис. 47, содержит только кратчайшие сравнения [г;г--1]. Будем называть такие сети примитивными.

a) Докажите, что примитивная сеть сортировки для п элементов должна иметь не менее (2) компараторов. [Указание. Рассмотрите инверсии перестановки.]

b) (Р. У. Флойд, 1964.) Пусть а - примитивная сеть для п элементов, & х - вектор, такой, что {xaji > {xa)j при некоторых i < j. Докажите, что {ya)i > {ya)j, где у - вектор {п, п-1,..., 1).

c) В качестве следствия (Ь) докажите, что примитивная сеть является сетью сортировки тогда и только тогда, когда она сортирует единственный вектор (п, п-1,..., 1).

37. [М22] Четно-нечетная сортировка с транспозициями для п чисел, п > 3, - это п-уровневая сеть с п(п - 1) компараторами, напоминающая кирпичную кладку (рис. 58). (Если п четно, имеется два варианта.) Такую сортировку особенно легко реализовать аппаратно, поскольку выполняются попеременно только два вида действий. Докажите, что такая сеть действительно будет работающей сетью сортировки. [Указание. См. упр. 36.]

,1,1,1

1,1.1 111 тгт

rrrr- 111 111

111 ill =trm

rr~ rrr III

n = 5 n = 6 n - 6

Рис. 58. Четно-нечетная сортировка с транспозициями.

► 38. [43] Пусть N = (j). Найдите взаимно однозначное соответствие между диаграммами Юнга вида (п-1, п-2,..., 1) и примитивными сетями сортировки [ii .ii-l-l]... [iN-iN+l]. [Следовательно, по теореме 5.1.4Н существует точно

1п-13П-25П-3 (2п-3)1

таких сетей сортировки.] Указание. В упр. 36, (с) показано, что примитивные сети без избыточных компараторов соответствуют пути от 12... п до п... 2 1 на многограннике, подобном изображенному на рис. 1 в разделе 5.1.1.

39. [25] Пусть известно, что примитивная сеть компараторов состоит из п линий и правильно сортирует единственный вход 1010 ... 10. (См. упр. 36; полагается, что п четное.) Покажите, что в такой сети "средняя треть", состоящая из всех компараторов, подключенных только к линиям от [п/З] до [271/3] включительно, будет сортировать любые входы.

40. [НМ44] Пусть компараторы [п .n-f-l][i2 :i2+l] • • • [v :«г+1] выбираются случайно, причем каждое значение и € {1, 2,..., п - 1} равновероятно. Процесс прекращается, когда в составе сети в качестве подсети появляется конфигурация сортировки по методу пузырька, подобная изображенной на рис. 47. Докажите, что г < 4п -f 0(п bgn), а вероятность остальных случаев - 0(п~°°°).

41. [Л/./7] Пуссь компараторы [ii: ji][J2 -32] • • • [«г -jr] выбираются случайным образом, причем каждый неизбыточный выбор 1 < н < jk < п имеет равную вероятность. Процесс остановится, когда получится сеть сортировки. Оцените ожидаемое значение г; будет ли оно 0(п+) при всех е > О?

► 42. [25] (Д. Ван Ворис (D. Van Voorhis).) Докажите, что 5(п) > 5(п - 1) -Ь [Ig ri].

43. [48] Найдите (m, п)-сеть слияния с числом компараторов, меньшим С(т, п), или докажите, что такой сети не существует.

44. [50] Найдите точное значение 5(п) для какого-либо п > 8.

45. [М20] Докажите, что любая (1, п)-сеть сортировки без разветвлений должна иметь по крайней мере [lg(n -Ь 1)] уровней задержки.

► 46. [30] (М. Айгнер (М. Aigner).) Покажите, что при использовании любого алгоритма, который способен параллельно выполнять несвязанные сравнения минимальное число стадий, необходимых для слияния т элементов, будет не меньше [lg(m-- п)]; следовательно, битонная сеть сортировки имеет оптимальную задержку.

47. [47] Является ли функция Г(п) в упр. 6 строго меньшей, чем Т{п) при некотором п?

► 48. [26] Можно дать другую интерпретацию сетей сортировки, считая, что на каждой линии находится не одно число, а мультимножество из in чисел; при такой интерпретации операция [i-.j] заменяет Xi и Xj соответственно значениями Xi xj и ж, Xj - наименьшими т и наибольшими пг из 2т чисел х, 1±) Xj. (Например, на приведенной ниже схеме иллюстрируется такая интерпретация при т - 2; каждый компаратор сливает свои входы и отделяет нижнюю половину от верхней.)

Если а и 6 суть мультимножества, содержащие по т чисел, то будем говорить, что а <С 6 тогда и только тогда, когда а = а (или, что эквивалентно, Ь = Ь; наибольший элемент а меньше или равен наименьшему элементу 6). Таким образом, а Д Ь <С а V Ь.

Пусть а есть п-сеть, а а; = (a;i,... ,я;п) - вектор, в котором каждая компонента Xi - мультимножество из m элементов. Докажите, что если {xa}i не <С {xa)j в описанной интерпретации, то в Dn найдется вектор у, такой, что {уа){ = 1 и {ya)j - 0. [Следовательно, сеть сортировки п элементов превращается в сеть сортировки тп атементов, если заменить сравнения т-путевыми слияниями. На рис. 59 изображен 8-элементный сортировщик, построенный из 4-элементного с использованием этого вывода.]

Рис. 59. 8-элементный сортировщик, построенный из 4-элементного сортировщика с использованием слияния.

49. [М23] Покажите, что в обозначениях упр. 48 {xf{y)f{z = xf{{yz) и {ху)Цг = x\{y)z); однако {x\y)z не всегда равно (х z)) (у z) и (х у)) (х z)) (у z) не всегда равно средним т элементам жЫуЫг. Найдите правильную формулу для этих средних элементов, использовав в ней х, у, z, а также операции шЦ.

50. [НМ46] Исследуйте свойства операций Д и V, определенных в упр. 48. Можно ли охарактеризовать все тождества в этой алгебре каким-либо изящным способом или вывести все их из конечного набора тождеств? В этом отношении такие тождества, как ххх = xfx и х{хЦ{х{хЦу))) = х{хЦу), которые имеют место только для m < 2, представляют относительно небольшой интерес; рассматривайте лишь тождества, справедливые при всех т.

► 51. [М25] (Р. Л. Грэхем (R. L. Graham).) Компаратор называется избыточным в сети ai[i:j]a2, если либо {xai)i < {xa\)j для всех векторов х, либо (xai)i > {xai)j для всех векторов х. Докажите, что если а является сетью с г неизбыточными ко.мпараторами, то найдется по крайней мере г различных упорядоченных пар (i,j) различных индексов, таких, что {xa)i < {xa)j для всех векторов х. (Следовательно, сеть без избыточных компараторов содержит не более (2) модулей.)