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

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

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

Значение передается из одной точки в другую по проводу (илге). Провода соединяют выход одного сравнивающего устройства с входом другого; в противном случае они являются либо входными каналами в сеть, либо выходными каналами из нее. В этой главе предполагается, что сравнивающая сеть содержит и входных проводок (шрц( хк(гез) аы аз,..., а„, по которым в сеть поступают сортируемые величины, и и выходных проводов (ои(рш хч(гез) Ьы Ьз,..., Ьп, по которым выдаются вычисленные сетью результаты. Кроме того, мы будем говорить о вход>сой х '= ппп(х, у) у'= мхх(х, у) Рис. 27.1.

Схематические представления сравнивающего устройства Глава 27. Сортирующие сети 801 последовательности (1прщ зес)пенсе) (а~, аз,..., а„) и выходной последовательности (оц1рш зейцепсе) (Ь|, Ьз,..., Ь„), подразумевая под ними наборы величин во входных и выходных проводах. Таким образом, одно и то же название будет использоваться и для проводов, и для значений, которые по ним передаются. Что именно имеется в виду — всегда будет понятно из контекста. На рис. 27.2 показана сравнивающая сеть (сошраг1зоп пепногх), представляющая собой набор сравнивающих устройств, соединенных между собой проводами.

В такой сети п входов изображаются в виде п горизонтальных пиний (йпез), а сравнивающие устройства — вертикальными отрезками. Заметим, что линия представляет не отдельный провод, а последовательность различных проводов, соединяющих разные сравнивающие устройства. Например, верхней линией на рис. 27.2 представлены три провода: входной провод аз, который подсоединен к входу сравнивающего устройства А; провод, соединяющий верхний выход сравнивающего устройства А со входом сравнивающего устройства С„выходной провод Ьз, присоединенный к верхнему выходу сравнивающего устройства С.

Ко входу каждого сравнивающего устройства подсоединен провод, который либо является одним из п входных проводов аз, аз,..., а„, либо присоединен к выходу другого сравнивающего устройства. Аналогично, к выходу каждого сравнивающего устройства подсоединен провод, который либо является одним из и выходных проводов Ьз, Ьз,..., Ь„, либо подсоединен к входу другого сравнивающего устройства. Основной принцип, по которому сравнивающие устройства соединяются между собой, заключается в том, что получившийся в результате граф соединений должен быть ациклическим: если проследить пуп, проходящий от выхода какого-нибудь сравнивающего устройства к входу другого сравнивающего устройства, затем — от его выхода к входу следующего сравнивающего устройства и т.д., то этот путь никогда не должен зацикливаться, дважды проходя через одно и то же сравнивающее устройство. Таким образом, как видно из рис.

27.2, на схеме сравнивающей сети входы можно расположить слева, а выходы — справа; при этом данные в процессе обработки будут продвигаться слева направо. Выходные значения производятся сравнивающим устройством лишь в том случае, когда на его вход подаются обе сравниваемые величины. Например, на рис. 27.2а предполагается, что в начальный момент времени на входные провода последовательности подается последовательность (9,5,2,6). Таким образом, в этот момент времени толью сравнивающие устройства А и В располагают всеми необходимыми входными величинами.

С учетом того что для вычисления выходных значений сравнивающему устройству требуется единичный промежуток времени, сравнивающие устройства А и В выдадут выходные величины в момент времени 1; результат показан на рис. 27.2б. Заметим, что результат в сравнивающих устройствах А и В появляется одновременно, или "параллельно". Далее, в момент времени 1 полным набором входных величин располагают сравнивающие устройства С и В, но не Е.

По истечении еще одного единичного интервала 802 Часть Ч!1. Избранные темы ь, а! ь, ау Ьз аз а! Ь4 Ь4 аг а4 Глубина ! ! б) а) ь, ь, а! ау ь ь аг аг а4 аг Глубина ! ! 2 2 Глубина ! ! 2 2 3 а) г) Рис. 27.2. Сравнивающая сеть на 4 входа и 4 выхода, которая фактически является сортирующей сетью времени, в момент времени 2, выдадут результат сравнивающие устройства С и Р (рис. 27.2в). Они также работают параллельно.

К верхнему выходу сравнивающего устройства С и нижнему выходу сравнивающего устройства Р подсоединены выходные провода 5! и Ь4 сравнивающей сети соответственно. Поэтому в момент времени 2 на эти выходные провода подаются их результирующие значения. В этот же момент времени входные значения подаются на сравнивающее устройство Е, и, как видно из рис.

27.2г, результат выдается на этом сравнивающем устройстве в момент времени 3. Полученные величины передаются по сети по выходным проводам 52 и бз, и теперь вычисление выходной последовательности (2, 5, 6, 9) завершено. Исходя из предположения, что каждое сравнение выполняется в течение единичного промежутка времени, можно определить "время работы" сравнивающей сети, т.е. время, которое требуется для подачи всех выходных значений на выходы сети с момента, когда на ее входы поданы все необходимые сигналы. Это время естественно считать равным максимальному количеству сравнивающих устройств, через которые проходит входное значение на пути следования от входного провода к выходному. Выражаясь более строго, дадим определение глубины (тгерт)у) провода. Глубина входного провода сравнивающей сети равна нулю. Далее, если глубины входных проводов сравнивающего устройства равны Ыи и бю то глубина его выходных проводов равна тпах (с~„Ни) + 1.

Поскольку в сравниваю- Глава 27. Сортирующие сети 803 щей сети отсутствуют циклы, глубина провода определяется однозначно, и можно определить глубину сравнивающего устройства как величину, равную глубине его выходных проводов. На рис. 27.2 показаны глубины изображенных на нем сравнивающих устройств. Глубина сравнивающей сети равна максимальной глубине выходного провода или, что эквивалентно, максимальной глубине сравнивающего устройства. Например, глубина сравнивающей сети, представленной на рис.

27.2, равна 3, поскольку именно этому значению равна глубина сравнивающего устройства Е. Если для вычисления результата каждому сравнивающему устройству требуется единичный интервал времени, и если входные значения подаются в нулевой момент времени, сравнивающее устройство на глубине о выдает результат в момент времени о. Таким образом, глубина сети равна времени, в течение которого сеть обрабатывает входные значения и выдает результат на все выходные провода.

Сортирующая сеть (зотйп8 петттог1с) — это сравнивающая сеть, в которой выходная последовательность является монотонно неубывающей (т.е. выполняется цепочка неравенств 61 < бз « Ь„) для любой входной последовательности. Конечно же, не все сравнивающие сети являются сортирующими, но сеть на рис. 27.2 именно такая. Чтобы понять причину этого, заметим, что по истечении единичного интервала времени минимальная из четырех входных величин появится либо на верхнем выходе сравнивающего устройства А, либо на верхнем выходе сравнивающего устройства В. Поэтому по истечении двух единичных интервалов времени эта величина должна оказаться на верхнем выходе сравнивающего устройства С. Аналогично, по истечении двух единичных интервалов времени максимальная из четырех входных величин появится на нижнем выходе сравнивающего устройства Р.

Все, что остается сравнивающему устройству Е, — это убедиться, что два средних значения займут правильные позиции, что и произойдет в момент времени 3. Сравнивающая сеть напоминает процедуру в том смысле, что она указывает, как должны выполняться операции сравнения, но отличается от нее тем, что ее размер (з(ге), т.е. количество содержащихся в сети сравнивающих устройств, зависит от количества входных и выходных величин. Таким образом, мы должны описывать "семейства" сравнивающих сетей. Например, цель этой главы — разработать семейство эффективных сортирующих сетей ЯОКТЕК. Конкретная сеть в пределах этого семейства задается семейным именем и количеством входов (которое равно количеству выходов).

Например, сортирующая сеть с и входами и и выходами в семействе ЯОКТЕК получает имя БОКТЕК1п1. УПРажНЕНИЯ 27.1-1. Какие значения появятся на всех проводах сети, представленной на рис. 27.2, если входная последовательность имеет вид (9, 6,5,2). Часть Ч!!. Избранные темы 804 Рис. 27.3. Сортирующая сеть, основанная на методе сортировки вставками, лля упражнения 27.1-6 27.1-2. Пусть и — степень двойки. Покажите, как сконструировать сравнивающую сеть глубиной 18п с и входами и и выходами, в которой верхний выходной провод всегда передает минимальное входное значение, а нижний выходной провод — максимальное.

27.1-3. К сортирующей сети всегда можно добавить сравнивающее устройспю таким образом, чтобы в результате получилась сравнивающая сеть, которая не является сортирующей. Покажите, как добавить сравнивающее устройство в сеть, изображенную на рис. 27.2, чтобы получившаяся сеть перестала сортировать все входные перестановки. 27.1-4. Докажите, что глубина сортирующей сети на п входов ограничена снизу величиной 18 и. 27.1-5.

Докажите, что количество сравнивающих устройств в произвольной сор- тирующей сети равно П (и!8 и). 27.1-6. Рассмотрим сортируюшую сеть, изображенную на рис. 27.3. Докажите, что это на самом деле сортирующая сеть и опишите, как ее структура связана со структурой алгоритма, работающего по методу вставок (раздел 2.1). 27.1-7. Сравнивающую сеть на п входов, содержащую с сравнивающих устройств, можно представить в виде списка с пар целых чисел, которые находятся в интервале от 1 до и. Если две пары содержат общее целое число, порядок соответствующих сравнивающих устройств сети определяется порядком пар в списке. Опишите с помощью этого представления (последовательный) алгоритм со временем работы 0 (и+ с), позволяющий определить глубину сравнивающей сети.

* 27.1-8. Предположим, что кроме обычных сравнивающих устройств мы располагаем "перевернутыми" сравнивающими устройствами, минимальное значение в которых поступает на нижний провод, а максимальное— Глава 27. Сортирующие сети 805 на верхний. Покажите, как преобразовать любую сортирующую сеть, содержащую с стандартных и перевернутых сравнивающих устройств в сортирующую сеть, в которой используется с стандартных сравнивающих устройств. Докажите корректность предложенного метода преобразования.

27.2 Нуль-единичный принцип Нуль-едыничный нриныыл (хего-опе рппс1р!е) утверждает, что если сортировочная сеть правильно работает для всех наборов входных величин, составленных из элементов множества (О, 1), то она правильно работает для любых входных чисел. (Эти числа могут быть целыми, действительными или любым другим подмножеством величин, извлеченных из произвольного линейно упорядоченного множества.) При построении сортирующих сетей или других сравнивающих сетей нуль-единичный принцип позволяет ограничиться операциями, выполняющимися над последовательностью, составленной только из нулей и единиц. Построив сортирующую сеть и доказав, что с ее помощью сортируются все последовательности из нулей и единиц, мо1кно обратиться к нуль-единичному принципу и доказать, что она надлежащим образом сортирует последовательности, составленные из произвольных величин. Доказательство нуль-единичного принципа основано на понятии монотонно неубывающей функции (раздел 3.2).

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

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