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