Викиконспекты - Вклад участника [ru]

0-1 принцип

2012-06-07T13:29:00Z

77.241.45.30:

Есть два способа проверить сеть из <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> проверить сеть очень проблематично.

== Второй способ ==
Второй способ основывается на предположении, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Если мы докажем это, то сможем проверять сеть за <tex> O(2^n \cdot Comp(n)) </tex>, что намного быстрее.

=== Доказательство 0-1 принципа ===
{{ Определение
| definition =
Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''', если <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>
*<tex> [i: j](f(a_0), \dots, f(a_{n-1}))_i </tex> (по введенному выше определению)
*<tex> f([i: j](a))_i = f([i: j](a)_i) </tex> (по определению компаратора и по введенному выше определению)
*<tex> \min(f(a_i), f(a_j)) = f(\min(a_i, a_j)) </tex> (по определению компаратора и по уже доказанной лемме).
Таким образом, результат не зависит от того, что мы сделаем с отдельным компаратором сначала: применим монотонную функцию или пропустим его через сеть. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </tex> для всех компараторов в сети, то есть лемма доказана.
}}

{{ Теорема
| about = 0-1 принцип
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
| proof =
Рассмотрим сеть <tex> N </tex>, сортирующую в возрастающем порядке: <tex> a_0 \le a_1 \le \dots \le 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>.

Рассмотрим функцию <tex> f(x) =
\begin{cases}
0, x < b_i \\
1, x \ge b_i
\end{cases}
</tex> . Очевидно, она монотонная. Заметим, что <tex> f(b_i) = 1 </tex>, а <tex> f(b_{i + 1}) = 0 </tex>, то есть <tex> f(b) </tex>, или <tex> f(N(a)) </tex> — не отсортирована. Так как <tex> f </tex> и <tex> N </tex> коммутируют, <tex> N(f(a)) </tex> — также не отсортирована. Но по предположению теоремы, все последовательности из нулей и единиц сеть сортировать умеет, то есть такой последовательности <tex> a </tex> не найдется, то есть сеть компараторов является сортирующей.
}}

== Источники ==
*[http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Sorting networks]
*[http://en.wikipedia.org/wiki/Sorting_network Wikipedia — Sorting networks]
*Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Сортирующие сети]]

0-1 принцип

2012-05-31T19:51:04Z

77.241.45.30: /* Доказательство 0-1 принципа */

Есть два способа проверить сеть из n компараторов на то, что она сортирующая.

__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> проверить сеть очень проблематично.

== Второй способ ==
Второй способ основывается на предположении, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Если мы докажем это, то сможем проверять сеть за <tex> O(2^n \cdot Comp(n)) </tex>, что намного быстрее.

=== Доказательство 0-1 принципа ===
{{ Определение
| definition =
Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''', если <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>
*<tex> [i: j](f(a_0), \dots, f(a_{n-1}))_i </tex> (по введенному выше определению)
*<tex> f([i: j](a))_i = f([i: j](a)_i) </tex> (по определению компаратора и по введенному выше определению)
*<tex> \min(f(a_i), f(a_j)) = f(\min(a_i, a_j)) </tex> (по определению компаратора и по уже доказанной лемме).
Таким образом, результат не зависит от того, что мы сделаем с отдельным компаратором сначала: применим монотонную функцию или пропустим его через сеть. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </tex> для всех компараторов в сети, то есть лемма доказана.
}}

{{ Теорема
| about = 0-1 принцип
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
| proof =
Рассмотрим сеть <tex> N </tex>, сортирующую в возрастающем порядке: <tex> a_0 \le a_1 \le \dots \le 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>.

Рассмотрим функцию <tex> f(x) =
\begin{cases}
0, x < b_i \\
1, x \ge b_i
\end{cases}
</tex> . Очевидно, она монотонная. Заметим, что <tex> f(b_i) = 1 </tex>, а <tex> f(b_{i + 1}) = 0 </tex>, то есть <tex> f(b) </tex>, или <tex> f(N(a)) </tex> — не отсортирована. Так как <tex> f </tex> и <tex> N </tex> коммутируют, <tex> N(f(a)) </tex> — также не отсортирована. Но по предположению теоремы, все последовательности из нулей и единиц сеть сортировать умеет, то есть такой последовательности <tex> a </tex> не найдется, то есть сеть компараторов является сортирующей.
}}

== Источники ==
*[http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/indexen.htm Sorting networks]
*[http://en.wikipedia.org/wiki/Sorting_network Wikipedia — Sorting networks]
*Дональд Кнут — Искусство программирования — Том 3 — Глава 5.3.4 — стр. 249

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Сортирующие сети]]