2024　大分大学　推薦知能情報システムプログラムMathJax

【１】　次の情報技術に関する文章を読んで，以下の問い(1)〜(3)に答えなさい．

　問題を解くための手順を一般にアルゴリズムと呼ぶ．アルゴリズムという概念自体は，計算機とは無関係に成立するが，普通は計算機を使って問題の解を求めるための手順を指す．計算機科学における基本的な問題にソート（整列）の問題がある．例えば，異なる数の列を昇順（任意の隣り合う$2$個の数で，右の数が左の数より必ず大きい）にソートするといったものである．ソートの問題を解くアルゴリズムは，入力列として$<29,37,51,18,46>$が与えられると，$<18,29,37,46,51>$を出力する手順である．ソートの問題については，その必要性の高さから多くの優れたアルゴリズムが開発され，現在でも様々なアプリケーションで利用されている．

　一つの問題に対して，複数のアルゴリズムが存在する場合，いずれを用いるかの判断基準で重要なのは効率である．多くの場合，問題のサイズ$n$（扱うデータの数．上のソートの例では入力列の数の個数）を大きくした時の，解を求めるまでの実行時間の増大の仕方で表す場合が多い．例として，二つのソートのアルゴリズムを比較しよう$\text{（}n\geqq 2$とする）．一つは，挿入ソートと呼ばれ，$n$個のデータを$c_1{n}^2$時間をかけてソートし，もう一方は，マージソートと呼ばれ，$c_{2}n{\log }_{2}n$時間かけてソートするとわかっている．ここで，$c_1$と$c_2$は，$n$に依存しない定数で，普通は，$c_1<c_2$である．実行時間に対して定数係数が与える影響の度合いは，$n$が増えるごとに小さくなる．したがって，問題のサイズ$n$が増えると，前者の計算時間は$n^2$に比例し，後者は$n{\log }_{2}n$に比例して増大すると言える．ここで，${\log }_{2}n$が$n$に比べてずっと小さいことは重要である（例えば，$n=1000$のとき，${\log }_{2}n$は，おおよそ$10\text{，}$$n$が$100$万のとき，${\log }_{2}n$は，おおよそ$20$である）．通常，問題のサイズ$n$が小さい時は，挿入ソートの方がマージソートより速いが$\text{（}{c}_1<c_2$の効果），どれだけ$c_1$が$c_2$より小さくとも，挿入ソートとマージソートの実行時間が逆転する$n$の値が存在する．

(1)　文章中のソートの入力列$<29,37,51,18,46>$を昇順にソートするとして，出力を得るまでの具体的な手順を文章で書きなさい．ただし，数の列の最も左の位置にある数を，$1$番の数，以下右に，$2$番の数，$\cdots \text{，}$$5$番の数と呼ぶとする．また，数の比較や位置の交換は一度に$2$個の数の間でしかできないとする．

(2)　問題のサイズ$n$$\text{（}\geqq 2\text{）}$の入力列に対して，ある計算機上で，挿入ソートの実行には$16n^2$時間かかり，マージソートの実行には$64n{\log }_{2}n$時間かかるとわかっているとする．この計算機では，問題のサイズ$n$がいくつ以上なら，マージソートの方が速いか求めなさい．計算過程も示すこと．

(3)　アルゴリズムの効率を評価する指標として，上の文章にあるように解を求めるまでの計算時間を入力サイズ$n$の関数で表すことが多い．その理由を考えて，簡潔に述べなさい．