Материал из Викиконспекты
Есть два способа проверить сеть из n компараторов на то, что она сортирующая.
Первый, наивный способ - перебрать все перестановки из n элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует [math] O(n! \cdot Comp(n)) [/math] действий, где [math] Comp(n) [/math] - количество компараторов в сети из n элементов. Обычно это количество можно оценить как [math] n^2 \log n [/math](сеть Бэтчера), то есть получаем асимптотику [math] O(n! n^2 \log n) [/math], то есть при n, равном уже 10, проверить сеть очень проблематично.
Второй способ основывается на предположении что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Докажем это.
| Определение: |
| Функция [math] f [/math] из A в B называется монотонной, если [math] \forall a_1, a_2 \in A : a_1 \le a_2 \Rightarrow f(a_1) \le f(a_2) [/math] |
| Лемма: |
Пусть [math] f: A \rightarrow B [/math] - монотонная. Тогда [math] \forall a_1, a_2 \in A: f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) [/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Не теряя общности, предположим что [math] a_1 \le a_2 [/math]. Тогда, [math] f(\min(a_1, a_2)) = f(a_1) [/math]. Также, по монотонности, [math] f(a_1) \le f(a_2) [/math]. Тогда [math] \min(f(a_1), f(a_2)) = f(a_1) [/math]. То есть, [math] f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) = f(a_1) [/math]. Такие же рассуждения можно провести для случая [math] a_2 \lt a_1 [/math]. |
| [math]\triangleleft[/math] |
| Определение: |
| Рассмотрим отображение [math] f: A \rightarrow B [/math] и последовательность [math] a = (a_0, a_1, \dots, a_{n-1}) [/math]. Определим [math] f(a) [/math] как последовательность [math] f(a_0), f(a_1), \dots , f(a_{n-1}) [/math], то есть [math] f(a_i) = f(a)_i [/math] |
| Лемма: |
Пусть [math] f: A \rightarrow B [/math] - монотонная, а [math] N [/math] - какая-то сеть компараторов. Тогда [math] N [/math] и [math] f [/math] коммутируют: [math] N(f(a)) = f(N(a)) [/math] - другими словами, неважно, применить сначала [math] f [/math] к [math] a [/math] и пропустить через сеть [math] N [/math], или пропустить через сеть [math] N [/math] последовательность [math] a [/math], а потом применить монотонную функцию [math] f [/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим произвольный компаратор [math] [i: j] [/math], сортирующий элементы [math] a_i [/math] и [math] a_j [/math]. Применим его к последовательности [math] f(a) [/math] и рассмотрим элемент с индексом [math] i [/math].
[math] [i: j]f(a)_i [/math]
[math]= [i: j](f(a_0), \dots, f(a_{n-1}))_i [/math] (по введенному нами определению)
[math] = \min(f(a_i), f(a_j)) [/math] (по определению компаратора)
[math] = f(\min(a_i, a_j)) [/math] (по уже доказанной лемме)
[math] = f([i: j](a)_i) [/math] (по определению компаратора)
[math] = f([i: j](a))_i [/math](по введенному нами определению).
То есть, в результате [math] i [/math]-й элемент не зависит от порядка применения компаратора [math] [i: j] [/math] и функции [math] f [/math]. Те же рассуждения можно провести для всех других индексов, то есть [math] [i: j]f(a) = f([i: j](a)) [/math], и также для всех компараторов в сети, то есть лемма доказана. |
| [math]\triangleleft[/math] |
| Теорема (0-1 принцип): |
Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая |
