Сортирующие сети — различия между версиями
| Строка 5: | Строка 5: | ||
Сеть называется '''сортирующей''' если для любой входной последовательности получающаяся из не выходная последовательность не убывает. | Сеть называется '''сортирующей''' если для любой входной последовательности получающаяся из не выходная последовательность не убывает. | ||
}} | }} | ||
| − | + | ||
| + | == Компараторы == | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
'''Компаратором''' называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах. | '''Компаратором''' называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах. | ||
}} | }} | ||
| + | |||
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения. | Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения. | ||
{{Определение | {{Определение | ||
| Строка 15: | Строка 17: | ||
'''k-компаратором''' называется устройство упорядочивающая значения на '''k''' проводах. | '''k-компаратором''' называется устройство упорядочивающая значения на '''k''' проводах. | ||
}} | }} | ||
| + | |||
Компаратором можно располагать в одном слое если они подключены к разным проводам. | Компаратором можно располагать в одном слое если они подключены к разным проводам. | ||
| − | + | == Сети == | |
| − | == | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| Строка 26: | Строка 28: | ||
'''Размером сети (size)''' называется количество компараторов в сети. | '''Размером сети (size)''' называется количество компараторов в сети. | ||
}} | }} | ||
| + | |||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. | Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. | ||
}} | }} | ||
| + | |||
Подробнее в статье [[0-1 принцип]]. | Подробнее в статье [[0-1 принцип]]. | ||
| + | |||
| + | == См.также == | ||
| + | [[Сортирующие сети для квадратичных сортировок]]. | ||
| + | |||
| + | |||
| + | == Источники == | ||
| + | * [http://en.wikipedia.org/wiki/Sorting_network Wikipedia - Sorting networks] | ||
| + | |||
| + | [[Категория: Сортирующие сети]] | ||
Версия 22:32, 7 июня 2011
Эта статья находится в разработке!
| Определение: |
| Сеть называется сортирующей если для любой входной последовательности получающаяся из не выходная последовательность не убывает. |
Содержание
Компараторы
| Определение: |
| Компаратором называется устройство подключенное к двум проводам, которое упорядочивает текущие значения на проводах. |
Обычно компараторы меньшее значение передают на провод с меньшим номером, но бывают и направленные компараторы, у которых указано направление перемещения.
| Определение: |
| k-компаратором называется устройство упорядочивающая значения на k проводах. |
Компаратором можно располагать в одном слое если они подключены к разным проводам.
Сети
| Определение: |
| Глубиной сети (depth) называется количество слоев в сети. |
| Определение: |
| Размером сети (size) называется количество компараторов в сети. |
| Теорема: |
Сеть является сортирующей тогда и только тогда, когда она сортирует все наборы из 0 и 1. |
Подробнее в статье 0-1 принцип.
См.также
Сортирующие сети для квадратичных сортировок.
