アルゴリズムイントロダクション第１章解答

この記事について

この記事は、アルゴリズムイントロダクション第1巻の問題を全て解くという壮大なプロジェクトの一環です。
間違いや指摘があれば遠慮なくコメントをください！

練習問題

1.1-1　

　ソートを必要とする実社会での応用あるいは凸包の計算を必要とする実社会での応用を説明せよ。

・勉強会のメンバーを名簿に整理するために、学年順にメンバーを並べ替える。
・物体が凸であるとは、ユーグリッド空間における物体の任意の2点を結んだ線分が、その物体内に含まれている状態のことを指す。凸集合とは、そのような物体の集合であり、凸包とは与えられた集合を含む最小の凸集合であると定義される。凸包の計算は、例えばある生物が存在する場所が座標としてわかるとき、ここからこの生物の生息範囲を調べることに利用できる。

1.1-2

実社会の枠組みの中で用いられる計算速度以外の効率の尺度をあげよ。

　・データを伝送する速さ
　・メモリの消費量

1.1-3

以前に見たことがあるデータ構造についてその長所と短所を述べよ。

　・連結リストは要素数の操作が用意だが、値の探索に時間がかかる

1.1-4

上で述べた最短路問題と巡回セールスマン問題の類似点を説明せよ。また、相違点は何か。

類似点
　・どちらもグラフとしてモデル化可能
　・どちらも莫大な計算量となる
　・どちらも近似アルゴリズムが考えられており、またそれが有効である

相違点
　・最短路問題はスタートからゴールまでの最短路だが、巡回セールスマン問題はスタートからスタートに戻る最短経路を求める。
　

1.1-5　

最適解しか意味を持たない実社会の問題を示せ。また、「近似解」でも十分に意味を持つ問題を示せ。

　ソートは最適解しか意味を持たない。
　平方根の値は「近似解」でも十分に意味を持つ。

1.2-1

アプリケーション層でアルゴリズムが必要になる応用の例を挙げ、必要とされるアルゴリズムの機能を議論せよ。

　入力した文章に出現する任意の単語の出現回数を調べてくれるwebアプリがあったとする。このアプリの実現のために、文章を単語の単位まで分割する必要がある。そして、文章の個々の単語が入力の単語と一致すればカウンタを1増やし、一致しなければ何もしないといったアルゴリズムが必要である。

1.2-2

　同じ計算上で挿入ソートとマージソートの実現を比較する。サイズnの入力に対して、挿入ソートの実現には8n^2ステップかかり、一方、マージソートの実行には64nlgnステップかかるとする。挿入ソートがマージソートに勝るnを求めよ。

これは、$8n^2$が$64nlgn$より小さいnの範囲を求めることと同義。従って、次のようなプログラムを用意する。

import math

n = 2
while True:
    x = 8*n**2
    y = 64*n*math.log(n,2)
    print(x,y)
    if x > y:
        break
    else:
        n += 1
        
print(n)

やってることは単純です。$8n^2$と$64nlgn$に２以上の値(真数1以下は定義されていない)を代入していって、前者のほうが大きくなったら停止するだけです。

これを実行すると答え　$1< n <44$　を得ます。

1.2-3

　同じ計算機上で、実行時間が100n^2のアルゴリズムが2^nのアルゴリズムより高速に実行できる最小のnを求めよ。

同様に計算して求めます。

import math

n = 2
while True:
    x = 2**n
    y = 100*n**2
    print(x,y)
    if x >= y:
        break
    else:
        n += 1
        
print(n)

これを実行すると $n = 15$が求めるnとなります。

章末問題

1-1

以下の表の各関数f(n)に対して、アルゴリズムが解くのにf(n)マイクロ秒かかるとき、t時間で解くことができる最大の問題サイズnを求めよ。

１マイクロ秒は$1.0×10^{-6}$秒です。この値と各関数を掛けたものが、1つの問題を解くのに必要な時間となります。つまり、$t=f(n)×1.0×10^{-6}$をnについて求める形になります。
例えば、
例１$lgn=log_2 n$の場合、
$a=1.0×10^{-6}$とし
$t = alog_2 n$
$\frac{t}{a}=log_2 n$
$({\frac{t}{a}})^2=n$
となります。
例２$\sqrt{n}$
$t = a*{\sqrt{n}}$
$\frac{t}{a}=\sqrt{n}$
$({\frac{t}{a}})^2=n$
つまり、与えられているのは$n$についての関数なので、逆関数を求める必要があるということです。

	1秒	1分	1時間	1日	1月	1年	1世紀
$lgn$	$10^{12}$	$10^{15.56}$	$10^{19.11}$	$10^{21.87}$	$10^{24.83}$	$10^{29.95}$	$10^{33.95}$
$\sqrt{n}$	$10^{12}$	$10^{15.56}$	$10^{19.11}$	$10^{21.87}$	$10^{24.83}$	$10^{29.95}$	$10^{33.95}$
$nlgn$
$n^2$	$10^{3}$	$10^{3.89}$	$10^{4.78}$	$10^{5.47}$	$10^{6.21}$	$10^{7.49}$	$10^{8.49}$
$n^3$	$10^{2}$	$10^{2.6}$	$10^{3.19}$	$10^{3.65}$	$10^{4.14}$	$10^{5}$	$10^{5.66}$
$2^n$	19	25	31	36	41	50	56
$n！$

$n!$や$nlgn$は解析的に解くことができません。従って、プログラムを使って解くことになりますが、それには天文学的な時間がかかるようです。私の頭ではここの計算方法が分かりませんでした。。。