5. Пусть /(n) = /(fn/2l) + 1 + [lgfn/2]], если n > 2. Тогда, применив индукцию по п, получим /(п) = (1 + figп])[Ign]/2.

6. Можно считать, что на каждой стадии выполняется [n/2j сравнений (лишние сравнения не помешают). Так как Т(6) = 5, достаточно доказать, что Т{5) = 5. В случае п = 5 после двух стадий мы не можем избежать частичных упорядочений или которые нельзя рассортировать за оставшиеся две стадии.

7. Допустим, что исходными ключами будут {1,2,..., 10}. Ключевым моментом решения является то, что после первых 16 компараторов линии 2, 3, 4 и 6 не могут содержать ни 8, ни 9, ни 6 и 7 вместе.

8. Это очевидное обобщение теоремы F.

9. Л/(3,3) > 5(6) - 25(3), М(4,4) > 5(8) -23(4), М(5,5) > 2М(2,3) -ЬЗ, как следует из результатов упр. 8 и М(2, 3) > 5(5) - 5(2) - 5(3). Аналогично М(3,4) = 8. Но чему равны М(3,5) и М(4,5)?

10. Используйте указание и метод доказательства теоремы Z. Затем покажите, что число нулей в четной подпоследовательности минус число нулей в нечетной подпоследовательности равно ±1 или 0.

11. (Решение М. У. Грина.) Рассматриваемая сеть симметрична в том смысле, что всякий раз, когда Zi сравнивается с Zj, найдется соответствующее сравнение Z2t i j :г2( 1 ,-. Любая симметричная сеть, способная сортировать последовательность (го,..., 22( i), будет также сортировать последовательность (-jt-i,..., -го).

Бэтчер заметил, что эта сеть в действительности будет сортировать любой циклический сдвиг {zj,Zj+i, ... ,Z2t-i,zo,... ,Zj-i) битонной последовательности. Это следует из принципа нулей и единиц.

[Данный результат не приложим к битонным сортировщикам, если их порядок отличен от степени 2. Например, сортировщик на рис. 52 не сможет сортировать последовательность (0,0,0,0,0,1,0). Сформулированное Бэтчером определение битонной последовательности сложнее и менее удобно, чем то, которым мы пользуемся.]

12. Последовательность xV у является битонной (рассмотрите последовательности из О и 1), а последовательность х Лу - нет (рассмотрите, например, (3,1,4, 5) Л (6, 7, 8, 2)).

13. Идеальное тасование заменяет Zi элементом Zj, где двоичное представление j получается из представления i в результате циклического сдвига вправо на один разряд (см. также упр. 3.4.2-13). Рассмотрим перетасовку компараторов, а не линий. Тогда первый столбец компараторов имеет дело с парами г [г] и г [г Ф 2"""], следующий столбец - с парами z[i] и z[i ф 2"], ..., t-Pi столбец - с z[i] и z[i Ф 1], {t + 1)-й столбец - снова с z[i] и z[i Ф 2"] и т. д. Здесь Ф обозначает операцию "исключающее или" над двоичными представлениями. Эти соображения показывают, что рис. 57 эквивалентен рис. 56; после S стадий мы получаем рассортированные группы из 2 элементов с чередующимися направлениями упорядочения.

В работе С. G. Plaxton, Т. Suel, Math. Systems Theory 27 (1994), 491-508, показано, что любая сеть такой структуры имеет, по меньшей мере, n((logn)7loglogn) уровней задержки.

14. (а) Пусть J/i, = Xj,, yj, = Xi,, у к = Хк при is ф к ф js] тогда уа = ха. (Ь) Это очевидно до тех пор, пока множество {is,J3,it,jt} имеет только три отличающихся элемента; предположим, что is - it. Тогда, если s <t, первые s - 1 компараторов заменят {i3,js,jt) соответственно элементами (js,jt,is) как в (аУ, так и в (а), (с) (аУ = а и а = а, так что можно предположить, что si > «2 >••>«*> 1- (d) Пусть /3 = a[i:j], тогда g0(xi,...,Xn) = {xiVxj)A{ga(xi,...,Xi,...,Xj,...,Xn)Vgaixi,...,Xj,...,Xi,...,Xn)). Построив итеративную процедуру из этих равенств, получим искомый результат, (е) fa{x) = 1

тогда и только тогда, когда не существует пути на графе Ga от г к j при условии Xi > Xj. Если а - сеть сортировки, то сопряженная с а сеть также является сетью сортировки и /а(х) = о при всех X, удовлетворяющих неравенству Xi > Xi+i. Примем х - е(*); это показывает, что G не имеет дуг от г к fci при некотором fci ф i. Если fci Ф i + 1, то X = е() V e(*i) показывает, что G имеет дугу от i или fci к при некотором ki {г, fci}. Если к2 Ф г + 1, продолжаем рассуждать так же до тех пор, пока не найдем путь на графе G от г к г + 1. Обратно, если а не является сетью сортировки, положим, что х - вектор с Xi > Xi+i и 9а(х) = 1. Для некоторого сопряженного а получим /«(х) = 1, так что Ga может и не иметь пути от г к г + 1. [В общем случае (xa)i < {xa)j при всех X тогда и только тогда, когда Ga имеет ориентированный путь от г к j при всех а, сопряженных с а.]

15. [1:4][3:2][1:3][2:4][2:3].

16. Процесс, очевидно, заканчивается. После каждого выполнения шага Т2 выходы с номерами г, и jq меняются местами, поэтому в результате выполнения алгоритма сформируется некоторая перестановка выходных линий. Так как получившаяся (стандартная) сеть не изменяет вход (1, 2,..., тг), выходные линии должны вернуться на свои прежние места.

17. Сделайте сеть стандартной, воспользовавшись результатом упр. 16. Затем, анализируя входную последовательность (1, 2,..., тг), увидим, что стандартные сети выбора должны помещать t наибольших элементов на t линий с наибольшими номерами, а 1((тг)-сеть должна помещать <-й в порядке убывания элемент на линию п+1 - t. Примените принцип нулей и единиц.

18. Из доказательства теоремы А следует, что Vt(n) > (п - t) \\g(t + 1)] + \lgt].

19. Сеть [1:тг][2:п] . .. [1:3][2:3] выбирает наименьшие два элемента, имея 2тг - 4 компараторов. Для V2(n) добавьте [1:2]. Нижняя оценка получается из теоремы А (см. ответ к предыдущему упражнению).

20. Прежде всего, заметим, что Vs{n) > Vs{n- 1) + 2, если п > 4. В силу симметрии можно считать, что первый компаратор есть [1:тг], после него расположена сеть для выбора третьего в порядке убывания из (х2, хз,..., Хп) и еще один компаратор, связанный с линией 1. С другой стороны, Vs(5) < 7, так как 4 компаратора находят минимум и максимум из {xi,X2,X3,X4} и остается рассортировать три элемента.

21. Утверждение ложно. Рассмотрите, например, сети [1:2][3:4][2:3][1:4][1:2][3:4] и [1:2] [3:4][2:3][3:4][1:4][1:2][3:4]. (Однако Н. Г. де Брейн (N. G. de Bruijn) доказал, что новые компараторы не вносят путаницу в пргшитивную сеть сортировки в смысле упр. 36; см. Discrete Math. 9 (1974), 337.)

22. (а) Результат получается индукцией по длине а, поскольку из Xi < у, и Xj < yj следует, что х; Л ху < у, Л yj и х; V Xj < yt V yj. (b) Результат получается индукцией по длине а, поскольку (х; Л Xj)(yi Л yj) + (xi V Xj)(yi V yj) > ХгУг + Xjyj. [Следовательно, u(x Ay) < u(xa Л у a). Автором этого вывода является У. Шокли (W. Shockley).]

23. Пусть Xk - 1 тогда и только тогда, когда рк > j, ук - 1 тогда и только тогда, когда Рк > j- Отсюда (ха)к = 1 тогда и только тогда, когда (ра)к > j, и т. д.

24. Формула для 1[ очевидна, а для lj выберем z = х Л у, как в указании. Обратите внимание на то, что из упр. 21 следует, что (za)i = {za)j = 0. Добавление дополнительных единиц к Z доказывает существование перестановки р, такой, что {pa)j < ((z), как следует из результатов упр. 23. Соотношения для и[ и uj получаются, если обратить порядок.

25. (Решение Дж. Шапиро (Н. Shapiro).) Пусть р и q суть перестановки, такие, что (ра)к = 1к ч {q)k = к- Можно преобразовать р в g за ряд шагов, на каждом из которых

выполняется взаимный обмен пар (г, г + 1) соседних целых; такой взаимный обмен приводит к изменению fc-ro выхода на не более чем ±1.

26. Существует взаимно однозначное соответствие, которое сопоставляет элементу (pi,..., Рп) из Р„а "последовательность покрытий": г покрывает ... покрывает х"\ где х принадлежат DnC»; в этом соответствии = х* V e(J тогда и только тогда, когда Pj = i. Например, (3,1,4, 2) соответствует такой последовательности: (1,1,1,1) покрывает (1,0,1,1) покрывает (1,0,1, 0) покрывает (0,0,1,0) покрывает (0,0,0,0). [Эндрю Яо проверил это заключение, протестировав сеть сортировки на {Х/2\) " соответствующим образом подобранных перестановках. Например, любая 4-элементная сеть, которая сортирует (4,1, 2, 3), (3,1,4, 2), (3,4,1, 2), (2, 4,1, 3) и (2,3,4,1), сортирует любую последовательность. См. упр. 6.5-1; см. также упр. 56.]

27. Этот принцип справедлив, поскольку (ха); является г-м по возрастанию элементом в X. Если X п у обозначают различные столбцы матрицы, строки которой упорядочены, т. е. Xi < yi при всех г, и если ха и уа обозначают результат сортировки столбцов, то из сформулированного принципа следует, что (ха); < (г/о); при всех г, поскольку мы можем выбрать г элементов х в тех же строках, в которых находятся данные i элементов у. [Этот принцип был использован для доказательства инвариантного свойства сортировки Шелла (теорема 5.2.1К). Дальнейшее развитие идея получила в интересной статье David Gale, R. М. Кагр, J. Computer and System Sciences 6 (1972), 103-115. Тот факт, что сортировка столбцов не нарушает упорядоченность строк, был, вероятно, впервые замечен в связи с обработкой таблиц; см. Hermann Boerner, Darstellung von Gruppen (Springer, 1955), Chapter V, §5.]

28. Если {x;i,..., X;,} суть t наибольших элементов, то Xij Л ... Л х;, есть t-й элемент. Если {xii,..., X;,} не являются t-ми наибольшими элементами, то Xjj Л ... Л х;, меньше t-ro элемента.

29. (xiA?/i,(x2A«/i)V(xiA«/2),(x3A«/i)V(x2Aj/2)V(xiA«/3), ?/i V(x3 Аг/2) V(x2Аг/з) V(xi Аг/4), У2 V (хз А Уз) V (Х2 А г/4) V (xi А г/5), уз V (хз А г/4) V (х2 А г/5) V xi, г/4 V (хз А уъ) V Х2, г/5 V хз).

30. Применив законы дистрибутивности и ассоциативности, можно привести любую формулу к набору членов, связанных операцией V, где каждый член представляет собой объединение посредством операции Л исходных переменных; каноническая форма получается затем с помощью законов коммутативности, идемпотентности и поглощения. Далее, 5; - это такие множества S, при которых формула равна 1, если Xj = [j € 5]; в то же время формула равна О, если ху = [j € 5] для любого собственного подмножества S множества 5.

31. ($4 = 166. В работе R. Church, Duice Afath. J. 6 (1940), 732-734, показано, что 65 = 7579, а в работе М. Ward, BuJJ. Amer. Afath. Soc. 52 (1946), 423, - что дв = 7828352 и следующие значения будут такими: 87 = 2414682040996, 5% = 56130437228687557907786 [R. Church, Notices Amer. Afath. Soc. 12 (1965), 724; J. Berman, P. Kohler, AfitteiJungen Afath. Seminar GieBen 121 (1976), 103-124; D. Wiedemann, Order 8 (1991), 5-6]. Неизвестно никакой простой формулы для Sn\ в работе D. Kleitman, Ргос. Amer. Afath. Soc. 21 (1969), 677-682, доказано с помощью очень сложных рассуждений, что (lg<5n)/(„"2j) ~ "Р" п -+ оо.

32. G(+i является также множеством всех цепочек вф, где в ш ф лежат в Gt и в < ф, как векторы, составленные из О и 1. Отсюда следует, что Gt есть множество всех цепочек Zo...Z2t-i ИЗ нулей и единиц, где г; < Zj, если двоичное представление индекса i "<" двоичного представления j (т. е. оба индекса рассматриваются как векторы из нулей и единиц). Каждый элемент zq . .Z2t i множества Gt, кроме 00...Ои 11...1, представляет A-V-функцию /(xi,..., Xt) из D2i при соответствии /(xi,..., xt) = г[(х1 ... Х()2].

33. Если бы такая сеть существовала, то мы получили бы, что (xiAx2)V(x2Ax3)V(x3AX4) -

f(Xl А X2,Xl V Х2,Хз, Х4) или /(Xl А Хз, X2,Xl V Хз,Х4) или . . . или /(Х1,Х2,Хз А Х4, Хз V Х4)