Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 166

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 166)

Лемма 27.1. Если сравнивающая сеть преобразует входную последовательность а = (аг, аз,..., а„) в выходную последовательность Ь = (Ь1, Ьз,..., Ь„), то для любой монотонно неубывающей функции 7" эта сеть преобразует входную последовательность Г (а) = (7" (ат), 7 (аз),..., Г (а„)) в выходную последовательность 7 (Ь) = (7 (Ьг), 7 (Ьз),..., 7 (Ь„)). Доказательство. Сначала докажем, что если функция г" монотонно неубывает, то отдельное сравнивающее устройство с входными значениями г" (х) и Г (у) выдаст результат 7' (плп (х, у)) и Г (шах (х, у)). Затем докажем лемму по индукции.

Чтобы доказать сформулированное выше утверждение, рассмотрим сравнивающее устройство, на вход которого подаются величины х и у. Верхнее выходное значение такого устройства равно пйп (х, у), а его нижнее выходное значение — шах (х, у). Предположим, что теперь на вход сравнивающего устройства подаются значения 7" (х) и 7" (р) (рис. 27.4). На верхний выход сравнивающего устройства выдается значение шш (7' (х), 7 (у)), а на нижний выход — значение шах ( Г (х), 7" (р) ). поскольку функция г монотонно неубывающая, из неравенства Часть ЧП. Избранные темы 806 /(х) пспу(х)яу)) /(ппп(х,у)) У(у) мппК(х),/(у)) =айвах(х, у)) Рис. 27.4. Работа сравнивающего устройства, иллюстрирующая доказательство леммы 27.1; функция Г' — монотонно неубывающая х < у следует неравенство 7" (х) < 7" (у).

Следовательно, выполняются тождества ппп (7' (х), 7" (у) ) = 7 (ппп (х, у) ), шах (( (х), 7" (у)) = 7" (шах (х, у)) . Таким образом, если на вход сравнивающего устройства подать значения 7"(х) и ( (у), то на его выходе получим значения ппп (7" (х), ( (у)) и )пах(7'(х), ~ (у)). На этом доказательство утверждения завершается. Методом индукции по шагам продвижения вглубь по каждому проводу в сравнивающей сети общего вида можно доказать более сильное утверждение, чем то, юторое сформулировано в лемме.

Оно заключается в том, что если какой-нибудь провод получает значение а, в результате подачи в сеть входной последовательности а, то при подаче входной последовательности 7"(а) он получает значение ( (а;). Поскольку в этом утверждении идет речь обо всех проводах, в том числе и о выходных, его доказательство станет доказательством леммы.

В качестве базиса индукции рассмотрим провод на глубине О, т.е. входной провод а;. Результат получается тривиальным образом: если на вход сети подается сигнал 7" (а), то по входному проводу передается сигнал 7'(а,). В качестве шага индукции рассмотрим провод, расположенный на глубине (( > 1. Этот провод является выходным в'сравнивающем устройстве, расположенном на глубине ((, а входные провода этого устройства находятся на глубине, строго меньшей (1. В соответствии с гипотезой индукции, если входные провода сравнивающего устройства передают сигналы а( и а при подаче в сеть входной последовательности а, то при подаче входной последовательности 7".

(а) они передают сигналы У(а,) и 7 (ау). Согласно доказанному ранее утверждению, выходные провода рассматриваемого сравнивающего устройства передают сигналы 7" (пйп(а;, а )) и 7'(шах(а;, а )). Так как при подаче в сеть входной последовательности а они передают сигналы пйп (а;, а ) и шах (аа а ), то лемма доказана. И В качестве примера применения леммы 27.1 рассмотрим рис. 27.5. Сортирующая сеть, изображенная в части а этого рисунка, идентична той, что показана на рис. 27.5. В части б этого рисунка показана эта же сеть в ситуации, ко)па ее входная последовательность образована путем применения к входной последовательности из части а монотонно неубывающей функции (' (х) = (х/2~1.

Глава 27. Сортирующие сети 807 ь, ь, а1 а| Ь2 аг ь, аз аз а4 а4 а) Рис. 27.5. Применение неубывающей функции ко входу сортнрующей сети Если сравнивающая сеть является сортирующей, то лемма 27.1 позволяет доказать сформулированное ниже замечательное утверждение. Теорема 27.2 (Нуль-единичный принцип). Если сравнивающая сеть с и входами правильно сортирует все 2" возможных последовательностей, состоящих из нулей и единиц, то она правильно сортирует все последовательности чисел произвольного вида.

Доказалаельслаео. Предположим, что это не так, и сеть сортирует все нуль-единичные последовательности, но существует последовательность, состоящая из произвольных чисел, которую сеть не может правильно отсортировать. Другими словами, существует входная последовательность (ам аз,... а„), которая содержит элементы а; и а., связанные соотношением а; ( а„но после прохождения сети значение ау расположено в выходной последовательности перед значением вь Определим следующую монотонно неубывающую функцию 7": (О при х ( а,, г" (х) = (1 прих>аь Поскольку в выходной последовательности сеть помешает значение а~ перед значением ан если на вход подается последовательность (ам аз,...а„), то из леммы 27.1 следует, что она разместит значение г"(а ) перед значением 7"(а,) в выходной последовательности, если на вход сети подается последовательность (7" (а1),7" (аз),..., Г(цв)). Но так как Яау) = 1 и Г(еа) = О, мы приходим к противоречию, что сеть не в состоянии правильно отсортировать нуль-единичную последовательность (У (а1), 1".

(аз),..., Г (а„)). И Упражнения 27.2-1. Докажите, что в результате применения монотонно неубывающей функции к отсортированной последовательности получится отсортированная последовательность. Часть Ч11. Избранные темы 808 Ь, Ь2 Ьз Ь4 а, аа а3 а4 Рис. 27.6. Сортируюшая сеть, предназначенная для сортировки четырех чисел 27.2-2. Докажите, что сравнивающая сеть с г4 входами правильно сортирует входную последовательность (44, п — 1,..., 1) тогда и только тогда, когда она правильно сортирует нуль-единичные последовательности (1, О, О,...

0,0), (1,1,0,...,0,0),..., (1,1,1,...,1,0), состоящие из и — 1 членов. 27.2-3. Докажите с помощью нуль-единичного принципа, что сравниваюшая сеть, показанная на рис. 27.6, является сортируюшей. 27.2-4. Сформулируйте и докажите утверждение, аналогичное нуль-единичному принципу, для модели дерева решений. (Указание: не забудьте корректно обработать равенство.) 27.2-5. Докажите, что для всех г = 1,2,..., и — 1 в сортирующей сети на и входов между г-й и (г + 1)-й линиями должно содержаться по крайней мере одно сравнивающее устройство.

27.3 Битоническая сортирующая сеть Первый этап конструирования эффективной сортируюшей сети состоит в том, чтобы построить сравнивающую сеть, которая может сортировать любую битоническую последовательность (ойоп4с зе41цепсе): последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига. Примерами битонических последовательностей являются последовательности (1, 4, 6, 8, 3, 2), (6,9,4,2,3,5) и (9,8,3,2,4,6). Любая последовательность, состоящая всего из одного числа или двух чисел, является битонической.

Такие последовательности представляют собой своего рода граничный случай. Нуль-единичные битонические последовательности обладают простой структурой. Они имеют вид 0'130" или 1'Ф1" для некоторых ь,у,4Ь > О. Заметим, что последовательность, которая либо монотонно возрастает, либо монотонно убывает, — тоже битоническая. Битонический сортировщик, который нам предстоит сконструировать, представляет собой сортирующую сеть, которая сортирует битонические последовательности, состояшие из нулей и единиц. В упражнении 27.3-б предлагается по- Глава 27. Сортирующие сети 809 казать, что битоннческий сортировщик может сортировать бнтонические после- довательности, образованные произвольными числами.

Полуфильтр Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется полуООильтрам (Ьа!Г-с1еапег). Каждый полуфильтр — это сравнивающая сеть глубиной 1, в которой а'-я входная линия сравнивается со входной линией под номером т'+ и/2, где а = 1,2,...,п/2. (Предполагается, что ть— четное.) На рис. 27.7 показана сеть НА!.Б Сьялмвк[8], — полуфильтр на 8 входов и 8 выходов, и приведены два примера нуль-единичных входных и выходных наборов значений. Если входные последовательности — битонические, то каждый элемент из верхней половины выходной последовательности не превышает значения любого элемента из нижней половины этой последовательности.

Кроме того, обе половины образуют битонические последовательности. Если на вход полуфильтра подается битоническая последовательность из нулей и единиц, то на его выход выдается последовательность, в которой меньшие значения расположены в верхней половине, большие — в нижней половине, причем обе половины образуют битонические последовательности. По крайней мере одна из половинных подпоследовательностей выходной последовательности является однородной (с1еап) — состоящей либо из нулей, либо из единиц.

Именно благодаря этому свойству такая сеть получила название "полуфильтр". (Заметим, Битоническаа О однородная О последовательность ! Битоническая 1 ! послеловательность 1 Битоническвя последовательнопь О О Битоническвя 1 последовательность О 1 Битоническая оанормиая последовательность 1 Битоническая последовательность Рис. 27.7. Сравнивающая сеть Ндьр Сьвднвк[8] Часть Ч11. Избранные темы 810 что все однородные последовательности — битонические.) В сформулированной ниже лемме доказываются эти свойства полуфильтров.

Характеристики

Список файлов книги