Изменения

Перейти к: навигация, поиск

Сортирующие сети

520 байт добавлено, 22:07, 7 июня 2011
Нет описания правки
{{Определение
|definition =
Сеть называется '''сортирующей''' если она сортирует все наборы для любой входной последовательности получающаяся из 0 и 1не выходная последовательность не убывает.
}}
 
=== Компараторы ===
 
{{Определение
|definition =
'''Компаратором''' называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах.
}}
 Компараторы бывают:* '''Прямыми''' - когда Обычно компараторы меньшее значение идет передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.* '''Обратными''' - когда меньшее значение идет на провод с большим номером. Компаратором можно располагать в одном слое если они подключены к разным проводам. 
{{Определение
|definition =
'''k-компаратором''' называется устройство упорядочивающая значения на '''k''' проводах.
}}
Компаратором можно располагать в одном слое если они подключены к разным проводам.
=== Характеристики сети ===
 
{{Определение
|definition =
'''Глубиной сети(depth)''' называется количество слоев в сети.}}{{Определение|definition ='''Размером сети (size)''' называется количество компараторов в сети.}}{{Теорема|statement=Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1.
}}
Подробнее в статье [[0-1 принцип]].
Анонимный участник

Навигация