アルゴリズム入門

共通問題（2017 年度 A セメスター試験）[試験日時：2018 年 1 月 25 日第 3 限（60 分），答案用紙：1 部，計算用紙：1 枚，持ち込み一切不可]

内容に関する質問は受け付けない．問題の記述が曖昧な場合は，適切な仮定をおいて回答し，どのような仮定をおいたのか明記せよ．

問題 1
以下に示すロジスティック方程式は生物の個体数の変化を表すモデルのひとつである．

dx(t)= a · x(t) − b · x(t)2dt
ここで x(t) は時刻 t におけるその生物の個体数，a は自然増加率を表すパラメタ，b は餌や縄張りなどを巡る種内競争を表すパラメタである．微分 dx(t)/dt の近似値として小さな正の値 h を用いた差分 (x(t + h) − x(t))/h を用いることで，このモデルを計算機シミュレーションすることにした．なお初期値は x(t) = x0 （t ≤ 0）とした．以下の問に答えよ．

(1) 差分で近似した後の方程式は，x(t) を x(t − h) から求める漸化式だとみなすことができる．変数 a，b，h を用いて空欄 A ・ B を埋め，この漸化式を完成させよ．
x(t) = x0
Ax(t) =· x(t − h) −B· x(t − h)2

ただし t ≤ 0
ただし t > 0(2) 問 (1) の漸化式をふまえ，x(t) を再帰を用いて計算する関数 population およびループを用いて計算する関数 population loop を作成した．空欄 C ∼ E を埋めよ．2 箇所の空欄 D には同じプログラム断片が入る．なお，引数 t，a，b，h，x0 はそれぞれ漸化式の t，a，b，h，x0 に対応し，整数ではなく実数が入力されるものとする．また，( E ).ceil() は E の値の小数点以下を切り上げた整数である．
def population(t, a, b, h, x0)
def population loop(t, a, b, h, x0)
ifCx = x0for i in 0 .. ((x0E).ceil() - 1)else
x =Dx = population(t - h, a, b, h, x0)
end
Dx
end
end
end
(3) population(0.4, 0.5, 0.1, 0.25, 1.0) を計算する過程を再帰呼び出しの様子が分かるように説明せよ．計算過程が明確であれば計算結果を示す必要はない．
(5) 右のグラフの縦軸は population や population loopで近似計算をした値と近似せず精密に計算した値との差の絶対値（誤差），横軸は近似計算に用いた h の値である．
ある程度までは h が小さくなると誤差は減少するが，h がさらに小さくなると逆に誤差が大きくなった．この傾向はpopulation と population loop の両方で見られた．このような結果となった理由を述べよ．

absolute error(4) population と population loop を計算量の観点から比較せよ．
10-510-610-710-810-910-1010-1110-1210-1310-1410-15
10-5 10-6 10-7 10-8 10-910-1010-1110-1210-1310-1410-15h問題 2
下方に示すプログラムに関連して，以下の問に答えよ．なお，rand() は 0 以上 1 未満の浮動小数点数を一様分布に従いランダムに返すものである．

(1) 辺の長さ 1 の正方形にランダムに点を n 個うち，ある頂点から距離 1 未満の点の数を数えることで四半円の面積を近似的に求める関数 circle(n) を定義した． A ・ B に入れる式を示せ．
(2) A 君は x と y の右辺が全く同じ式であることに気がついた．そこで共通の式をまとめて変数 rに代入しておき rand() の呼び出しを 1 回にまとめることを考えた．circle を書き換えて circle2を定義したが，どうも四半円の面積ではないものを求めているようである．その理由と何を求めているかを述べよ．
(3) B 君は rand() が返すのが 0 から 1 の間の乱数なら，rand()**2 も 0 から 1 の間の数であることに気がついた．二乗すればよりランダムになるかと考え，circle を書き換えて circle3 を定義したが，どうも四半円の面積ではないものを求めているようである．その理由を述べよ．
(4) C 君は x と y の一つだけ新しい乱数を使い，もう一方は前回の乱数を再利用することを考えた．circle を書き換えて，circle4 を定義したところ，それらしい値を求めているようである．
その理由を述べよ．
(5) x 軸が [0, π) の範囲で，sin(x) 関数と x 軸で囲まれる範囲の面積を近似的に求める関数 wave(n)を定義した． C ∼ E を埋めよ．なお，必要ならば円周率 PI や sin 関数 sin(x) などを利用しても良い．
def circle(n)count = 0.0
for i in 0 .. (n - 1)
x = rand()y = rand()ifAcount = count + 1
end
end
B
end

def circle2(n)count = 0.0
for i in 0 .. (n - 1)r = rand()
x = r
y = r
if
A
count = count + 1
end
end
B
end

def circle4(n)count = 0.0
y = rand()for i in 0 .. (n - 1)
x = yy = rand()A
ifcount = count + 1
end
end
B
end

def circle3(n)count = 0.0
for i in 0 .. (n - 1)
x = rand() ** 2
y = rand() ** 2ifAcount = count + 1
end
end
B
end

include(Math)def wave(n)count = 0.0
for i in 0 .. (n - 1)
C
x =y = rand()ifDcount = count + 1
end
end
Eend

問題 3
p0 , p1 , . . . , pn−1 の n 人の交友関係を考える．各人の関係は二次元配列 rel に格納されており，pi と pj が直接の友人同士の場合 rel[i][j] および rel[j][i] の値は 1，そうでない場合には 0である．また rel[i][i] の値は 0 である（自身自分は直接の友人ではない）．pi と pj ，pj と pkが直接の友人同士のとき，「pi と pk は間に 1 人を介した友人」と言うことにする（pi と pk が直接の友人同士でも構わない）．間に 2 人を介した友人なども同様に定める．以上をふまえ以下の問に答えよ．なお，make1d(n) は長さ n で全要素が 0 の配列を作る関数であり，定義済みとする．
(1) rel が右のような配列であるとき，p0 , p1 , p2 , p3 の 4 人のうち，間に 2 人を介した友人は誰と誰か．間にどの 2 人を介しているかもあわせて答えよ．

rel = [[0, 1, 1, 0],[1, 0, 0, 1],[1, 0, 0, 0],[0, 1, 0, 0]](2) pi または pj と直接の友人である人を全て挙げる関数 either を作成した．この関数は，i，j ，n，rel を入力とし，長さ n の配列を返す．この配列の k 番目の要素は，pk が pi または pj と友人であれば 1，そうでなければ 0 である．空欄 A · B を埋めよ．
def either(i, j, n, rel)union(rel[ A ], rel[ B ], n)
end

def union(r1, r2, n)r = make1d(n)for i in 0 .. (n - 1)
if (r1[i] == 1 || r2[i] == 1)
r[i] = 1
end
endr
end
(3) ps と間に 1 人を介した友人を全て挙げる関 def friends1(s, n, rel)
数 friends1 を作成した．この関数は，s，n， result = make1d(n)for i in 0 .. (n - 1)
rel を入力とし，長さ n の配列を返す．この配if rel[ C ][ D ] == 1
列の k 番目の要素は，pk が間に 1 人を介したE, n)
result = union(result,友人であれば 1，そうでなければ 0 である．空end
欄 C ∼ E を埋めよ．
end
resultend(4) ps と間に k 人を介した友人を全て挙げる再帰関数 friends k を作成した．この関数は，s，k ，n，rel を入力とし，出力は friends1 と同様の形式である．空欄 F ∼ H を埋めよ．
def friends k(s, k, n, rel)def friends sub(s, n, rel, rel2)
if k == 0
result = make1d(n)rel[ F ]for i in 0 .. (n - 1)else
if rel2[ G ] == 1
rel2 = friends k(s, k - 1, n, rel)H, n)result = union(result,friends sub(s, n, rel, rel2)
end
end
end
end
resultend(5) friends k(s,k,n,rel) の実行時間を n と k を用いてオーダ記法で示せ．その理由も簡単に説明すること．