Стадия 1

Стадия 2

Стадия 3

Стадия 4

X - \- X О

y-LJ-y

X -У -

- min(x, у) тах(х,у)

X -У -

- max(x,i/) -min(x,i/)

Рис. 57. Сортировка 16-ти идеально перемешанных элементов.

12. [М20] Докажите или опровергните следующее утверждение: если х и у - битонные последовательности равной длины, то последовательности хУ у и х Ау также битонные.

► 13. [24] (X. С. Стоун (Н. S. Stone).) Покажите, что сеть сортировки для 2 элементов можно построить по схеме, представленной на рис. 57, для случая t = 4. Каждый из шагов этой схемы состоит из "идеального тасования" первых 2" элементов с последними 2~\ за которым следуют операции, выполняемые одновременно над 2" парами соседних элементов. Каждая из этих операций обозначена либо через "О" (нет операции), либо через "+" (стандартный модуль компаратора), либо через "-" (обращенный модуль компаратора). Сортировка протекает в t стадий по t шагов каждая; на последней стадии все операции суть "+". В течение стадии s при s < t мы выполняем t - s шагов, где все операции суть "О" а затем выполняем s шагов, где на каждом, д-м шаге поочередно выполняются 2" операций "-Ь" и затем 2" операций "-" при q = 1, 2,..., s.

[Попутно отметим, что эта схема сортировки может быть реализована весьма простым устройством, реализующим один шаг "тасования и операций" и возвращающим выход на вход. Первые три шага на рис. 57 можно, конечно, исключить. Они оставлены лишь для того, чтобы сделать схему понятнее. Стоун замечает, что тот же принцип "тасования/опе-рации" встречается в других алгоритмах, таких как быстрое преобразование Фурье (см. формулу 4.б.4-(40)).]

► 14. [М27] (В. Е. Алексеев.) Пусть а = [ii:ji]...[ir-jr] представляет собой п-сеть; при 1 < S < г определим = [ii :/i]... [ii js-i][is -js] • • [*r -jr], где ik и jj, получены из u и jk путем замены элементом js и замены js элементом is во всех случаях, когда они встречаются. Например, если а = [1:2][3:4][1:3][2:4][2:3], то а* = [1:4][3:2][1:3][2:4][2:3].

a) Докажите, что Dna = Dn(a).

b) Докажите, что (aY = (л)".

c) Сопряженной с а является любая сеть вида {... {(ау).. .)>. Докажите, что а имеет не более 2" сопряженных сетей.

d) Пусть да{х) = [я: € Dno] и пусть /а(я:) = (£ii V Xji) А А (xi V Xjv). Докажите, что да{х) = \/{fa{x) I а является сопряженной с а}.

e) Пусть Ga есть ориентированный граф с вершинами {1,...,п} и дугами -> js при 1 < S <г. Докажите, что а является сетью сортировки тогда и только тогда, когда Ga имеет направленный путь от г к г-Ы при 1 < г < п и для всех а, сопряженных с а. [Это условие весьма примечательно, поскольку Ga не зависит от порядка компараторов в а.]

15. [20] Найдите нестандартную сеть сортировки четырех элементов, содержащую только пять модулей компараторов.

16. [М22] Докажите, что следующий алгоритм преобразует любую сеть сортировки [п : ji] • - [ir-jr] в стандартную сеть сортировки той же длины.

Т1. Пусть q - наименьший индекс, такой, что г, > jq. Если таких индексов нет, то остановиться.

Т2. Заменить все вхождения г, элементами jq и все вхождения j, элементами г, во всех компараторах [is -.js] для q < s <г. Вернуться к шагу Т1.

Так, [4:1][3:2][1:3][2:4][1:2][3:4] преобразуется сначала в [1:4][3:2][4:3][2:1][4:2][3:1], затем в [1:4] [2:3] [4:2] [3; 1] [4:3] [2:1], затем в [1:4] [2:3] [2:4] [3; 1] [2:3] [4:1] и т. д., пока не получится стандартная сеть [1:4][2:3][2:4][1:3][1:2][3:4].

17. [М25] Пусть Dtn - множество всех (") последовательностей {xi,.. .,Хп) из нулей и единиц, имеющих ровно t единиц. Докажите, что Ut{n) равно минимальному числу компараторов, которые необходимы в сети, сортирующей все элементы Dtn, что Vt(n) равно минимальному числу компараторов, необходимых для сортировки An UD(f i)„; и что Wt{n) равно минимальному числу компараторов, необходимых для сортировки Uo<fc<f п

► 18. [М20] Докажите, что для сети, которая определяет медиану 2t - l элементов, требуется не менее (i -l)["lg(t-H)]-Ь flgt] модулей компараторов. [Указание. См. доказательство теоремы А.]

19. [М22] Докажите, что f72(n) = 2п - 4 и Щп) = 2п - 3 для всех п>2.

20. [24] Докажите, что ЩЬ) = 7.

21. [21] Подтвердите или опровергните следующее утверждение: вставка нового стандартного компаратора в любую стандартную сеть сортировки приведет к образованию новой стандартной сети сортировки,

22. [М17] Пусть а - любая п-сеть, & х и у - два п-вектора.

a) Докажите, что из х <у следует ха < уа.

b) Докажите, что х у < (ха) (уа), где х у означает скалярное произведение xiyi + +

ХпУп-

23. [Ml8] Пусть а есть п-сеть. Докажите, что существует перестановкар € Рп, такая, что {pa)i = j тогда и только тогда, когда в D„ найдутся векторы хиу, такие, что х покрывает у, ixa}i = 1, {ya)i = О и С{у} = j-

► 24. [М21] (В. Е. Алексеев.) Пусть а есть п-сеть; введем обозначения

h - min{(pa)fc I р € Рп}, = max{(pa)A, ] р € Рп}

при 1 < А: < п для нижней и верхней границ диапазона значений, которые могут появляться на линии выхода к. Пусть 1 и uj. - аналогично определенные величины для сети а = Q[i:j]. Докажите, что

li = liMj, lj<li + lj, ui>Ui + Uj-{n + l), uj=UiVUj.

[Указание. Для данных векторов х к у из Dn, таких, что {xa)i = {ya)j = О, {х) = U и С(г/) = найдите вектор z из Dn, такой, что {za)j = О, c{z) < U + lj.]

25. [МЗО] Пусть lk и Uk определены, как в упр. 24. Докажите, что множество {{ра)к \ р in Рп} содержит все целые числа между 1к и Uk включительно.

26. [М24] (Р. У. Флойд.) Пусть а есть п-сеть. Докажите, что множество Dna = {ха \ х in Dn} может быть определено из множества PnQ = {pa р in Рп} и, обратно, Рпа может быть определено из Dna.

► 27. [М20] Пусть X и у - векторы и пусть ха и уа - рассортированные векторы. Докажите, что .(<*)i < {ya)j тогда и только тогда, когда для любой совокупности j элементов из у можно найти совокупность i элементов из х, такую, что любой элемент, взятый из X, меньше некоторого элемента, взятого из у, или равен ему. Используйте этот принцип для доказательства того, что если рассортировать строки любой матрицы, а затем рассортировать столбцы, то строки.останутся упорядоченными.

► 28. [М20] На следующей диаграмме показано, как записать формулы для содержимого всех линий сети сортировки через ее входы.

-а л Ь--а Vb--сЛ d--cVd-

- (а Л Ь) Л (с Л d). . (а V Ь) Л (с V d).

- (а ЛЬ) V (с Ad). {aV Ь)\/ (сУ d).

{а ЛЬ) Л {с Ad)

((aVb)A (cVd))A ((а Ab)V(cAd))

((а V Ь) А (с V d)) V ((а А Ь) V (с А d)) {aV b)V {cv d)

Используя законы коммутативности х А у = у А х, xV у = yV х, законы ассоциативности X А (у А z) = (х Ay) А z, хУ {уУ z) = {хУ у)У z, законы дистрибутивности х А (у У z) = (х Ау)У (х Az), хУ (у Az) = {хУ у) А{хУ z), законы поглощения х А (х У у) = х У (х Ау) = х