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.

第16回 故障に強い証明・循環する状態・順序制約

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

← 备考目录

試験時間(目安)満点問題数
210分100点全3問
問題分野テーマ配点
問題1グラフ理論全域木の全辺故障をまとめて診断する35点
問題2動的計画法何周してもよい環状局所アラインメント35点
問題3整列アルゴリズム並列段数を制限した最適な隣接併合30点

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

全域木の全辺故障をまとめて診断する

連結単純無向グラフ G=(V,E)G=(V,E) の各辺に正の重み w(e)w(e) があり、n=∣V∣≥2n=\vert V\vert \ge 2、m=∣E∣m=\vert E\vert とする。全域木 TT が一つ与えられる。木辺 ee を除くと TT は二つの成分に分かれる。その間を結ぶ非木辺の最小重みを r(e)r(e) とし、候補がなければ r(e)=∞r(e)=\infty とする。R(T)=max⁡{r(e):e∈T}R(T)=\max\{r(e):e\in T\} を、どの木辺が1本故障しても必要となる修復辺の最大重みと定義する。修復は TT の残りの辺を保って1本だけ追加する。単一の故障だけを調べる方法から出発し、全木辺に対する判定をまとめる方法を設計せよ。

(1) 修復候補と木パス(5点)

非木辺 f={u,v}f=\{u,v\} が木辺 ee の修復候補となる必要十分条件を、TT 上の u−vu-v パスを用いて示せ。「ee の端点に接続する非木辺だけを調べればよい」という主張への反例も与えよ。

(2) MSTの故障後の総重み(6点)

さらに TT が最小全域木であるとする。G−eG-e が連結ならば、その最小全域木の総重みは W(T)−w(e)+r(e)W(T)-w(e)+r(e) であることを証明せよ。R(T)R(T) と故障後の最大総重みは異なる指標であることにも注意せよ。

(3) 全木辺の修復候補(7点)

すべての非木辺について木上のパスをたどることで、各 r(e)r(e) と、その値を達成する修復辺を計算するアルゴリズムを示せ。時間と補助空間を評価し、計算結果だけでなく候補辺も保存する意義を述べよ。

(4) 閾値と差分集計(7点)

重みの閾値 BB を固定する。TT を根付き木とし、w(f)≤Bw(f)\le B の非木辺 f={u,v}f=\{u,v\} ごとに差分配列へ +1 を u,vu,v、-2 を LCA(u,v)LCA(u,v) に加える。子の値を親へ加算した後、非根頂点 xx の値が何を表すか証明し、R(T)≤BR(T)\le B の判定法を導け。

(5) 祖先表と二分探索(6点)

祖先を 2j2^j 段ずつ記録する表を使って LCA を計算する方法を説明せよ。非木辺の重みを整列し、(4)の判定と二分探索で R(T)R(T) を求める擬似コードを書け。LCA は最初に各非木辺について1回だけ求め、判定で再利用すること。

(6) 故障診断の具体例(4点)

TT がパス 1−2−3−4−51-2-3-4-5 で、木辺の重みが順に 2,2,3,12,2,3,1、非木辺が (1,3,4),(2,4,6),(3,5,5),(1,5,9)(1,3,4),(2,4,6),(3,5,5),(1,5,9) である。括弧内は両端点と重みである。各 r(e)r(e)、R(T)R(T)、および各故障後の最小全域木の総重みを求めよ。

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

何周してもよい環状局所アラインメント

文字列 L=L1…LmL=L_{1}\ldots L_{m} と環状文字列 C=C1…CnC=C_{1}\ldots C_{n}(m≥1,n≥2m\ge 1,n\ge 2)がある。CC は正方向に何周してもよい。LL の連続部分文字列と周期列 CCCCC…CCCCC\ldots の有限連続部分文字列をアラインする。各列は文字対、LL の文字とギャップ、またはギャップと CC の文字であり、両側ギャップは禁止する。文字対の得点は S(x,y)S(x,y)、同じ側の連続長 k≥1k\ge 1 のギャップ得点は −(go+kge)-(g_{o}+k g_{e})(go,ge>0g_{o},g_{e}>0)である。空アラインメントの得点は0。H(i,j)H(i,j) は最後に消費した LL の位置 ii と CC の位置 jj における局所最大得点とし、空も候補に含める。CC を消費しない列では jj を固定する。

(1) 境界と空アラインメント(5点)

E(i,j)E(i,j) を最終列が (Li,−)(L_{i},-) の最大得点、F(i,j)F(i,j) を最終列が (−,Cj)(-,C_{j}) の最大得点とする。H(0,j),E(0,j)H(0,j),E(0,j) の境界値を定めよ。空アラインメントと実現不能状態を混同しないよう説明せよ。

(2) 前行からの更新(7点)

p(1)=n,p(j)=j−1p(1)=n,p(j)=j-1(j>1j>1)とする。前の行の H,EH,E が既知のとき E(i,j)E(i,j) の漸化式を導け。また B(i,j)B(i,j) を、最終列が LL 側のギャップではない場合の最大得点(空を含む)として、BB の式を導け。

(3) 最終ギャップと環状伝播(7点)

F(i,j)F(i,j) を最終ギャップの長さ kk と BB を用いて表せ。kk を無制限に試す必要がないことを証明せよ。さらに、環状配列の j=1j=1 から nn への通常の1回走査だけでは正しい行が得られない反例を与えよ。

(4) 二回の走査による閉包(7点)

V[j]=B(i,j)−goV[j]=B(i,j)-g_{o} と初期化し、j=1,…,nj=1,\ldots ,n の順に V[j]←max⁡(V[j],V[p(j)]−ge)V[j]\gets \max(V[j],V[p(j)]-g_{e}) を2回走査する。この処理が必要な環状閉包を与えることを証明し、全行を O(mn)O(mn) 時間で求める擬似コードを書け。

(5) 周回する具体例(5点)

L=AABAL=AABA、C=BAC=BA、同字得点4、異字得点-5、go=2,ge=1g_{o}=2,g_{e}=1 とする。i=0,…,4i=0,\ldots ,4 の H(i,1),H(i,2)H(i,1),H(i,2) を求め、最高得点のアラインメントを一つ示せ。環状境界を越える場所も明記せよ。

(6) 循環ポインタを使わない復元(4点)

最高得点のアラインメントを復元する情報を設計せよ。2回の走査による同じ行の依存を、循環するポインタにせず保存する方法を説明し、得点のみと復元つきの場合の空間を評価せよ。

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

並列段数を制限した最適な隣接併合

kk 本の連続区間 R1,…,RkR_{1},\ldots ,R_{k} がそれぞれ非減少順に整列され、長さ ri≥1r_{i}\ge 1、N=∑riN=\sum r_{i} が与えられる。操作は、現在隣接する二つの区間の安定併合だけであり、長さ a,ba,b の費用を a+ba+b と定める。さらに併合木の高さを整数 h≥0h\ge 0 以下に制限する。これは、一つの要素が参加する併合回数、または独立併合を同時に行う場合の併合段数の上限である。個々の併合そのものの並列深さは数えない。葉順は R1,…,RkR_{1},\ldots ,R_{k} を保ち、高さ制約の下で総移動費用を最小化したい。実行可能な木がなければ ∞\infty とする。

(1) 深さと隣接制約(5点)

葉 ii の深さ did_{i} により総費用が ∑ridi\sum r_{i}d_{i} となることと、高さ制約がすべての di≤hd_{i}\le h であることを示せ。r=(1,100,1),h=2r=(1,100,1),h=2 で、隣接制約あり・なしの最小費用を比較せよ。

(2) 高さ制約付きの区間DP(7点)

D(i,j,h)D(i,j,h) を Ri,…,RjR_{i},\ldots ,R_{j} を高さ hh 以下で一つにする最小費用とする。h=0h=0 と i=ji=j の境界、最後の併合の分割による漸化式を導け。実現可能性が j−i+1≤2hj-i+1\le 2^h と同値であることを証明せよ。

(3) 表の計算と木の復元(6点)

累積和を使い、高さごとの表 DD と最適な分割を計算する擬似コードを書け。O(k3h)O(k^{3}h) 時間・O(k2h)O(k^{2}h) 空間の評価を示し、併合木の復元と実際の整列費用を区別せよ。h>k−1h>k-1 の場合には表の高さを打ち切ってよい理由も述べよ。

(4) 高さと仕事量の具体例(5点)

r=(1,1,1,10)r=(1,1,1,10) について h=2h=2 と h=3h=3 の最適費用と併合木を求めよ。各高さで根の三つの分割を評価し、高さを1段増やすと仕事量を減らせることを確認せよ。

(5) エントロピーによる下界(7点)

pi=ri/Np_{i}=r_{i}/N、H=∑pilog2(1/pi)H=\sum p_ilog_{2}(1/p_{i}) とする。葉深さの ∑2−di≤1\sum 2^{-d_{i}}\le 1 から、実現可能な高さ制約付き木にも総費用≥NH\ge NH が成り立つことを示せ。⌈log⁡2k⌉≤h\lceil \log_{2}k\rceil \le h のときの N⌈log⁡2k⌉N\lceil \log_{2}k\rceil の上界と、実現不能な場合を比較せよ。