照山 順一

比較ソートにおける効率は主に比較回数によって計られる. 本研究では, できるだけ平均の比較回数が少ない比較ソートアルゴリズムの設計を目的とする. EdelkampとWeiβによってFordとJohnsonのアルゴリズムの平均比較回数がnlgn-1.3999n+O(lgn)であることが示されている. また, 情報理論的下限から平均比較回数の下限はlceil lgn!rceil approx nlgn-1.4426n+O(lgn)であることが知られている. 本研究では, 2つの要素を挿入する操作を与えることにより, 平均比較回数が高々nlgn-1.4034+O(lgn)となるアルゴリズムを設計した. また, 我々のアルゴリズムとFordとJohnsonのアルゴリズムを組み合わせることにより, 平均比較回数nlgn-1.4106n+O(log n)が達成されることを示した.

k-IBDD は，k 段のレイヤーを持つ分岐プログラムであり，各レイヤーが OBDD (順序付き二分決定図) となっている．本稿では，k-IBDD 充足可能性問題 （以下，k-IBDD SAT） を考える．k-IBDD SAT とは，与えられた k-IBDD が 1 を出力するような変数割当が存在するかどうかを判定する問題である．本問題に対して，n 変数，poly(n) ノードの k-IBDD SAT を高々 poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムが知られている．ここで，poly(n) は n の多項式を表す．本稿では，n 変数，cn ノードの k-IBDD SAT を高々 poly(n)・2(1-μ(c))n 時間で解く指数領域アルゴリズムを与える．ここで，μ(c)=Ω(1/(log c)2k-1-1) である．我々のアルゴリズムは既存のアルゴリズムを拡張することで線形サイズの k-IBDD に対して 2n 時間より指数的な高速化を達成している．

k-IBDD は,k 段のレイヤーを持つ分岐プログラムであり,各レイヤーが OBDD (順序付き二分決定図) となっている.本稿では,k-IBDD 充足可能性問題 (以下,k-IBDD SAT) を考える.k-IBDD SAT とは,入力として k-IBDD が与えられ,シンク 1 に到達する変数への割当が存在するかどうかを判定する問題である.本稿では,n 変数,poly(n) ノードの 2-IBDD SAT を高々 poly(n)・2n-√n 時間で解く多項式領域アルゴリズムを与える.poly(n) は n の多項式を表す.さらに,このアルゴリズムを拡張することにより,n 変数,poly(n) ノードの k-IBDD SAT を高々,poly(n)・2n-n1/2k-1 時間で解く多項式領域アルゴリズムを与える.

本稿ではk集合整列問題に対して効率のよいアルゴリズムを与える.k集合整列問題とは以下のような問題である:n個のビンにk個のボールが入っており,i番目のビンにあるボールすべてに番号n-i+1がついている.隣り合うビンに存在する任意の2つのボールの交換のみを許した時,すべてのボールとビンの番号を一致させるためには何回の交換が必要だろうか.我々はこの問題に対して,高々(k+1)/4n^2+O(n)回の交換で本問題を解く貪欲アルゴリズムを与える.この値はn,kが大きくなるにつれて下界値と近くなる.また,k=3の場合に対してさらに効率のよいアルゴリズムを与える.このアルゴリズムは再帰的アルゴリズムであり,高々(15)/(16)n^2+O(n)回の交換で本問題を解くことができる.

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string S by making queries of the following form: "Is s a substring of S?", where s is a query string over the given alphabet. The number of queries required to identify the string S is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string S with at most 3/4 N + o(N) queries, where N is the length of S. This contrasts sharply with the classical query complexity N. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in S, which may have an independent interest. We also prove that any bounded-error quantum algorithm needs Ω(N/log^2N ) queries. For this, we introduce another query model and obtain a lower bound for this model with the adversary method, from which bound we get the desired lower bound in the original query model.

We investigate the following sorting puzzle: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n-i+1. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost (4n^2)/5 swaps. In this paper, we show an algorithm which solves this puzzle using less than (2n^2)/3 swaps. Since it is known that the lower bound of the number of swaps is [numerical formula],our result is almost tight. Futhermore, we show that for n=2^k+1(k〓0) the algorithm is optimal.