AOP_Tom3 (1021738), страница 188
Текст из файла (страница 188)
19. Сеть [1; пЦ2: и]... [1 ЗЦ2: 3] выбирает наименьшие два элемента, имея 2п — 4 компараторов. Для! е(п) добавьте [1:2]. Нижняя оценка получается из теоремы А (см. ответ к предыдущему упражнению). 20. Прежде всего, заметим, что Ъз(п) > Ъз(п — 1) +2, если и > 4. В силу симметрии можно считать, что первый компаратор есть [1: и], после него расположена сеть для выбора третьего в порядке убывания из (хю хз,, к„) и еще один компаратор, связанный с линией 1. С другой стороны, 1тз(3) < 7, так как 4 компаратора находят минимум и максимум из (хт, хж хз, х») и остается рассортировать три элемента 21.
УтвеРждение ложно. РассмотРите, напРимеР, сети [1:2ЦЗ:4Ц2:ЗЦ1 4Ц1 2ЦЗ:4) и [1. 2] [3:4Ц2:ЗЦЗ:4Ц1:4Ц1:2ЦЗ:4]. (Однако Н. Г. де Брейн (Х. С. Ое Вгп1)п) доказал, что новые компараторы не вносят путаницу в приматппеиую сеть сортировки в смысле упр. Зб, см. ВЫстеге МаНь 9 (1974), 337.) 22. (а) Результат получается индукцией по длине и, поскольку из хт < у, и х, < уэ следует, что к, Л х„< ут Л у и хт Ч х < у, Ч уу. (Ь) Результат получается иидукцией по длине а, поскольку (х; Л к )(у; Л у ) + (х; Ч хт)(у, Ч у ) > х у, + х ут. [Следовательно, тт(х Л у) <» (ха Л уп).
Автором этого вывода является У. Шокли (ЪЧ. ЯЪос1»1еу).] 23. Пусть х» = 1 тогда и талька тогда, когда р» > 1', у» = 1 тогда и только тогда, когда р» > 71 Отсюда (хст)» = 1 тогда и только тогда, когда (ра)» > 1, и т. д. 24. Формула для 1,' очевидна, а для 1,' выберем х = х Л у, как в указании. Обратите внимание на то, что из упр. 21 следует, что (хо)» = (хо)т. = О. Добавление дополнительных единиц к е доказывает существование перестановки р, такой, что (ро') < Де), как следует из результатов упр. 23.
Соотношения для а[ и а„' получаются, если обратить порядок. 25. (Решение Дж. Шапира (Н. БЬартга).) Пусть р и д суть перестановки, такие, что (ра)» = 1» и (до)» = ью Можно преобразовать р в д за ряд шагов, на каждом из которых выполняется взаимный обмен пар (з, з+1) соседних целых; такой взаимный обмен приводит к изменению й-го выхода на не более чем х1. 26. Существует взаимно однозначное соответствие, которое сопоставляет элементу (рм р„) из уг,а "последовательность покрытий"; х1Н покрывает .
покрывает хыз, где хо! принадлежат Р„а; в этом соответствии ха М = хб! Ч ебз тогда и только тогда, когда р, = й Например, (3, 1,4, 2) соответствует такой последовательности: (1, 1, 1, 1) покрывает (1,0, 1, 1) покрывает (1,0, 1, 0) покрывает (0,0, 1, О) покрывает (О, О, О, 0). [Эндрю Яо проверил это заключение, протестировав сеть сортировки на (,„" ) — 1 соответствующим образом подобранных перестановках. Например, любая 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. Этот принцип справедлив, поскольку (хо), является з-м по возрастанию элементом в х. Если х и у обозначают различные столбцы матрицы, строки которой упорядочены, т.
е. х; < у, при всех з, н если го и уа обозначают результат сортировки столбцов, то из сформулированного принципа следует, что (ха), < (уо), при всех з, поскольку мы можем выбрать з элементов х в тех же строках, в которых находятся данные з элементов у [Этот принцип был использован для доказательства инвариантного свойства сортировки Шелла (теорема 5.2.1К). Дальнейшее развитие идея получила в интересной статье Рак!з) Са!е, В М. Катр, Х Сатризег аис( Бузгет Вс!епгез 6 (1972), 103-115.
Тот факт, что сортировка столбцов не нарушает упорядоченность строк, был, вероятно, впервые замечен в связи с обработкой таблиц; см. Неппапн Воегиег, Рагззе!!иззу гон Сгирреп (Брг1лбег, 19а5), СЬарзег Ч, 55.] 28. Если (хп,, хч) суть ! наиболыпих элементов, то хч Л... Л хч есть бй элемент. Егли (хч,...,хч] ие являющая бми наибольшими элементами, то хч Л... Л хч меньше З-го элемента. 29. (хз луп (хглу~)ч(хг луг), (хзлуг)ч(хглуг)ч(хз луг), у~ ч(хзлуг)ч(хглуз)ч(хз луг), уг Ч (хз Л уз) Ч (хг Л уз) Ч ( гз Л уз), уз Ч (хз Л уз) Ч (хг Л уз) Ч хм у4 Ч (хз Л уз) Ч хг. уз Ч хз).
30. Применив законы дистрнбутивности и ассоциативности, можно привести любую формулу к набору членов, связанных операцией Ч, где каждый член представляет собой объединение посредством операции Л исходных переменных; каноническая форма получается затем с помощью законов коммутатнвности, идемпотентности н поглощения. Далее, аз это такие множества 8, при которых формула равна 1, если хг = [7' 65]; в то же время формула равна О, если х = [В б Я'] для любого собственного подмножества В' множества 8. 31.
Вз = 166. В работе В. СЬигсЬ, Вийе Магй .!. 6 (1940), 732-734, показано, что Вз = 7579, а в работе М. ЪЧагб, Ви!!. Ашгг. ЫаЗЛ. Баг. 52 (1946), 423, — что бе = 7828352 и следующие значения будут такими; Вг = 2414682040996, дз = 56130437228687557907786 [В. СЬигсЬ, 7!аз!гез Атег. Мабб Зос. 12 (1965), 724; 3 Ветшал, Р. КаЭйег, Михе!!ииуео Магй. Веш!ггаг С!едегг 121 (1976), 103-124; Р.
%')ебешаип, Огг!ег 8 (1991), 5-6]. Неизвестно никакой простой формулы для д„; в работе Р К!ейгаап, Ргос. Ашег. Магй. Яас, 21 (1969), 677-682, доказано с ползощью очень ггожных рассуждений, что (185 )гз(,,"„!) -+ 1 при 7г! и -+ ао. 32. Сз+з является также множеством всех цепочек ВЗЬ где В и ф лежат в Сз и В < г]г, как векторы, составленные из 0 и 1. Отсюда следует, чта С, есть множество всех цепочек зе...
зг~, из нулей и единиц, где зз < зю егли двоичное представление индекса з "<" двоичного представления В (т. е. оба индекса рассматриваются как векторы из нулей и единиц). Каждый элемент зе... зг~, множества Ст, кроме 00 .. 0 и 11... 1, представляет л — чфункидю 7(хы,хз) из Рм при соответствии ! (хм...,хз) = з[(хг ..хз)г]. ЗЗ. Если бы такая сеть существовала, то мы получили бы, что (хг Лхг) Ч(хглхз) У(хздхз) = з(хз Лхг,хз Чхз,хз,хз) или З(хз Лхз хг,хз Чхз,хз) илн...
или !(хыхг,хаЛхмхзЧхз) для некоторой функции с. Подставляя (хс,хз,хз,:сс) = (х,х,1,0), (х,О,х,1), (.г,1,0,х), (1, х, х, 0), (1, х, О, х), (О, 1, х, х), находим, что такой функции у не существует. 34. Да; доказав эта, вы можете взяться за сеть, представленную на рнс.
49, при и = 16 (если только вы просто не проверите это иа всех двоичных векторах 2", воспользовавшись теоремой Е). 35. В противном случае перестановка, в которой только С и с + 1 находятся не на своих местах, никогда не была бы рассортирована. Пусть Р» —. номера компараторов [с:с+А! в стандартной сети сортировки. Тогда Рс + 2Рз + Рз > 2(п — 2), поскольку должно существовать два компаратора от (с, С+1) до (с+2, с+3) прн 1 < с < и — 3 так же, как [1:2! и [и-1;и! Аналогично Р~ Ч 2Рз+..
+ЫР»+(Ы вЂ” 1)Р» с+ .+Рз»» > Ы(п — Ы). Эта формула предложена Дж. М. Поллардом (Я. М. Ройагс() Можно также доказать, что 2Вс + Рз > 3п — 4 Егли удалить первые компараторы вида [Ззу+1! для всех с', то должен существовать, по меньшей мере, еще один компаратор, размесцешсый в пределах (з,з+1,»+2) прн1 < С < и — 2 АнаяогичнайВ»+(Ы-1)Рз+..+Р» > Б(Ы+1)(п — Ы)+Ы(Ы вЂ” 1).
36. (а) Каждое сравнение соседних элементов уменьшает число инверсий на 0 или 1, а (п,п — 1,...,1) имеет (") инверсий. (Ъ) Пусть о = сЗ[р:р+1! н будем рассуждать по индукции по длине о. Если р =- з, та З > р + 1, и (хсЗ)р > (х»З)м (хд)р»з > (хсЗ)з: следовательно, (уБ)р > (у)З), и (уД)рз.с > (уД),. Если р = с — 1, то либо (хд)р, либо (хд)р»з > (х~д)„: следовательно, либо (УСЗ)„либо (УСЗ)р»с > (УСЗ), Егчи Р = 7' — 1 или В рассуждения аналогичны. Для остальных р доказательство тривиально.
Замечаиое. Если а является сетью сортировки, то ол — тоже сеть сортировки (в ней компараторы расположены в обратном порядке). Более общий случай и другое доказательство (с) приведены в работе К. С, с(е Вгц!)и, Рсэсгесе МаСЫепзайсэ 9 (1974), 333-339; 1пдэбапооез МаСЫ. 45 (1983), 125-132. В этой статье доказано, что примитивная сеть сортирует все перестановки мультимножества (пс 1,..., и .
т) тогда и только тогда, когда она сортирует единственную перестановку т' ... 1", Отношение х < у, определено для перестановок х н у таким образом, что означает существование стандартной сети а, такой, что х = уо, и называется порядкам Брюа, аналогичное отношение, но ограниченное только примитивом а, есть слабый порядок Ьрюа (см. ответ к упр. 5.2.1 — 44). 37. Достаточно показать, что егли заменить каждый компаратор операцией езаамиай перестановки, то получится отражающая сеть (гейесйоп пес»рогу), преобразующая (хс,..., х„) в (х„,, гс). Но при такой интерпретации нетрудно проследить путь х» Обратите внимание на то, что перестановка я = (1 2)(3 4)... (2п — 1 2п)(2 3)(4 5)...
(2п — 2 2п — 1) = (1 3 5 ... 2п — 1 2п 2п — 2 . 2) удовлетворяет условию я" = (1 2п)(2 2п-1)... (п — 1 и). Четно-нечетная сортировка с транспозициями была вскользь упомянута Х. Сьювордом (Н. Бепагс() в 1954 голу; она была проанализирована в работах А. СгазэеП1, 1ЯЕ Тралл. ЕС-11 (1962), 483, и Кацзз, 1,ерйС, Юа)»этап, ЫЕЕЕ Тгааэ. С-17 (1968), 443-451. Свойство отражения такой сети было придумано значительно раньше Г. Э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
