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