東京大学 情報理工学系研究科 創造情報学専攻 2006年8月実施 筆記試験 第1問

标签：

• Tokyo-University
• Sorting-Network-Comparator-Count-and-Depth
• Algorithm-Complexity

Author

itsuitsuki

Description

日本語

下左図は，$2$ 入力 $2$ 出力の比較器であり，大きさ $2$ のソーティングネットワークでもある。入出力の接続部は黒丸●で表現されている。比較器に左から数を $2$ つ入力すると，小さい数を上から，大きい数を下から右方向へそれぞれ出力する。$2$ 数が等しい場合には，同じ数を上下から出力する。

以下ではこの比較器を組み合わせることで，大きさ $n$ のソーティングネットワークを構成することを考える。大きさ $n$ のソーティングネットワークには，入力線が $n$ 本あり，左端から $n$ 個の整数を入力すると，上から下に昇順に整列して右端から出力する。 ある比較器の出力が別の比較器の入力となっている場合は，その二つの比較は $1$ ステップでの同時実行はできない。たとえば，上右図においては，比較器 $1$ と $2$ は同時に $1$ ステップで実行することができるが，比較器 $3$ は比較器 $1$ と $2$ の出力を入力とするため，別に $1$ ステップ必要であり，全体で $2$ ステップかかる。

(1) 下記のように配線すると，$3$ つの入力は $4$ ステップの実行の後，右端で必ず昇順に出力されることを示しなさい。

(2) 比較器の個数が $O(n^2)$ となる大きさ $n$ のソーティングネットワークを大きさ $n-1$ のソーティングネットワークから帰納的に構成する方法を一つ示し，正しさを説明した上で，必要な比較器の個数を $n$ の式で表しなさい。

(3) (2) で構成した大きさ $n$ のソーティングネットワークにおいて，同時に実行できる比較を $1$ ステップで実行する場合，全体でかかるステップ数を $n$ で表しなさい。

(4) 同時に実行できる比較を $1$ ステップで実行する場合を考える。大きさ $4$ のソーティングネットワークのステップ数の最小数は $3$ であることが知られている。そのような大きさ $4$ のソーティングネットワークを $1$ つ構成し，ステップ数が $3$ であること，また，正しくソーティングできることを説明しなさい。

English

The left figure below shows a sorting network of size 2. The network has a "comparator module" that has two inputs, represented as lines coming into the module from left, and two outputs, represented as lines going out to right. Note that the connecting points of input/ouptut are indicated by the black dots $\bullet$. The upper output is the smaller of the two inputs and the lower output is the larger. When the 2 values are the same, the value is output from both lines.

We consider a problem of constructing a sorting network of size $n$. A sorting network of size $n$ has $n$ lines and multiple comparator modules. The $n$ numbers are given at the left end and the network sorts them in the increasing order from top to bottom and outputs them from the right end. Comparisons of two modules of which one's output is another's input cannot be executed simultaneously in an execution step. For example, in the right figure above, the comparisons of modules 1 and 2 can be executed simultaneously in a step, but another step is required for the comparison by module 3, because the outputs of modules 1 and 2 are the inputs of module 3.

(1) Explain that the sorting network of size 3 as in the following figure outputs any 3 numbers in the increasing order.

(2) Show how to construct a sorting network of size $n$ inductively from a sorting network of size $n-1$, using in total $O(n^2)$ comparator modules. Describe the exact number of comparator modules as a function of $n$.

(3) As regards your answer of (2), if we allow simultaneous operations of comparator modules in a step, how many steps are required to sort $n$ inputs?

(4) Consider the case of executing multiple comparisons simultaneously. It is known that the sorting network of size 4 can be executed in 3 steps. Construct such a sorting network of size 4 and explain the correctness of your answer.

题目描述

题图左侧给出一个双输入、双输出比较器，也可视为规模为 2 的排序网络；黑点表示输入、输出连接点。两个数从左侧输入后，较小值从右侧上方输出，较大值从右侧下方输出；若二者相等，上下均输出该值。

用这种比较器构造规模为 (n) 的排序网络。网络有 (n) 条输入线，从左侧输入 (n) 个整数，右侧必须按从上到下的升序输出。若某比较器的输出是另一比较器的输入，两次比较不能在同一步同时执行；彼此无依赖的比较器可以并行。如题图右侧的比较器 1、2 可在一步内同时执行，比较器 3 依赖它们的输出，故整个过程共需两步。

1. 证明原文第二幅图的接线能使三个输入在执行 4 步后必然按升序输出。
2. 给出一种从规模 (n-1) 的排序网络归纳构造规模 (n) 排序网络的方法，使比较器总数为 (O(n^2))；说明构造正确性，并写出比较器数量关于 (n) 的精确表达式。
3. 对第 2 问构造的网络，若所有可并行的比较均在同一步执行，写出总步数关于 (n) 的表达式。
4. 已知规模为 4 的排序网络最少可用 3 步完成。构造一个这样的网络，并说明其步数确为 3 且能正确排序。

考点

• 排序网络的比较器数量与深度：从较小规模网络归纳增添比较器，分别计算总比较器数和考虑并行依赖后的执行层数。
• 算法正确性与复杂度：用比较器输出的不变量或分类讨论证明网络对任意输入均能排序，并用渐近记号描述规模。