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.

第20回 総合設計:故障・予算・適応性の証明

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

← 备考目录

試験時間(目安)満点問題数
210分100点全3問
問題分野テーマ配点
問題1グラフ理論全単一辺故障に対する最短路の証明書35点
問題2動的計画法予算を守りながら最悪区間を最小化する35点
問題3整列アルゴリズム区間構造と重複構造のよい方を使う安定整列30点

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

全単一辺故障に対する最短路の証明書

連結単純無向グラフ GG の辺重みはすべて厳密に正である。異なる s,ts,t に対し、各辺 ee を1本削除したグラフでの s−ts-t 最短距離 DeD_{e} をすべて求めたい。到達不能なら ∞\infty とする。元の最短パス P=(p0=s,p1,…,pk=t)P=(p_{0}=s,p_{1},\ldots ,p_{k}=t)、その長さ DD、全頂点への距離 ds,dtd_{s},d_{t} を考える。PP を含む ss 根の最短路木 TsT_{s} と、逆向きの PP を含む tt 根の最短路木 TtT_{t} を選ぶ。頂点 uu の TsT_{s} 上の最も近い PP 祖先を pa(u)p_{a(u)}、TtT_{t} 上の最も近い PP 祖先を pb(u)p_{b(u)} とする。未知の高度なアルゴリズムを引用せず、区間への最小値更新から設計せよ。

(1) 非パス辺の故障と最短路木(5点)

e∉Pe\notin P なら De=DD_{e}=D であることを示せ。各 PP 辺について最短路を再計算する素朴な方法の時間を評価せよ。また、Ts,TtT_{s},T_{t} がそれぞれ PP を含むように親を選べる理由と、正の重みを仮定する意義を説明せよ。

(2) 二つの木のラベル(6点)

Lj=ds(pj)L_{j}=d_{s}(p_{j}) とする。uu までの両最短路木の PP 外部分の長さを使い、a(u)≤b(u)a(u)\le b(u) を証明せよ。両木は別々なので「同じ部品に属するはず」と説明するだけでは十分でない。

(3) 故障辺を避ける歩道(7点)

非 PP 辺 {u,v}\{u,v\} を向き u→vu\to v で考え、z=ds(u)+w(u,v)+dt(v)z=d_{s}(u)+w(u,v)+d_{t}(v) とする。故障 ei={pi−1,pi}e_{i}=\{p_{i-1},p_{i}\} に対し a(u)<i≤b(v)a(u)<i\le b(v) なら、zz の長さの s−ts-t 歩道が eie_{i} を避けることを示せ。閉路が含まれても距離の上界に使える理由を述べよ。

(4) 最適回避パスと区間候補(8点)

各非 PP 辺を両方向に考えると、DeiD_{ei} が「ii を区間 [a(u)+1,b(v)][a(u)+1,b(v)] に含む候補 zz の最小値」に等しいことを証明せよ。下からの不等式だけでなく、任意の最適な故障回避パス上で候補を見つけること。PP の辺を候補に入れない理由も示せ。

(5) 区間木と全体の計算量(5点)

長さ kk の配列を ∞\infty で初期化する。各候補の区間に zz との最小値更新を行う処理を、二分された区間木の各節点への最小タグとして O(log⁡(k+1))O(\log(k+1)) 時間で行う方法を説明せよ。距離計算・木のラベル・最終展開を含む全擬似コードと計算量を示せ。

(6) 全故障距離の具体例(4点)

P=s−a−b−tP=s-a-b-t の辺重みは順に1,2,11,2,1。非 PP 辺は s−x:2,x−b:2,a−y:3,y−t:2,x−y:2s-x:2,x-b:2,a-y:3,y-t:2,x-y:2。TsT_{s} では yy の PP 祖先を aa、TtT_{t} では xx の PP 祖先を bb と選ぶ。a(x),b(x),a(y),b(y)a(x),b(x),a(y),b(y) と PP の3辺の故障距離を求めよ。

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

予算を守りながら最悪区間を最小化する

長さ nn の列を、空でない連続区間 KK 個(1≤K≤n1\le K\le n)に分割する。区間 [i,j][i,j] の費用 c(i,j)c(i,j) と悪さ d(i,j)d(i,j) は非負整数で、全 O(n2)O(n^{2}) 個の値が表で与えられる。予算BBは非負整数とし、費用和はBB以下とする。区間の悪さの最大値を最小化したい。同じ最大値なら費用和が小さい分割を選ぶ。c,dc,d の長さに関する単調性や加法性は仮定しない。最大値という非加法的な目的と、費用和という制約を混同せず、状態を増やす方法と判定問題へ変える方法の両方から考えよ。実現可能な分割がなければ不可能と答える。

(1) 予算軸の完全DP(5点)

D(i,k,b)D(i,k,b) を先頭 ii 要素を kk 区間へ分割し、費用和がちょうど bb のときの最小の悪さの最大値とする。境界値と最後の区間を用いた漸化式を導け。空の分割の最大値を0とすること。

(2) 状態の競合と支配(6点)

同じ (i,k)(i,k) について「悪さの最大値が最小の状態」だけを残すと失敗する理由を、費用・悪さの組で示せ。予算を使う後続区間との組合せも考え、二つの状態の正しい支配関係を定義せよ。

(3) 閾値ごとの最小費用(6点)

閾値 λ\lambda を固定して悪さ d(i,j)≤λd(i,j)\le \lambda の区間だけを許す。Cλ(i,k)C_{\lambda}(i,k) をその条件での最小費用とし、予算を状態に持たない漸化式を導け。Cλ(n,K)≤BC_{\lambda}(n,K)\le B の真偽が λ\lambda に対して単調になることを証明せよ。

(4) 二分探索と復元(7点)

最適な λ\lambda が区間悪さ表のいずれかの値であることを示せ。異なる値の整列と二分探索によって解く擬似コード、時間・空間・復元方法を示せ。予算 BB が非常に大きい場合、(1)より有利となる理由を述べよ。

(5) 重み和では選べない解(6点)

n=4,K=2n=4,K=2 の各切断位置 t=1,2,3t=1,2,3 に対し、二つの区間の費用和と悪さ最大が順に (1,9),(5,6),(6,1)(1,9),(5,6),(6,1) になる入力を構成せよ。B=5B=5 の答えを求め、費用+α×+\alpha \times悪さ(α≥0\alpha \ge 0)だけの最小化ではこの答えを得られないことを証明せよ。

(6) 二方法と最小費用の保証(5点)

(1)の完全 DP と(4)の判定法を比較せよ。最適な最大値に加えて最小費用の分割を返すために、二分探索終了後の最後の DP で何を保存すべきかを説明せよ。区間の悪さが一般整数でも同じ方法が使えるか。

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

区間構造と重複構造のよい方を使う安定整列

N≥2N\ge 2 個のレコードにはキーと元の位置がある。相異なるキーの個数を dd、昇順のキー群の出現数を f1,…,fdf_{1},\ldots ,f_d とし、Hkey=∑(fi/N)log⁡2(N/fi)H_{\mathrm{key}}=\sum (f_{i}/N)\log_{2}(N/f_{i}) とする。別に、非減少区間と厳密な減少区間を左から最大まで取り出し、減少区間だけを反転して得る kk 区間の長さを rir_{i}、Hrun=∑(ri/N)log⁡2(N/ri)H_{\mathrm{run}}=\sum (r_{i}/N)\log_{2}(N/r_{i}) とする。正しい安定整列と、期待時間 O(N(1+min⁡(Hkey,Hrun)))O(N(1+\min(H_{\mathrm{key}},H_{\mathrm{run}}))) の両立を目指す。キーは比較だけで扱い、入力の値は乱数を引く前に固定される。作業配列 O(N)O(N) は使用してよい。 最後の改良では、サイズ ss のキー列の正確な中央値を O(s)O(s) 時間で求める決定的な選択手続きを使えるものとする。元レコードを並べ替えず、キーの作業コピーで選択してよい。

(1) 安定三分割と比較確率(5点)

一様に選んだレコードをピボットとし、ピボット自身以外の全レコードを小・同・大へ順序を保って分け、小・大だけを再帰整列する。安定性を証明せよ。異なるキー群 i<ji<j の特定2レコードが比較される確率を、Fij=∑h=ijfhF_{ij}=\sum _{h=i}^j f_h を用いて求めよ。

(2) 期待時間とキー頻度(6点)

(1)から期待比較数が N−d+2∑i<jfifj/FijN-d+2\sum _{i<j}f_{i}f_{j}/F_{ij} となることを導け。x/(a+x)≤ln⁡((a+x)/a)x/(a+x)\le \ln((a+x)/a) を使い、これを N+2Nln⁡2⋅HkeyN+2N \ln2\cdot H_{\mathrm{key}} 以下に抑え、分割・コピーの総期待時間も O(N(1+Hkey))O(N(1+H_{\mathrm{key}})) と示せ。

(3) 区間長に適応する併合木(5点)

区間長 rir_{i} に対する葉順を保つ併合木を構成し、費用 O(N(1+Hrun))O(N(1+H_{\mathrm{run}})) を達成せよ。各区間の重み幅 ri/Nr_{i}/N の中点を含む二進区間と、長さ ⌈log⁡2(N/ri)⌉+1\lceil \log_{2}(N/r_{i})\rceil +1 の接頭語を用いてよい。初期区間抽出と木構築も費用に含めること。

(4) 二方法の交互実行(4点)

「まず平衡探索木で dd と頻度をすべて調べ、それから速い方を選ぶ」方法が目標を満たさない例を示せ。代わりに、入力の二つのコピーで(1)と(3)を1演算ずつ交互に進め、先に完成した出力を採用する方法の期待時間・安定性・空間を証明せよ。

(5) 頻度だけの情報量下界(4点)

頻度 fif_{i} だけを約束し、入力の並びを任意とする場合の比較決定木の下界を示せ。その下界が Ω(N(1+Hkey))\Omega (N(1+H_{\mathrm{key}})) となる総時間の評価と、Hrun が小さい特定入力への高速性が矛盾しないことを説明せよ。

(6) 期待保証と決定的な改良(6点)

(4)のランダム実行の期待時間を最悪保証と読み替えられないことを、q≥2,N=q2q\ge 2,N=q^{2}、0がN−qN-q個、1,…,q1,\ldots ,qが各1個の区間分断入力で示せ。次に、与えられた正確な中央値選択を使い、各キー群の処理回数を評価して決定的 O(N(1+Hkey))O(N(1+H_{\mathrm{key}})) を証明せよ。区間法との交互実行で最終的にどの保証を得るか。