Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 87
Текст из файла (страница 87)
23. Соотношения для и,' и и] получаются, если обратить порядок. 2$. (Решение Дж. Шапиро (Н. БЬар1го).) Пусть р и д суть перестановки, такие, что (рп)» = 1» и (йа)» = и». Можно преобразовать р в д за ряд шахов, на каждом из которых выполняется взаимный обмен пар (с, >+1) соседник цшсых; такой взаимный обмен приводит к изменению й-го выхода иа не более чем х1. 26.
Су>пествует кзаимио однозиачиое соответствие, которое сопоставляет элементу (р>,..., р„) из Р„о "последовательность покрмтий"; хбч покрмвает ... покрывает хщ>, где хб> принадлежат В„о; в этом соответствии хо '> = хп> ч еб> тогда и только то>да, когда р> = й Например, (3„1, 4, 2) соответствует такой последовательности; (1, 1, 1, 1) покрывает (1,0, 1, 1) покрывает (1,0,1,0) покрывает (0,0, 1,0) покрывает (0,0,0,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К).
Дальнейшее развитие идея получила в интересной статье Ваг>с( Са1е, Е. М. Катр, Х Согорпгег аале Яузгеш Яс>еле>и 6 (1972), 103-115. Тот факт, что о>ртировка столбцов не нарушает упорядоченность строк, был, вероятно, впервые замечен в связи с обработкой таблиц; гм. Неппапп Воегпег, ВагзЫ1>шб иш Сгпрреп (Брг>пВег, 1955), СЬарсег Ч, 55.) 28. Если (х„,,,г„) суть 1 наибольших элементов, то х„Л... Л х„есть 1-й элемент. если (х„,...,х„) не,являю>псл бми наибольшими элементами, то х„л... л хь меньше 1-го элемента.
29 (х> ЛУ>, (хзЛУ>) Ч(х> Лрз), (хзЛ9>) Ч~(хздйз) Ч(х> Лрз), 9> Ч(хе Лрз) Ч(хзЛРз) Ч(х> Л94), рз 4 (гз Л уз) Ч (хз Л уз) Ч (х> Л уз), Уз Ч (хз Л 34) Ч (гз Л уз) Ч хс, уз Ч (хз Л рз) Ч хз, рз Ч хз). 30. Применив закоиы дистрибутивлости и ассоциативности, можно привести любую формулу к набору членов, связанных операцией Ч, где каждый член представляет собой объединение посредством операции Л исходнык переменных; каноническая форма получается затем с помощью законов коммутативности, идемпотеитности и поглощеиня. Далее, Я,— зто такие множества 5', при которых формула равна 1, если х> = (у б Я); в то же время формула равна О, если х; = (,>' 6 У ) для любого собствениого подмножества Е' множества Я.
31. 5с = 166. В рабате К. СЬпгсЬ, Вийе Мазуь Х 6 (1940), 732-734, показаио, что Юз = 7579, а в работе М. 1>С>аг6, Вп!1. Ашег, Масй. З>с, 52 (1946), 423, — что бе = 7828352 и следуя>шие значения будут такими: б> = 2414682040996, 6з = 56130437228687557907786 [Е. СЬпгсЬ, Жос>сез Ашег. ЛХасй. Яос. 12 (1965), 724; 1.
Ветшав, р. КоЫег, Л(>есш1ппбел Маей. 5еш>паг С>ебеп 121 (1976), 103-124; В. %1ес>ешапп, Огбег 8 (1991), 5-6). Неизвеспсо никакой простой формулы для бь; в работе В, К1е>сшап, Ргос. Ашег. Мас)ь Яос. 21 (1969), 677-682, доказано с помощью очень сложнык рассуждений, что (1Вб„)/(,„'~з>) -> 1 при и -> сю.
32. С>е> является также множеством всех цепочек Вф, где д и»> лежат в С~ и 6 <»~, как векторм, составленные из 0 и 1. Отсюда следует, что С~ есть множество всех цепочек за .. зз~ > из нулей и единиц, где з, < з>, если двоичное представление индекса > "<" двоичного представления у (т. е. оба индекса рассматриваются как векторы из пулей и единиц). Каждмй элемент зе... зз, множества Ст, кроме 00... О и 11... 1, представляет Л Чфуикцию,>(х>,..., 3>) из Рз~ при соогеегстаии >(х>,..., х>) з((х> .. ° х>)2) 33.
Если бы такая сеть существовала, то мм получили бы, что (х>Лхз) Ч(хзЛхз) Ч(хздх4) = У(х> Л хз,х> Ч хз хз, хс) или 7(х> Л хз,хз,х> Ч хз хс) или ... или ~(х>, хз,хз Л хз хз Ч хс) для некоторой функции у. Подставляя (хс,хэ,хз,хс) = (х,х,1,0), (х,0,2,1), (х,1,0,2), (1, х, х, О), (1, х,О, й), (О, 1„х, й), находим, чта такой функции у не существует. 34. Да; доказав это, вы мо.кете взяться за сеть, представленную на рис. 49, при и = 16 (еслн только вьс просто не проверите это на всех двоичных векторах 2", воспользовавшись теоремой 2). 35. В противном случае перестановка, в которой только с и с + 1 находятся не на своих местах,никогда не была бы расгортирована.
Пусть Р» — номера компараторов (»:с+к] в стандартной сети сортировки. Тогда Рс + 2Р» + Р» > 2(п — 2), поскольку должно существовать деа компаратора от (», с+1) до (с+2,»+3) прн 1 < с < и — 3 так же, как (1;2) и (и-1;и). Аналоснчна Рс + 2Р»+ +(»Р» + (5 — 1)Р» с+ + Р»» с ) (с(п — Й). Эта формула предлоксена Дж.
М. Поллардом (1, М. РоИегс1). Можно также доказать, что 2Рс + Р» > 3п — 4. Если удалить первые компараторы вида (2:2 +1) для всех у, то должен существовать, по меньшей мере, еще адин компаратор, размещенный в пределах (с, с+1, с+2) прн 1 < с < и — 2. Аналогично 1»Рс+(»с — 1)Р»+.. +Р» > отх+1)(сс-5)+5(5 — 1). 36. (а) Каждое сравнение соседних элементов уменьшает число инверсий на О или 1, а (п,п — 1,...,1) имеет („) инверсий, (Ь) Пусть а = (1(р:р+1) и будем рассуждать по индукции оо длине а.
Если р = с, то у > р + 1, н (хд)г > (хд)», (хд)»+с > (хд)Р следовательно, (уЯ» > (уб)» и (уО)г+с > (усВ)». Если р = с' — 1, то либо (хЯ», либО (хО)р»с > (хВ)", следовательно, либо (уО)ю либо (уЯрвс > (усу)Р Егли р = у — 1 или 2, рассуждения аналогичны.
Для остальных р доказательство тривиально. Замечанее. Если а является сетью сортировки, то ал — тапсе сеть сортировки (в ней компараторы расположены в обратном порядке). Более общий случай и другое доказательство (с) приведены в работе Х. О, де Вгшуп, Рбвстесе Маг)сешагссв 9 (1974), 333-339; 1лс(абас»алев МЩЬ. 45 (1933), 125 — 132. В этой статье доказано, что примятивиая сеть сортирует все перестановки мучьтимножества (пс 1,..., п»п) тогда и только тогда„ когда она сортирует единственную перестановку и»' ...
1", Отношение х -С у, определено для перестановок х и у таким образом, что означает существование стандартной сети а, такой, что х = уа, и называется порядком Бр»ее; аналогичное отношение, но ограниченное только примитивом а, есть слабый порядок Бр»ее (см. ответ к упр. 5.2. 1-44). 32. Достаточно показать, что еглн заменить каждый кампаратор операцией еваамной пересснаноекв, то получится отражающая сеть (гейесйоп песиог)с), преобразующая (хс,..., х„) в (хь,..., хс), На при такой интерпретации нетрудно проследить путь х».
Обратите внимание на то, что перестановка я = (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 году; она была проанализирована в работах А. Огавве01, ЖЕ Тгапв. ЕС-11 (1962), 433, и Капы, 1 ет1»С, Жа1сзшап, 1ЕЕЕ 7?елв. С-12 (1968), 443 — 451. Свойство отражения такой сети было придумано значительно раныпе Г. Э.
Дыадени (Н. Е. Рас(епеу) в одной яз его головоломок [см. Ашпвешелгв»л Ма»)»ешаг»иж (191»), 193). 38. Вставьте элементы сс...,, сн в первоначально пустую диаграмму, воспользовавшись алгоритмом 5.1,41, но выполнив адно весьма существенное изменение: установите Р„+- х; на шаге 13 только в том случае, если х, ~ Р,с О. Можно доказать, что х, будет равно Рц,,с на этом шаге, только егли г., + 1 = Р„когда входы Н...сл определюот примитивную сеть сортировки.
(Заключенный в «кобкн комментарий придется ссютветственно модифицировать.) После тога как с, будет вставлено в Р, установите Сс»с»- у, как в теореме 5.1,4А. После Ас шагав диаграмма Р всегда будет содержать (г, г + 1,..., и — 1) в строке г, в то время как сг будет представлять собой диаграмму, из которой можно восстановить последовательность Н .., сл, выполняя операции в обратном порядке. Например, если и = 6, то последовательность Н...!л = 413243о43123514 соот- ветствует Транспозиция (4 ссютветствует дополняющей сети [и-!1. и-!1+1]... [и-!я: и-!я+1], ]См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
