AOP_Tom3 (1021738), страница 189
Текст из файла (страница 189)
Дьюдени (Н. Е Рпс(епеу) в одной нз его головолол»ок [см. Аписэешессгэ сп МаСЫесааС!сэ (1917), 193!. 38. Вставьте элементы зс, ..., Ся в первоначально пустую диаграмму, воспользовавшись алгоритмом 5.1.41, но выполнив одно весьма существенное изменение: установите Р, »- х, на шаге 13 талька в том сяучае, если х, ~ Рц, О. Можно доказать, что х, будет равно Рс„,! на этом шаге, только егли хс + 1 = РЗ, когда входы сс...
сл определяют примитивную сеть сортировки. (Заключенный в скобки комментарий придется соответственно модифицировать ) После того как Сз будет вставлено в Р, установите Щз»- 71 как в теореме 5.1.4А. После Ар шагов диаграмма Р всегда будет содержать (г,г+ 1,...,п — 1) в строке г, в та время как бр» будет представлять собой диаграмму, из которой можно восстановить последовательность В...
Ся, выполняя операции в обратном порядке. Например, если и = 6, то последовательность Н ... гм = 41 3 243 543123514 соот- ветствует Транспозиция Я соответствует дополняющей сети (и — Н:и-В+1]., (и — !н:п — !и+1]. ]Слс А. 1 авсопх, М. Р. БсЬйекепбегбег, Сошргез Непдпэ Асад.
Ясс РагВ (1) 296 (1982), 629.-633; В,. Р. Ягап!еу, Еиг. Х СошЫпагогкэ 6 (1984), Зо9-372; Р. Н. Еде!шап, С. Сгеепе, Адгапсеэ !и ЛбагЛ. 63 (1987), .42 — 99.] Диаграммы примитивных сетей сортировки также соответствуют организации псевдолнннй и других абстракций при двумерном представлении сложности сетей.
Более подробно об этом речь идет в работе О. Е. КппсЬ, Лесепса №Геэ ш Сошр. Ясй 806 (1992). 39. Если, например, и = 8, то такая сеть должна включать показанные здесь компараторы. Все другие компараторы не будут задействованы в наборе 10101010 Тогда линии ]и/3]. ]2п/3] = 3..6 сортируют 4 элемента, как и в упр. 37. (Это упражнение базируется на идее Дзвида Б. Уилсона (БагЫ В. И'йвоп).) Замечание. Существует взаимно однозначное соответствие между примитивной сетью минимальной длины, которая сортирует данную цепочку битов, н диаграммамн Юнга, внд которых ограничен зигзагообразным путем, определенным этой цепочкой битов. Таким образом, из упр. 38 следует взаимно однозначное соответствие между примитивной сетью из ("7~~~) компараторов, которая сортирует (1О)"~, и примитивной 2 сетью из ("~~ ') компараторов, которая сортирует и/2 + 1 произвольных чисел.
Если ~э 2 72 примитивная сеть сортирует цепочку битов 1Ш~О" 7, можно сделать следующий вывод: все ее "половинки", состоящие из подсетей с ливиями от Л до Л + и/2 включительно, также являются сетями сортировки при 1 < Л < и/2. (См. также теорему де Брейна, которая цитируется в ответе к упр 36.) 40. Это вьшекает из применения неравенств относительно конечных членов интересующего нас построения, которые представлены в п. 7 статьи Н. Наес, Зе!гэсЛгИ /Лг ИаЛгвсЛе!и!!сИсишсйеог!е апд гегвчшдге Себ!еге 68 (1981), 41-63 В ней наложено Ь = -', а = -' и ! = 4п+,/и 1и ть Эксперименты показали, что ожидаемое время достижении любой примитивной сети сортировки — не обязательно по методу пузырька — очень близко к 2п . Кстати, э Р. П.
Стэнли (Н. Р. Бсап!еу) н С. В. Фомин доказали, что если компараторы ((ь: !я 91] выбираются не с равной вероятностью, а таким образом, что (ь = / возникает с вероятностью //("), то соответствующее ожидаемое время становится точно равным (") Н( ). 42. Должен существовать путь длиной (!8 п] или больше из некотарага входа в наибольший выход (рассмотрнте т„в теореме А). Если поместить на этот вход оо, то поведение всех компараторов на этом пути будет предопределено, а оставшаяся сеть должна быть (и — 1)-сортнровщиком.
(1ЕЕЕ Тгаое. оп Сошрисеш С-21 (1972), 612-613.] 46. После ! уровней вход х~ может оказаться в не более чем 2' разных местах. После завершении слияния к! может оказаться в и+ 1 разных местах. 46. (См. 3, А!8огЫЬпгв 3 (1982), 79-88 приведенное ниже доказательство предложено В. С. Гринбергом.] Можно предположить, что 1 < т < и и что на любой стадии выполняется т сравнений. Пусть ! = ] (и — т)/2], и предположим, нужно выполнить слияние х~ < . < х с р~ < < 9 . Противник может принудить выполнить (!8(т -Ь и)] стадий следующим образом; на первой стадии некоторое х„сравнивается с элементом рю причем либо й < 1, либо й > 1+ ти.
Противник решает, что х»» < у» и х т» > у, а также> что х ) у», если й < 1, и х» < у», если !с > 1+ иь Остальная часть задачи — это, по сути, слияние х» либо с у»»» « у„, либо с у~ < < у»», Таким образом, остается, по крайней мере, ппп(и — й-»-1, й) > ппп(и — !+1, !+та) = [(т + и)/2] исходов. Отсюда следует, что необходимо не менее чем [!8[(гл, + и)/2]] = [!8(т + и)] — 1 последующих стадий. 48. Пусть и — наименьп»ий элемент среди (ха)», а у ! -- любой вектор из множества !о! П„, такой, что из (ую»)» = 0 следует, что (ха)» содержит элемент < и, а из (уйл)» = 1 следует, что (ха)» содержит элемент ) и.
Если а = /![р:д], то можно найти вектор у!'1, удовлетворяющий тому же условию, в котором а заменено элементом )3, и такой, что уц![рьу] = ую!. Начав с (у!э!), = 1, (уйй), = О, мы, в конце концов, получим вектор у = уй», удовлетворяющий требуемому условию. Ж. Боде (С. Вапбе!) и Д Стивенсон (11. Я»етеввоп) заметили, что из комбинации результатов упр. 37 и 48 следует простой метод параллельной сортировки с (и1п и)/й + О(»») циклами сравнения на й процессорах. Для этого следует сначала рассортировать й подфайлов размером < [и/й], а затем слить их за й проходов, используя "четно-нечетное слияние с транспозицнями" порядка й.
[!ЕЕЕ Тгалк С-27 (1978), 84 — 87.] 49. Как (х у у) ух, так и ау (у у х) представляют собой наиболыпие т элементов мульти- множества х О» у Ш х; (х /! у) /! х и х /[ (у /[ х) представляют собой наименьшие т элементов. Если х = у = х = (О, !], то (х д х) у (у )т х) = (х )з у) у (х г» х) у (у /» х) = [О, 0), в то время как средние элементы в [0,0,0,1,1,1) суть (0,1]. Из анализа сети сортировки для трех элементов и результатов упр. 48 следует, что средние элементы х Ш у Э! могут быть выражены либо как ((хуу)]эх)у(х/[у), либо как ((хду)ух)][(хуу), либо с помощью любой другой формулы, получаемой путем перестановки переменных х, у, х в этих выражениях.
(По-видимому, для средних элементов симметричной формулы не существует.) 80. Точно так, как в теореме Е, можно найти все тождества, удовлетворяемые операцией хну = ш!п(х+у,1), х]! у = п»ах(О,х+у — 1) на множестве рациональных чисел х, у в диапазоне [О .. 1]. [Это операция "переливания" как можно большего количества жидкости из одного стакана, в который налиты х, в другой, в который ранее были налиты у, что подмечено Дж. М Поллардом (Е М.
Ро!!агд).] Бсе такого рода тождества можно пачучить из системы четырех аксиом и правила интерференции для многозначной логики Лукашевича (Бпйав!е»г!сз); см. также работу Нове, Ноээег, Тгапэ. Атег. Ма»Л. Вес. 87 (1958), 1-53, 81. Пусть а' = а[~':у], а й — произвольный индекс ~ й/. Если (ха), < (ха)» при всех х, то (ха'), < (ха')»; если (ха)» < (ха)» и (ха)» < (ха)! при всех х, тогда то же самое имеет место, если замеяить а элементом а; е»ши (ха)» < (ха), при всех х, то (ха )» < (ха')„.
Таким образом, мы видим, что для а' существует. по крайней мере, столько же соотношений, сколько для а, плюс еще одно, если [»:у] не является избыточным [Ве!! Яуз»еш ТесЛ.,1. 49 (1970), 1б27-1б44.] 62. (а) Будем рассматривать сортировку нулей и единиц. Пусть ш = хе+в»+ . +хл. Сеть не выполнит работу тогда и только тогда, когда ш < ! и хе = 1, прежде чем завершится Х-сортировка. Если в этот момент хе = 1, то в начале должна была быть единица и при 1 < ! < и мы должны были в начале иметь либо хм»»»в» = 1 при 0 < й < ш, либо хштз„» = 1 при О < й < иц таким образом, ш > 1+ (гл+ 1)г» = й Итак, отказ свидетельствует о том, что ш = ! и х! = х»»э,» при 1 < й < т и хз» = х»»» при 1 < ! < и.
Более того, специальная подсеть должна преобразовать эти входы таким образом, что х» тхвт» — 1 при 1 ( ! ( щ. (Ь) Например, специальная подсеть для (у! Чу! Ч уз) Л(угу уз Чу!) Л... могла бы быть [1 + 2и ! 2!пи + 2и + 1ЦЗ + 2и ! 2иси + 2и + 1[[6 + 2и: 2ти + 2и + 1[ [4 + 4и. 2ти+ 2и + 2[[5 -1- 4и: 2ти+ 2и + 2[[8 + 4и: 2ти + 2и + 2]... если использовать хг, !хо!„и хг,еы„для представления у, и у, в й-м подвыражении и хг хг э.о .-- для представления самого этого выражения.
53. Раскрасьте все линии красным или синим цветом в соответствии со следующим пра- вилом: цвет в случае (Ь) красный красный с.иний синий если ! тес(4 равно 0 1 2 3 тогда цвет лизин с' в случае (а) красный синий синий красный Теперь вы увидите, что первые 1 — 1 уровней сети состоят из двух отдельных сетей: одна из 2 красных линий, а другая - - из 2' синих линий. Компараторы на Ьм с-! с — ! уровне образуют сеть слияния, как в сетях битонного или четно-нечетного слияния. Таким образом, мы получили искомый результат при 1с = 1. Красно-синяя декомпозиция также годится и для случая )с = 2. Если вход 4-упорядочен, красные линии содержат 2' ' чисел, которые являются 2-упорядоченными; то же самое можно сказать относительно синих линий.
Так что мы оказались в ситуации с хоуоусхсхгугузхз .. (случай (а)) или хохсуоусхгхзугуз . (случай (Ь)) после ! — 1 уровней; окончательный результат (хоЛуо)(хоЧуо)(усЛх!)(усЧх!)... или хо(хсЛуо)(хсЧуо)(усЛхгНусЧхг).. совершенно очевидно является 2-упорядоченным. Теперь для Ь > 2 можно предположить, что Ь < !.
Первые 1 — Й + 2 уровней с-сэг разделяются в результате декомпозиции на 2! г отдельных сетей размером 2 +, каждая из которых является 2-упорядоченной в случае Ь = 2; следовательно, линии являются 2" с-! упорядоченными после 1 — Ь+ 2 уровней. Последую!дне уровни, очевидно, сохраняют 2 упорядочение, поскольку они обладают "вертикальной" периодичностью порядка 2 (Можно представить себе — оо на линиях — 1, — 2, ... и +ос — на линиях 2, 2 + 1, ....) с с Литература. Сеть (а) впервые была рассмотрена в работе М Ропс1, У. Рег!, Ь. Пасло)рЬ, М. Яа1сэ, 3АСМ 36 (1989), 738-757; сеть (Ъ) в работе Е. К Сапбе1с), Б. С Ч'!111атэоп, Ъспеаг апс1 Мв)сс)спеаг А!Оебга 29 (1991), 43-51.
Исстересно отметить, что в случае (а) имеем Р и = Сс, где Сс определено в упр. 32 [Дауд и др., теорема 17[; таким образом, изображения Р самого по себе недостаточно для того, чтобы охарактеризовать поведение периодической сети. 54. Следующее построение выполнено в работе А)!ас, Косо!бэ, Ягепсегебб [РОСЯ 33 (1992), 686 — 692]. Ово показывает, как рассортировать сиз элементов с четырьмя уровнями тгэлементных сортироюциков: предположим, что сортируемые элементы суть нули и единицы; пронумеруем линии (а,Ь,с) = асио+ Ьси+ с при 0 < а,б,с < т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
