| dbo:abstract
|
- En ciencias de la computación, una red de ordenamiento (en inglés, sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro. Las redes de ordenamiento se diferencian del más general en el hecho de que no son capaces de manejar cantidades arbitrariamente grandes de entrada, y que su secuencia de comparaciones se conoce de antemano, independientemente del resultado de las comparaciones previas. Esta independencia de la secuencia de comparaciones es útil para la ejecución paralela y para su implementación en hardware. A pesar de la simplicidad de las redes de ordenamiento, su teoría es sorprendentemente profunda y compleja. Las redes de ordenamiento fueron primero estudiadas circa 1954 por Armstrong, Nelson y O'Connor, quienes subsecuentemente patentaron la idea. Las redes de ordenamiento pueden ser implementadas tanto en hardware como en software. Donald Knuth describe como los comparadores para los enteros binarios pueden ser implementados como sencillos dispositivos electrónicos de tres estados. , en 1968, sugirió usarlos para construir redes de interruptores para hardware de computadora, reemplazando a ambos: los buses de computadora y el más rápido pero más caro conmutador de barras cruzadas. Desde la década del 2000, las redes de ordenamiento (especialmente del ordenamiento bitónico) son usadas por la comunidad GPGPU para construir algoritmos de ordenamiento para correr en unidades de procesamiento gráfico. (es)
- En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre. Les réseaux de tri diffèrent des algorithmes de tri par comparaison dans le sens où ils ne sont pas capables de traiter un nombre arbitraire d'entrées ; de plus, leur séquence de comparaisons est définie à l'avance, et indépendante du résultat des comparaisons précédentes. L'indépendance des séquences de comparaison est utile pour l'exécution en parallèle et pour la réalisation en hardware. Elle peut aussi être vue comme une protection contre un logiciel malveillant qui chercherait à examiner la nature des séquences triées. (fr)
- In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks. Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort larger amounts of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor, who subsequently patented the idea. Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices. Batcher, in 1968, suggested using them to construct switching networks for computer hardware, replacing both buses and the faster, but more expensive, crossbar switches. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units. (en)
- ソーティングネットワーク（英: sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。 (ja)
- Sieć sortująca to abstrakcyjny, matematyczny model sieci, składającej się z przewodów i modułów porównujących (komparatorów), używanej do sortowania sekwencji liczb. Każdy moduł porównujący łączy dwa przewody i sortuje dwie wartości, wyprowadzając mniejszą na jeden przewód i większą na drugi. Pomimo prostoty modelu, teoria sieci sortujących jest zaskakująco głęboka i złożona. (pl)
- Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений. Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию. (ru)
|
| rdfs:comment
|
- ソーティングネットワーク（英: sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。 (ja)
- Sieć sortująca to abstrakcyjny, matematyczny model sieci, składającej się z przewodów i modułów porównujących (komparatorów), używanej do sortowania sekwencji liczb. Każdy moduł porównujący łączy dwa przewody i sortuje dwie wartości, wyprowadzając mniejszą na jeden przewód i większą na drugi. Pomimo prostoty modelu, teoria sieci sortujących jest zaskakująco głęboka i złożona. (pl)
- Сеть сортиро́вки (англ. sorting network) — класс алгоритмических методов сортировки, в которых последовательность сравнений не зависит от результатов предыдущих сравнений. Часто изображаются в виде сети, горизонтальные линии в которой соответствуют передаче сортируемого элемента слева направо, а вертикальными соединениями пар линий обозначены так называемые «модули компараторов», имеющие два входа и два выхода. Модуль компаратора производит сравнение элементов на входе и обменивает их местами таким образом, чтобы на нижнем выходе было, например, большее число. Сети сортировки допускают эффективную аппаратную реализацию. (ru)
- En ciencias de la computación, una red de ordenamiento (en inglés, sorting network) es un algoritmo que ordena un número fijo de valores mediante el uso de una secuencia fija de comparaciones. Esta puede ser imaginada como una red de hilos y módulos comparadores. Los valores (de cualquier tipo ordenable) fluyen a través de los hilos (no se debe confundir con hilo de ejecución). Cada comparador conecta dos hilos, compara los valores introducidos por los hilos, y los ordena obteniendo el menor como salida a un hilo, y el mayor a otro. (es)
- In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform sorting on fixed numbers of values, in which case they are called sorting networks. (en)
- En Informatique, un réseau de tri est un algorithme de tri qui trie un nombre fixe de valeurs en utilisant une suite fixe de comparateurs. On peut voir un réseau de tri comme un réseau composé de fils et de comparateurs. Les valeurs, prises dans un ensemble ordonné, circulent le long des fils. Chaque comparateur connecte deux fils, compare les données qui entrent par les fils et les trie, sortant la plus petite donnée sur l'un des fils, la plus grande sur l’autre. (fr)
|
