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