アルゴリズムと計算量の問題

互いに異なる $5$ 個の実数 $a_1,a_2,a_3,a_4,a_5$ を、比較ソートで昇順に並べかえる。比較ソートとは、$2$ つの要素の大小を比べる操作（結果は「$<$」か「$>$」の $2$ 通り）だけを用いて並べ方を決めるアルゴリズムのことである。

どの比較ソートも、最悪の場合には少なくとも $\lceil {\log }_{2}5!\rceil$ 回の比較を行う。これは決定木の考え方から得られる下界である。この下界 $\lceil {\log }_{2}5!\rceil$ の値を求めよ。ただし、$\lceil x\rceil$ は $x$ 以上の最小の整数を表す。

互いに異なる $6$ 個の実数 $a_1,a_2,\dots ,a_6$ を、比較だけを使って昇順に並べかえる。$1$ 回の比較では、ある $2$ 個 $a_i,a_j$ について「$a_i<a_j$ か」を調べ、「はい」か「いいえ」の答えを得る。どのような比較ソートのアルゴリズムでも、最悪の場合の比較回数は決定木による下界 $\lceil {\log }_{2}6!\rceil$ 以上になる。この下界 $\lceil {\log }_{2}6!\rceil$ の値を求めよ。ただし、$\lceil x\rceil$ は $x$ 以上の最小の整数を表す。

互いに異なる $10$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[10]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,9$ の順に、各 $k$ について $j=1,2,\dots ,10-k$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

入力の並びは $10!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

互いに異なる $7$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[7]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,6$ の順に、$j=1,2,\dots ,7-k$ の順で $A[j]$ と $A[j+1]$ を比べ、$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

最初の並びは、$7$ 個の数の $7!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

互いに異なる $6$ 個の実数を、$6!$ 通りの並べ方のどれもが等確率 $\frac{1}{720}$ で起こるように並べ、配列 $A[1],A[2],\dots ,A[6]$ を作る。$1\leqq i<j\leqq 6$ を満たす整数の組 $(i,j)$ のうち、$A[i]>A[j]$ となるものを転倒といい、転倒の個数を $X$ とする（$X$ は、この配列を挿入ソートで昇順に並べかえるときに行われる隣り合う要素の交換の回数に等しい）。$X$ の期待値 $E(X)$ を求めよ。