0-1 принцип — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 7 участников)
Строка 1: Строка 1:
Есть два способа проверить сеть из n компараторов на то, что она сортирующая.
+
Есть два способа проверить сеть из <tex>n</tex> компараторов на то, что она сортирующая.
  
 
__TOC__
 
__TOC__
  
 
== Первый способ ==
 
== Первый способ ==
Первый, наивный способ - перебрать все перестановки из n элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует <tex> O(n! \cdot Comp(n)) </tex> действий, где <tex> Comp(n) </tex> - количество компараторов в сети из n элементов. Обычно это количество можно оценить как <tex> n \log^2 n </tex>(сеть Бэтчера), то есть получаем асимптотику <tex> O(n! n \log^2 n) </tex>, то есть при n, равном уже 10, проверить сеть очень проблематично.
+
Первый, наивный способ перебрать все перестановки из <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>, что намного быстрее.
+
Второй способ основывается на предположении, что если сеть сортирует все последовательности из нулей и единиц, то сеть является сортирующей. Если мы докажем это, то сможем проверять сеть за <tex> O(2^n \cdot Comp(n)) </tex>, что намного быстрее.
  
 
=== Доказательство 0-1 принципа ===
 
=== Доказательство 0-1 принципа ===
 
{{ Определение
 
{{ Определение
 
| definition =
 
| 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>
+
Функция <tex> f: A \rightarrow B </tex> называется '''монотонной''' (англ. ''monotonous''), если <tex> \forall a_1, a_2 \in A : a_1 \leqslant a_2 \Rightarrow f(a_1) \leqslant f(a_2) </tex>
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
| statement =
 
| 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>.
+
Пусть <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 =
 
| 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> a_1 \leqslant a_2 </tex>. Тогда <tex> f(\min(a_1, a_2)) = f(a_1) </tex>. Также, по монотонности, <tex> f(a_1) \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> f(\min(a_1, a_2)) = \min(f(a_1), f(a_2)) = f(a_1) </tex>. Такие же рассуждения можно провести для случая <tex> a_2 < a_1 </tex>.
Строка 31: Строка 31:
 
{{Лемма
 
{{Лемма
 
| statement =
 
| 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>.
+
Пусть <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 =
 
| proof =
 
Рассмотрим произвольный компаратор <tex> [i: j] </tex>, сортирующий элементы <tex> a_i </tex> и <tex> a_j </tex>. Применим его к последовательности <tex> f(a) </tex> и рассмотрим элемент с индексом <tex> i </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(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: j]f(a)_i =</tex>
 
+
*<tex> [i: j](f(a_0), \dots, f(a_{n-1}))_i </tex> (по введенному выше определению)
То есть, в результате <tex> i </tex>-й элемент не зависит от порядка применения компаратора <tex> [i: j] </tex> и функции <tex> f </tex>. Те же рассуждения можно провести для всех других индексов, то есть <tex> [i: j]f(a) = f([i: j](a)) </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> для всех компараторов в сети, то есть лемма доказана.  
 
}}
 
}}
  
Строка 45: Строка 48:
 
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
 
| statement = Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
 
| proof =
 
| proof =
Рассмотрим сеть <tex> N </tex> , сортирующую в возрастающем порядке: <tex> a_0 \le a_1 \le \dots \le a_{n-1} </tex>.
+
Рассмотрим сеть <tex> N </tex>, сортирующую в возрастающем порядке: <tex> a_0 \leqslant a_1 \leqslant \dots \leqslant a_{n-1} </tex>.
 
   
 
   
Предположим, что есть последовательность <tex> a </tex>, которую сеть <tex> N </tex> не сортирует. Тогда после пропуска <tex> a </tex> через сеть <tex> N </tex>, получим последовательность b, в которой найдется индекс <tex> i </tex> такой, что <tex> b_i > b_{i + 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) =  
 
Рассмотрим функцию <tex> f(x) =  
Строка 54: Строка 57:
 
1, x \ge b_i
 
1, x \ge b_i
 
\end{cases}
 
\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> не найдется, то есть сеть компараторов является сортирующей.
+
</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.html Sorting networks]
+
*[[Сеть_Бетчера|Сеть Бетчера]]
* [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks]
+
*[[Сортирующие_сети|Сортирующие сети]]
* Дональд Кнут - Искусство программирования. Том 3. Глава 5.3.4, стр. 249
+
 
 +
== Источники информации ==
 +
*[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
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Сортирующие сети]]

Текущая версия на 19:35, 4 сентября 2022

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

Первый способ

Первый, наивный способ — перебрать все перестановки из [math] n [/math] элементов, пропустить их через сеть и проверить их на то, что они отсортированы. Этот подход потребует [math] O(n! \cdot Comp(n)) [/math] действий, где [math] Comp(n) [/math] — количество компараторов в сети из [math]n[/math] элементов. Это количество можно оценить как [math] n \log^2n [/math] (Сеть Бетчера). Таким образом, получаем асимптотику [math] O(n!n \log^2n) [/math], и при [math]n = 10[/math] проверить сеть очень проблематично.

Второй способ

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

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

Определение:
Функция [math] f: A \rightarrow B [/math] называется монотонной (англ. monotonous), если [math] \forall a_1, a_2 \in A : a_1 \leqslant a_2 \Rightarrow f(a_1) \leqslant 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 \leqslant a_2 [/math]. Тогда [math] f(\min(a_1, a_2)) = f(a_1) [/math]. Также, по монотонности, [math] f(a_1) \leqslant 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] f([i: j](a))_i = f([i: j](a)_i) [/math] (по определению компаратора и по введенному выше определению)
  • [math] \min(f(a_i), f(a_j)) = f(\min(a_i, a_j)) [/math] (по определению компаратора и по уже доказанной лемме).
Таким образом, результат не зависит от того, что мы сделаем с отдельным компаратором сначала: применим монотонную функцию или пропустим его через сеть. Те же рассуждения можно провести для всех других индексов, то есть [math] [i: j]f(a) = f([i: j](a)) [/math] для всех компараторов в сети, то есть лемма доказана.
[math]\triangleleft[/math]


Теорема (0-1 принцип):
Если сеть компараторов сортирует все последовательности из нулей и единиц, то она сортирующая
Доказательство:
[math]\triangleright[/math]

Рассмотрим сеть [math] N [/math], сортирующую в возрастающем порядке: [math] a_0 \leqslant a_1 \leqslant \dots \leqslant a_{n-1} [/math].

Предположим, что есть последовательность [math] a [/math], которую сеть [math] N [/math] не сортирует. Тогда после пропуска [math] a [/math] через сеть [math] N [/math], получим последовательность [math] b [/math], в которой найдется индекс [math] i [/math] такой, что [math] b_i \gt b_{i + 1} [/math].

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

См. также

Источники информации