47
правок
Изменения
м
Remove space in LaTeX token
Есть два способа проверить сеть из <tex>n </tex> компараторов на то, что она сортирующая.
__TOC__
== Первый способ ==
Первый, наивный способ — перебрать все перестановки из <tex> n </tex> элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> — количество компараторов в сети из <tex>n</tex> элементов. Обычно это Это количество можно оценить как <tex> n \log^2n </tex> ([[Сеть_Бетчера|Сеть Бетчера]]). Таким образом, получаем асимптотику <tex> O(n!n \log^2n) </tex>, и при <tex>n = 10</tex> проверить сеть очень проблематично.
== Второй способ ==
{{ Определение
| definition =
Функция <tex> f </tex> из <tex> : A </tex> в <tex> \rightarrow B </tex> называется '''монотонной'''(англ. ''monotonous''), если <tex> \forall a_1, a_2 \in A : a_1 \le leqslant a_2 \Rightarrow f(a_1) \le leqslant f(a_2) </tex>
}}
Пусть <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 leqslant a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \le leqslant 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>.
Рассмотрим произвольный компаратор <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[i: j](a_ja)) </tex> (по определению компаратора) <br> <tex> = f(\min(a_i, a_j)) </tex> (по уже доказанной лемме) <br> <tex> _i = f([i: j](a)_i) </tex> (по определению компаратораи по введенному выше определению) <br> *<tex> \min(f(a_i), f(a_j)) = f([i: j]\min(aa_i, a_j))_i </tex>(по введенному нами определениюкомпаратора и по уже доказанной лемме). То есть в результате <tex> i </tex>-й элемент Таким образом, результат не зависит от порядка применения компаратора <tex> [iтого, что мы сделаем с отдельным компаратором сначала: j] </tex> и функции <tex> f </tex>применим монотонную функцию или пропустим его через сеть. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </tex>, и также для всех компараторов в сети, то есть лемма доказана.
}}
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
| proof =
Рассмотрим сеть <tex> N </tex>, сортирующую в возрастающем порядке: <tex> a_0 \le leqslant a_1 \le leqslant \dots \le leqslant a_{n-1} </tex>.
Предположим, что есть последовательность <tex> a </tex>, которую сеть <tex> N </tex> не сортирует. Тогда после пропуска <tex> a </tex> через сеть <tex> N </tex>, получим последовательность <tex> b </tex>, в которой найдется индекс <tex> i </tex> такой, что <tex> b_i > b_{i + 1} </tex>.
}}
== См. также ==*[[Сеть_Бетчера|Сеть Бетчера]]*[[Сортирующие_сети|Сортирующие сети]] == Источники информации ==* [http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Bachelor-Studiengang Angewandte Informatik {{---}} Sorting networks]* [http://en.wikipedia.org/wiki/Sorting_network Wikipedia {{--- }} Sorting networks]* Дональд Кнут {{- --}} Искусство программирования. {{---}} Том 3. {{---}} Глава 5.3.4, {{---}} стр. 249
[[Категория:Дискретная математика и алгоритмы]][[Категория: Сортирующие сети]]
