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.

第5回 境界条件と計算モデル

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論全域木がBFS木になれる条件35点
問題2動的計画法曲がる回数を制限した格子経路35点
問題3整列アルゴリズム双調整列の仕事量と並列深さ30点

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

全域木がBFS木になれる条件

単純連結無向グラフGGの全域木TTと根rrが与えられる。TT上の深さをdepth⁡[v]\operatorname{depth}[v]とする。隣接頂点を調べる順序は頂点ごとに自由に選べる。TTがGGのBFS木として得られるかを調べたい。BFS木では各頂点の親はその頂点を初めて発見した頂点であり、単に最短距離の親を任意に選ぶ定義ではない。

(1) 深さと最短距離(6点)

TTがBFS木なら、すべての辺{u,v}\{u,v\}について∣depth⁡[u]−depth⁡[v]∣≤1|\operatorname{depth}[u]-\operatorname{depth}[v]|\le 1となることを証明せよ。さらに、この条件がTT上の深さとGGのrrからの最短距離の一致を保証することを証明せよ。

(2) 辺条件だけでは不十分な反例(7点)

上の辺条件だけでは、標準的なFIFOキューを用いるBFSでTTを実現できるとは限らない。rrの子a,ba,bと、深さ2の頂点x,yx,yについて、TTの親をparent⁡[x]=a, parent⁡[y]=b\operatorname{parent}[x]=a,\ \operatorname{parent}[y]=bとし、追加辺a−y,b−xa-y,b-xを入れた例で不可能性を示せ。

(3) 親と子ブロックの処理順序(8点)

各深さ層の頂点の処理順序を考える。深さd+1d+1の頂点vvの親ppが、同じ深さddの他の隣接頂点より先に処理される必要がある。この条件が必要であることを示し、親の順序が次層の子のブロック順序を制約することを説明せよ。

(4) 正しい判定法と計算量(8点)

TTがBFS木として実現できるかの簡単で正しい判定法を設計せよ。効率より正しさを優先し、各頂点の隣接順序をすべて列挙してBFSを実行する方法でもよい。上界を各頂点の次数deg⁡(v)\deg(v)で表せ。成功時と失敗時に返す内容を定めよ。

(5) 訪問順と最短距離(6点)

BFSにおいて「深さが同じ頂点はどの順に処理しても親木は変わらない」が誤りである理由を述べよ。一方、訪問順が変わっても最短距離は変わらないことを証明せよ。

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

曲がる回数を制限した格子経路

h×wh\times wの格子の各セルに整数得点a[i,j]a[i,j]があり、一部は障害物である。左上(1,1)から右下(h,wh,w)まで右または下へ移動する。訪問した各セルの得点を一度ずつ加える。連続する二移動の方向が異なるとき「曲がり」が1回あると数える。最初の移動は曲がりに数えない。曲がりがちょうどqq回の最大得点経路を求める。

(1) 状態と境界条件(6点)

最後の移動方向と曲がり回数を含む状態を定義し、初期値と障害物の扱いを示せ。h=w=1h=w=1の場合と、片方だけが1の場合を別に説明せよ。

(2) 方向別の漸化式(7点)

右移動で終わる状態と下移動で終わる状態の漸化式を導け。移動方向を記録しない二次元状態では不十分な理由を、同じセル・同じ曲がり回数の二つの接頭経路を用いて説明せよ。

(3) 正しさと到達不能状態(8点)

計算順序と正しさの証明を示し、時間・空間計算量をh,w,qh,w,qで評価せよ。到達不能状態を0で初期化すると誤る具体例を示せ。

(4) 具体例(8点)

障害物のない3×3格子の得点を、行ごとに

(a[i,j])=(1234−85678).(a[i,j])=\begin{pmatrix}1&2&3\\4&-8&5\\6&7&8\end{pmatrix}.

とする。q=1q=1とq=2q=2について最適得点と経路を求めよ。

(5) 最適経路数と復元(6点)

最大得点を達成する経路の本数も同時に求める方法を設計せよ。方向別の状態を足し合わせる際の二重計数の有無を説明し、最適経路一つの復元方法も示せ。

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

双調整列の仕事量と並列深さ

n=2kn=2^k個の値を、比較交換器からなるネットワークで整列する。比較交換器は二入力の小さい方と大きい方を指定された出力へ送る。互いに異なるワイヤを使う比較器は同時実行できる。双調列とは、循環シフト後に非減少区間と非増加区間の連結になる列であり、同値を許す。

(1) 双調併合の性質(5点)

長さnnの双調列について、距離n/2n/2の対を比較し小さい方を前半へ、大きい方を後半へ送る。前半・後半がそれぞれ双調で、前半の最大値が後半の最小値以下になることを証明せよ。0–1列の場合を先に示して一般値へ拡張してよい。

(2) 併合の仕事量と深さ(5点)

双調併合の比較器数M(n)M(n)と深さDm(n)D_m(n)の再帰式を導いて解け。同じ段でn/2n/2個の比較器が並列に動くことと、仕事量を区別せよ。

(3) 整列全体の仕事量と深さ(7点)

任意の列の前半を昇順、後半を降順に再帰整列して双調併合する。全比較器数S(n)S(n)と深さDs(n)D_s(n)の再帰式を解き、nlog⁡nn\log nとnlog⁡2nn\log^2 nのどちらが仕事量か明記せよ。

(4) 各比較段の具体例(7点)

双調列 [1,4,7,9,8,6,3,2][1,4,7,9,8,6,3,2]について、最初の比較段の出力、前半と後半それぞれの次の比較段の出力、最終昇順列を示せ。

(5) 処理器数と深さの下界(6点)

各段をpp個の処理器で実行する場合の実行時間の上界を、仕事量と深さで示せ。さらに、各出力値が依存し得る入力数から、比較ネットワークの整列深さにΩ(log⁡n)\Omega(\log n)の下界があることを説明せよ。