Сортирующие сети — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{В разработке}}
 
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 41: Строка 39:
  
 
== См.также ==
 
== См.также ==
[[Сортирующие сети для квадратичных сортировок]].
+
[[Сортирующие сети для квадратичных сортировок]]
 +
 
 +
[[0-1 принцип]]
 +
 
 +
[[Сеть Бетчера]]
  
  

Версия 03:19, 15 июня 2011

Определение:
Сеть называется сортирующей если для любой входной последовательности получающаяся из нее выходная последовательность монотонно возрастает.
Сортирующая сеть с 2 проводами



Компараторы

Определение:
Компаратором называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах.


Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.

Определение:
k-компаратором называется устройство упорядочивающие значения на k проводах.


Компаратороы можно располагать в одном слое если они подключены к разным проводам.

Сети

Определение:
Глубиной сети (depth) называется количество слоев в сети.


Определение:
Размером сети (size) называется количество компараторов в сети.


Теорема:
Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1.

Подробнее в статье 0-1 принцип.

См.также

Сортирующие сети для квадратичных сортировок

0-1 принцип

Сеть Бетчера


Источники