Сеть Бетчера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
|definition=
 
|definition=
 
Нуль-единичные битонические последовательности - последовательности вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для <tex>i,j,k\le0</tex>}}
 
Нуль-единичные битонические последовательности - последовательности вида <tex>0^i1^j0^k</tex> или <tex>1^i0^j1^k</tex> для <tex>i,j,k\le0</tex>}}
На первом этапе конструирования стоит задача построить сравнивающую сеть, которая будет сортировать любую нуль-единичную битоническую последовательность - битонический сортировщик.
 
 
[[Файл:Half-Cleaner1.png‎|250px|right|Half-Cleaner для 8 проводов]]
 
[[Файл:Half-Cleaner1.png‎|250px|right|Half-Cleaner для 8 проводов]]
 +
На первом этапе конструирования стоит задача построить сравнивающую сеть, которая будет сортировать любую нуль-единичную битоническую последовательность - битонический сортировщик.<br>
 
Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется <b>''полуфильтром''</b> (half-cleaner). Каждый полуфильтр - сравнивающая сеть глубиной 1, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>i+\frac{n}{2}</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex>.<br>
 
Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется <b>''полуфильтром''</b> (half-cleaner). Каждый полуфильтр - сравнивающая сеть глубиной 1, в которой <tex>i</tex>-й входной провод сравнивается со входным проводом с номером <tex>i+\frac{n}{2}</tex>, где <tex>i=1,2,...,\frac{n}{2}</tex>.<br>
 
{{Лемма|statement=
 
{{Лемма|statement=

Версия 04:38, 15 июня 2011

Эта статья находится в разработке!

Определение

Сеть Бетчера (Batcher odd-even mergesort) - сортирующая сеть размером [math]O(n log^2n)[/math] и глубиной [math]O(log^2n)[/math], где [math]n[/math] - количество элементов для сортировки.

Конструирование сети

Для начала введем понятие битонической последовательности:

Определение:
Битонической последовательностью называется последовательность, которая сначала монотонно возрастает, а затем монотонно убывает, или последовательность, которая приводится к такому виду путем циклического сдвига.

В нашем случае мы будем рассматривать нуль-единичные битонические последовательности:

Определение:
Нуль-единичные битонические последовательности - последовательности вида [math]0^i1^j0^k[/math] или [math]1^i0^j1^k[/math] для [math]i,j,k\le0[/math]
Half-Cleaner для 8 проводов

На первом этапе конструирования стоит задача построить сравнивающую сеть, которая будет сортировать любую нуль-единичную битоническую последовательность - битонический сортировщик.
Битонический сортировщик состоит из нескольких каскадов, каждый из которых называется полуфильтром (half-cleaner). Каждый полуфильтр - сравнивающая сеть глубиной 1, в которой [math]i[/math]-й входной провод сравнивается со входным проводом с номером [math]i+\frac{n}{2}[/math], где [math]i=1,2,...,\frac{n}{2}[/math].

Лемма:
Если на вход в полуфильтр подать битоническую последовательность из нулей и единиц длиной [math]n[/math], то на выходе мы получим две битонические последовательности длиной [math]\frac{n}{2}[/math] такие, что каждый элемент из верхней последовательности не превосходит любой элемент из нижней, и что одна из них будет однородной (clean) - состоящей либо из нулей, либо из единиц.