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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 22: Строка 22:
 
Компараторы можно располагать в одном слое, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
 
Компараторы можно располагать в одном слое, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.
 
== Сети ==
 
== Сети ==
 +
{{Определение
 +
|definition =
 +
'''Сравнивающая сеть''' — несколько компараторов, соединенных проводами. Используется для
 +
}}
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =

Версия 01:09, 30 мая 2012

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



Компараторы (сравнивающие устройства)

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


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

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


Компараторы можно располагать в одном слое, если они подключены к разным проводам. В этом случае сравнения будут выполняться параллельно.

Сети

Определение:
Сравнивающая сеть — несколько компараторов, соединенных проводами. Используется для


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


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


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

См.также

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

0-1 принцип

Сеть Бетчера


Источники