Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

第11回 変化に耐えるアルゴリズム

グラフ理論・動的計画法・整列アルゴリズム

← 备考目录

試験時間(目安)満点問題数
200分100点全3問
問題分野テーマ配点
問題1グラフ理論単一辺の変更と最小全域木35点
問題2動的計画法帯領域を通る編集列35点
問題3整列アルゴリズムキーの種類数に適応する安定整列30点

問題1 · グラフ理論(35点)

単一辺の変更と最小全域木

連結な単純無向グラフ G=(V,E)G=(V,E) の各辺には正の重みがあり、すべての重みは相異なる。最小全域木を TT とする。1回の問い合わせでは、1本の辺 ee の重みだけを新しい正の値 xx に変更する。変更後も全辺の重みは相異なるものとする。問い合わせ同士は独立であり、毎回元の G,TG,T から開始する。隣接リストを利用し、重みの比較・加算は定数時間で行える。以下では、変更された重みで評価した最小全域木を求めたい。

(1) 非木辺の減少(4点)

e∉Te\notin T の重みを減少させる場合を考える。TT 上の ee の両端点を結ぶ道と、そこに含まれる最大重みの辺 ff を用いて、TT を変更する必要がある条件と、変更後の木を述べよ。

(2) 交換の正しさ(7点)

(1)の判定と辺交換が正しいことを証明せよ。単に「閉路性質より」と述べるだけでなく、任意の競合する全域木から、同じ重み以下の候補木を作れることを説明せよ。

(3) 木辺の増加と他の変更(6点)

e∈Te\in T の重みを増加させる場合を考える。T−eT-e の二つの連結成分を結ぶ辺の集合から、代替辺を選ぶ方法を示せ。また、e∈Te\in T の減少と e∉Te\notin T の増加で TT が変わらない理由も述べよ。

(4) 独立問い合わせの具体例(7点)

頂点を {1,2,3,4,5}\{1,2,3,4,5\}、辺と重みを 12:2,23:4,34:5,45:3,13:7,25:8,15:1012:2, 23:4, 34:5, 45:3, 13:7, 25:8, 15:10 とする。元の TT と総重みを求めよ。次に、辺25を1に減少させる場合と、辺34を9に増加させる場合の新しい最小全域木を、それぞれ独立に求めよ。

(5) 線形時間の処理(6点)

前処理を行わず、どの種類の単一辺変更にも O(∣V∣+∣E∣)O(\vert V\vert +\vert E\vert ) 時間で答えるアルゴリズムを書け。木上の道の探索、削除後の成分の識別、代替辺の走査を区別し、補助空間も示せ。

(6) 祖先表と最大辺(5点)

e∉Te\notin T の減少だけが繰り返し問い合わせられるとする。根付き木の祖先を2のべき乗だけたどる表と、対応する道の最大辺を保持する表を設計せよ。前処理、記憶量、1問い合わせの計算量を示せ。

問題2 · 動的計画法(35点)

帯領域を通る編集列

文字列 L=L1…LmL=L_{1}\ldots L_{m} と R=R1…RnR=R_{1}\ldots R_{n} を考える。挿入と削除の費用は各1、異なる文字への置換は3、同じ文字の対応は0である。編集列を、格子上の (0,0)(0,0) から (m,n)(m,n) への道として表す。削除、挿入、対応はそれぞれ (1,0),(0,1),(1,1)(1,0),(0,1),(1,1) の移動に対応する。本問では、道のすべての頂点が ∣i−j∣≤b\vert i-j\vert \le b を満たすという制約を課す。bb は非負整数であり、制約を満たす道が存在しない場合の最適費用を ∞\infty とする。

(1) 状態と帯領域の境界(5点)

D(i,j)D(i,j) を帯領域内の (0,0)(0,0) から (i,j)(i,j) までの最小費用とする。境界条件と漸化式を示せ。帯領域の外の値をどのように扱うべきかも明記せよ。

(2) 編集列の具体例(6点)

L=ABCDL=ABCD、R=ACDR=ACD、b=1b=1 の DD の表を、帯領域外を ∞\infty として完成させよ。最小費用と、それを達成する編集列を一つ示せ。

(3) 正しさと制約なしとの比較(6点)

漸化式の正しさを最後の移動による場合分けで証明せよ。また、帯制約付きの値が制約なしの編集距離の下界・上界のどちらになるか述べ、厳しい不等号になる例を作れ。

(4) 帯内の計算と空間(6点)

帯領域にある格子点だけを列挙する擬似コードを書け。その格子点数を QQ とした時間計算量を示し、費用のみを求める場合に隣接2行だけを保持してよい理由と必要空間を説明せよ。

(5) 復元と終点の判定(6点)

最適な編集列を復元する方法を示せ。複数の最適な前状態がある場合の規則を一つ定め、記憶量と復元時間を示せ。さらに ∣m−n∣>b\vert m-n\vert >b の場合を計算前に判定できる理由を述べよ。

(6) 閾値判定の帯幅(6点)

制約なしの最小費用が整数 KK 以下かだけを判定したいとする。帯幅を b=Kb=K として計算してよいことを証明せよ。計算量を m,n,Km,n,K で評価し、K=0K=0 の場合にも適用できる式を示せ。

問題3 · 整列アルゴリズム(30点)

キーの種類数に適応する安定整列

NN 個のレコードがあり、各レコードは比較可能なキーと付随データを持つ。同じキーのレコードは元の入力順に出力する必要がある。入力に現れる相異なるキーの数を dd とするが、dd は事前には与えられない。比較・レコードの移動は定数時間とし、入力は読み取り専用、出力用配列は別に確保できる。本問では、dd が NN よりはるかに小さい場合の整列を考える。ハッシュの平均計算量には頼らず、最悪計算量を保証せよ。

(1) 平衡木と待ち行列(5点)

平衡二分探索木の各節点に同じキーのレコードの待ち行列を持たせる。入力を順に登録し、木を中順走査して出力する方法の正しさ、安定性、最悪時間と補助空間を示せ。

(2) 安定な中央値分割(6点)

別の方法として、長さ ss の列から中央値を O(s)O(s) 時間で選択できると仮定する。中央値のキーより小さい・等しい・大きいの三群へ安定に分割し、外側二群だけを再帰的に整列する方法を書け。安定性を証明せよ。

(3) キー頻度と時間計算量(6点)

(2)の時間が O(N(1+log⁡d))O(N(1+\log d)) となることを証明せよ。各キーの出現回数を f1,…,fdf_{1},\ldots ,f_d とし、そのキーが処理される深さを log⁡(N/fi)\log(N/f_{i}) と関連付けて評価せよ。

(4) 比較回数の下界(7点)

d≥2d\ge 2、N=drN=dr とし、各キーがちょうど rr 回現れる入力を考える。キーの配置の可能性の数を数え、三通りの比較結果を持つ決定木から Ω(Nlog⁡d)\Omega (N \log d) の最悪比較回数の下界を導け。

(5) 計数整列との比較(6点)

キーが整数 0,…,U−10,\ldots ,U-1 の場合の安定な計数整列を示し、上の比較法と比較せよ。さらに入力 [(b,1),(a,2),(b,3),(c,4),(a,5)][(b,1),(a,2),(b,3),(c,4),(a,5)] の安定な出力を求め、N=106,d=16,U=109N=10^{6},d=16,U=10^{9} ならどの方式を選ぶか根拠を述べよ。