Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 88
Текст из файла (страница 88)
А. 1 вясоэх, М. Р. БсЬйэяепЬегйег, Сошргаэ Еелдпэ Асад. Бей Рапз (!) 295 (1982), 629 — 633! Н, Р. Бсап1еу, Еиг. Х СошЫпаеог!сэ 5 (1984), 359-372; Р. Н. Еде1шап, С. Сгеепе, Адгапсеэ !п МагЬ. 63 (1987), 42 — 99.] Диаграммы примитивных сетей сортировки также соответствуют организации псевдолиний и других абстракций при двумерном представлении сложности сетей. Более подробно об этом речь илет в работе 11.
Е, КппэЬ, Ъессоге Мо!ез !и Сощр. Бей 606 (1992). 39, Если, например, я = 8, то такая сеть должна включать показанные здесь компараторы. Все другие компараторы не будут задействованы в наборе 10101010. Тогда линии [и/3] .. [2п/3] = 3, . б сортируют 4 элемента, как и в упр. 37. (Это упражнение базируется на идее Дэвида Б.
Уилсона (11ат!д В. %!)эоп).) Замечание. Существует взаимно однозначное соответствие между примитивной сетью минимальной длины, которая сортирует данную цепочку битов, и диаграммами Юнга, вид которых ограничен зигзагообразным путем, определенным этой цепочкой битов. Таким образом, из упр. 38 следует взаимно однозначное соответствие между примитивной сетью из ( Гг+'] компараторов, которая сортирует (10)" ~~, и примитивной сетью из ("Г~~+') компараторов, которая сортирует и/2+ 1 произвольных чисел.
Если примитивная сеть сортирует цепочку битов 1эгг0"~г, можно сделать следующий вывод: все ее "половинки", состоящие из подсетей с линиями от Ь до Ь+ и/2 включительно, также являются сетями сортировки при 1 < Ь < и/2. (См. также теорему де Брейна, которая цитируется в ответе к упр. 36,) 40. Это вытекает из применения неравенств относительно конечных членов интересующе. го нас построения, которые представлены в п. 7 статьи Н.
Бовь, Яе!гзсЬг!й' йуг ИгайгясЬе!л!!сЬЬшйягЬеогю пвд гегяипдге СеЫеге 58 (1981), 41-53. В ней положено Ь = -', а = -' и 1 = 4я+ ь/и 1п и. Эксперименты показали, что ожидаемое время достижения любой примитивной сети сортировки — ие обязательно по методу пузырька — очень близко к 2п .
Кстати, э Р. П. Стэнли (Б.. Р. Бгап1еу) н С. В. Фомин доказали, что если компараторы [!ь:гь+1] выбираются не с равной вероятностью, а таким образом, что гь = д возникаег с вероятностью д/("), то соотвегствукяцее ожидаемое время становится точно равным (э] Н( ) . 42.
Должен существовать путь длиной [!8 и] или больше из некоторого входа в наибольший выход (рассмотрите ш„в теореме А). Если поместить иа этот вход оо, то поведение всех компараторов на этом пути будет предопределено, а оставшаяся сеть должна быть (и — 1)-озртировщнком. [ХЕЕЕ Тгалэ. ол Соглрисегз С-21 (1972), 612-613.] 45.
После ! уровней вход х| может оказаться в не более чем 2' разных местах. После завершения слияния э:1 может оказаться в и + 1 разных местах. 46. [См. Х А!8опгЬтя 3 (1982), 79-88; приведенное ниже доказательство предложено В. С. Гринбергом.) Можно предположить, что 1 < гп < и и что на любой стадии выполняется т сравнений. Пусть ! = ] (и — ш)/2], и предположим, нужно выполнить слияние хг « я~ с 91 < < 9„.
Противник может принудить выполнить [!8(гп+ и)] стадий следующим образом: на первой стадии некоторое я! сравнивается с элементом уь, причем либо и < 1, либо !с > !+ гл. Противник решает, что х»-с < ус и х»»с > у„, а также, что х! > у», ехли и < 1, и х~ < у», если (с > 1+ т. Остальная часть задачи — это, по сути, слияние х! либо с у»»с « у, либо с ус « у»-с.
Таким образом, остается, по крайней мере, ппп(п — !г+1,!с) > ппп(п — !+1,!+т) = [(си+и)!'2] исходов. Отсюда следует, что необходимо не менее чем [18[(сл + и)!с2]] = [18(т + и)] — 1 последующих стадий. 48. Пусть и — наименьший элемент среди (ха), а ус~с — любой вектор из множества Р„, такой, что из (ууи)» = О следует, что (ха)» содержит элемент < и, а из (укй)» = 1 следует, что (ха)» содержит элемент > и. Если а = В[р:с!], то можно найти вектор ус с, удовлетворяющий тому же условию, в котором а заменено элементом су, и такой, что ус»с[у.д] = уйн начав с (у! 1), = 1, (уОО)с = О, мы, в конце концов, получим вектор у = у01, удовлетворяющий требуемому условию. Ж.
Боде (О. Вапс(ес) и Д. Стивенсон (Р. Бсетепеоп) заметили, что из комбинации результатов упр. 37 и 48 следует простой метод параллельной сортировки с (п)пи)!'!с + О(п) циклами сравнения на А процессорах. Для этого следует сначела рассортировать !с подфайлов размером < [и!'!с], а затем слить их за я проходов, используя "четно-нечетное слияние с транспозициями" порядка й. [1ЕЕЕ Т1'алз. С-27 (1978), 84 — 87.] 49. Как (х уу) ух, так и хс! (у»(х) представляют собой наибольшие т элементов мультимновсества хсо у осх; (х !» у) !»» и х )с (у!с») представляют собой наименьшие т элементов. Еслихы у= »= [О,Ц то(х!1»)у(уй») =(хйу)у(х![»)у(у)1») = (0,0),вто время как среднке элементы в [О, О,О, 1, 1, Ц суть (О, Ц.
Из анализа сети сортировки для трех элементов и результатов упр. 48 следует, что средние элементы х Ю у !сс х могут быть выражены либо хак ((хуу))[х) у(х)[у), либо как ((х![у)Я») !»(хуу), либо с помощью любой другой формулы, получаемой путем перестановки переменных х, у, х в этих выражениях. (По-видимому, для средних элементов симметричной формулы не существует.) 60. Точно так, как в теореме Е, можно найти все тоясдества, удовлетворяемые операцией х у у = ппп(х+у,1), х й у псах(О, х+у-1) на множестве рациональных чисел х, у в диапазоне [О ..
1]. [Это операция спереливания*' как можно большего количества жидкости из одного стакана, в который налиты х, в другой, в который ранее были налиты у, что подмечено Дж. М, Поллардом (1. 61. Ройвгд).] Все такого рода тождества можно получить из системы четырех аксиом и правила интерференции для многозначной логики Лукашевича ()л»)сэя(евчсз); см. также работу Козе, Еоэ»ег, Тгапк Ашег. Мв»)с. Бог. 87 (1958), 1-53. 61. Пусть а' = а[с:Я, а )с — произвольный индекс з» 1,11 Если (ха); < (ха)» при всех х, то (ха'), < (ха )»; если (ха)» < (ха), и (ха)» < (ха) при всех х, тогда то же самое имеет место, если заменить а элементом а; если (ха)» < (ха), при всех х, то (ха )» < (хап)с.
Таким образом, мы видим, что для а' существует, по крайней мере, столько же соотношений, сколько для а, плюс еще одно, если [с:2] не является избыточным. [Вей Яузсеш Тес)с. Х 49 (1970), 1627-1644.] 62. (а) Будем рассматривать сортировку нулей и единиц. Пусть со = хо+хс+. +хи, Сеть не выполнит работу тогда и только тогда, когда ш < 1 и хо = 1, прежде чем завершится М-сортировка. Если в этот момент хо = 1, то в начале должна была быть единица и прн 1 < с < и мы должны были в начале иметь либо хг с»»„» = 1 при О < (с < т, либо хэг»»„» = 1 при О < й < т; таким образом, ш > 1+ (си+ 1)п = Ф.
Итак, отказ СаядвтЕЛЬСтяувт О тОМ, Чта СО = Ф И Х» = Хз+»ь» Прн 1 < и < т И Х»1 = й»1-С Прн 1 < ! < И. Более того, специальная подсеть должна преобразовать этя входы таким образом, что х»м+» +1 = 1 при 1 < 1 < т. (Ь) Например, специальная подсеть для (уг Ч уз Ч уз) Л (уг Чуз Чуз) Л... могла бы бьгть [1+ 2п:2тп+ 2н+ 1)[3+ 2п:2гпп+ 2н+1Н6+ 2п:2тп+ 2п+ 1) [4+ 4н: 2пзп+ 2п+ 2)[5+ 4п: 2глп+ 2п+ 2)[8+ 4п.2глп+ 2п+ 2)..., вели испольэовать хгг г+гз» и хзг+зь для представления уг и уг в й-м подвыраяеении и хгмтг ~ез — для представления самого этого выражения. 63. Раскрасьте все линии красным или синим цветом в соответствии со следующим пра- вилом: цвет в случае (Ь) красный красный синий синий если з пкя1 4 равно 0 1 2 3 тогда цвет линии г в случае (а) красный синий синий красный Теперь вы увидите, что первые г — 1 уровней сети состоят нз двух отдельных сетей: олив из 2' ' красных линий, а другая — из 2' ' синих линий.
Компараторы на Рм уровне образуют сеть слияния, как в сетях битонного или четио-нечетного слияния. Таким образом, мы получили искомый результат при й = 1. Красно-снняя декомпозиция также годится и для случая й = 2. Если вход 4-упорядочен, красные линии содержат 2' ' чисел, которые являются 2-упорядочеинымн; то же самое можно сказать относитеяьно синих линий. Так что мы оказались в ситуации с хоуоугхгхгугузхз...
(случай (а)) нли хохгуоугхзхзузуз .. (случай (Ь)) после 1 — 1 уровней; окопчательнмй результат (холуо)(хочуо)(углхг)(узчхг)... или хо(хглуо)(хгчуо)(ьч ляг)(узчхг) ° ,»2.-1 ! ащ 11 о +2 совершенно очевидно является 2-упорядоченным. Теперь для й > 2 можно предположить, что й < г. Первые г — й+ 2 уровней г-зтг раздезщются в результате декомпозиции на 2» г отдельных сетей размером 2», каждая из которых является 2-упорядоченной в случае й = 2; следовательно, линии являются 2ь '- упорядоченными после г — й+ 2 уровней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
