第15回 証明書と並列化
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 200分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
指定された木はDFS木になり得るか¶
単純連結無向グラフ 、根 、 の全域木 が与えられる。 の辺を根から子へ向け、祖先・子孫を定義する。DFS が隣接頂点を調べる順序は自由に選べる。本問では、ある隣接順序の下で DFS の探索木がちょうど になるかを判定し、可能なら具体的な隣接順序、不可能なら矛盾を証明する辺を出力したい。木を検査するための走査と、のDFS実行は区別すること。
(1) 非木辺の必要条件(5点)¶
のDFS木では、すべての非木辺の両端点が祖先・子孫の関係になることを証明せよ。片方の部分木の探索が完了したとき、未訪問の他方へ辺が残っている可能性を考えよ。
(2) 隣接順序による実現(6点)¶
「 のすべての非木辺の両端点が祖先・子孫の関係なら、 をDFS木として実現できる」という逆命題を証明せよ。各頂点で木の子への辺を先に調べる順序を用い、部分木外へ逸れない理由を説明せよ。
(3) 違反辺と具体的な順序(7点)¶
の辺を 、根を1、の追加辺を とする。実現不可能の証拠を求めよ。追加辺45だけを除いたグラフでは、 を実現する各頂点の隣接順序を一つ示せ。
(4) 時刻による祖先判定(6点)¶
を一度走査して各頂点の入時刻 tin、出時刻 tout を求める。祖先関係を定数時間で判定する式を示し、すべての非木辺を検査するアルゴリズムと時間・空間を述べよ。
(5) 証明書と検証(6点)¶
可能な場合・不可能な場合の出力を「証明書」として定義せよ。受け取った隣接順序または違反辺を第三者が線形時間で検証できる理由を述べ、隣接順序の出力サイズも評価せよ。
(6) 有向グラフの反例(5点)¶
有向グラフで同じ必要十分条件を使うことはできるか。有向全域木の辺は根から子へ向くものとする。祖先関係にない非木辺を含むが、指定木をDFS木として実現できる小さな反例を作れ。
参考解答・採点の観点 — 問題1
(1) 非木辺の必要条件
祖先関係にない頂点を結ぶ辺があるとする。先に発見された側の部分木のDFS中、もう一方は未訪問であるか、すでに探索中・完了している。探索中なら祖先鎖に属するため仮定と矛盾。未訪問ならその辺を調べた時点で探索され、同じ部分木に入る。完了しているなら、その完了側の探索中に未訪問のへ辺を調べたはずで同じ矛盾になる。従って非木辺は祖先・子孫間だけに存在する。
(2) 隣接順序による実現
各頂点での子を任意の固定順に先に列挙し、その後に親と非木辺の隣接頂点を置く。根から帰納的に、子への木辺で開始した探索はの部分木を全て訪問する。部分木から外への非木辺の端点は祖先であり、すでに訪問済みなので新しい枝を作らない。子孫への非木辺は木の子の探索が全部終わった後に調べるため、その時点では訪問済み。従って追加の探索辺は生じず、木辺だけがDFS木を形成する。
(3) 違反辺と具体的な順序
45の両端は2の別の子なので祖先関係にない。この辺が不可能の証拠。45を除いた場合、一例は 。DFS木の子を先に調べる。発見順はであり、探索木は指定となる。
(4) 時刻による祖先判定
入るとき・出るときに異なる時刻を付ける。がの祖先(自分自身も許す)である条件は かつ 。木の走査 、非木辺の各端点についてどちらかの祖先関係が成立するかの検査 。合計 、時刻・親・スタックの補助空間 。辺番号を使って木辺を印付けすれば分類も線形。
(5) 証明書と検証
可能なら全頂点の隣接順序を出し、それに従うのDFSを実行して得た親辺がと一致するか検査する。各無向辺は両端から一回ずつ読まれるので 。不可能なら非木辺一本を出し、の時刻を求めて両端が祖先関係でないことを確認する。順序の出力には個の隣接項目と頂点ごとの区切りがあり 、違反辺証明書自体は 項目。
(6) 有向グラフの反例
根と子、木辺 、追加辺 を持つ有向グラフを考える。の順序をとすれば、先にが完了し、次にを探索するとは既訪問の完了頂点へ向かうだけで、指定木が実現する。しかしは祖先関係にない。有向では完了した部分木への辺が許されるため、無向の必要条件は成立しない。
問題2 · 動的計画法(35点)¶
環状配置でちょうどr個を選ぶ¶
個の位置が円環上にあり、位置の価値は整数 である。負の価値も許す。隣接する位置を同時に選ばず、ちょうど 個を選んで価値和を最大化したい。位置1と位置も隣接する。、実現不能なら を返す。本問では最大値だけでなく、最適集合の一つと、最適集合の個数も考える。集合は選んだ位置番号によって区別し、選ぶ順番は区別しない。
(1) 実現可能な個数と貪欲法(4点)¶
実現可能な の範囲を求め、必要性と十分性を示せ。また最大価値の位置から順に選ぶ貪欲法が誤る例を、 で作れ。
(2) 直線DPと境界(6点)¶
まず直線上の 個の位置からちょうど 個選ぶ状態 を定める。直前位置を選ばない制約を使った漸化式と、およびに対する境界条件を示せ。
(3) 円環の二場合(6点)¶
円環の問題を「位置1を選ばない」と「位置1を選ぶ」の二場合に分け、直線DPに帰着せよ。、、実現不能な個数も正しく扱う式にせよ。
(4) 最適集合の具体例(7点)¶
、価値 とする。 に対する二場合の最適値と最適集合を求めよ。さらに の最適値・集合を求め、負の価値があるときも個数を守る必要性を説明せよ。
(5) 空間削減と復元(6点)¶
最適値の計算を 時間で行う擬似コードを示せ。直線の直前2行を利用する空間削減と、最適集合を復元する場合の記憶量・復元時間を区別して評価せよ。
(6) 最適集合の個数(6点)¶
各DP状態に最適集合の個数を追加する。候補値が同じ場合の加算と、円環の二場合の結合を示せ。重複を数えない理由と、個数が最大 ビット程度で格納できる理由を述べよ。
参考解答・採点の観点 — 問題2
(1) 実現可能な個数と貪欲法
のとき、かつそのときに限り可能。選択位置ごとにその直後の非選択位置が必要で、これらは異なるため。逆にを選べば隣接しない。貪欲の反例は価値 、。最大の位置2を選ぶと位置を失い、残りの最大は0で合計10。位置なら合計16。
(2) 直線DPと境界
直線列の価値を とする。。位置を選ぶとを除くため二つ前へ戻る。、、も。では0。負価値でも「ちょうど」を表すため、実現不能状態を0にしてはならない。
(3) 円環の二場合
なら空集合の0を返す。では、1を除く直線から個選ぶ値 と、1を含めて隣接を除き直線から個選ぶ値 を計算し 。では後者の直線は空なのでを使う。必要個数が負または直線長から不可能なら。 は最初に棄却する。
(4) 最適集合の具体例
で1を除く場合は 、値。1を含む場合は、から1個選び最大7なので 、値15。従って全体は の16。では円環上の可能な集合は と の二つ。値は20と13なので 、20。例えば全て負の価値なら空集合0が最大になり得るが、の指定では空集合を許せない。
(5) 空間削減と復元
path(a, r):
prev2 と prev1 の境界を初期化
for j=1..len(a):
cur[0]=0
for t=1..r:
cur[t]=max(prev1[t], a[j]+prev2[t-1])
prev2=prev1; prev1=cur
return prev1[r]二つの直線問題を解いて 、は 。値だけなら3本の長さ配列で 。復元は採否を全状態に保存して 空間、選択なら を2、非選択なら1減らすので 時間。採用した円環のケースを最初に記録する。
(6) 最適集合の個数
実現可能な境界の個数を1、実現不能を0とする。採用・不採用の候補のうち値が大きい側の個数を取り、等しく有限なら両者を足す。二候補の集合は位置を含むかどうかで分離するので重複しない。円環の二ケースも位置1の有無で分離するため、同値なら個数を足す。集合数は以下、必要ビットは高々。整数加算を1操作とするなら 、通常のビット計算なら個数加算を含め という上界を得る。
問題3 · 整列アルゴリズム(30点)¶
並列に安定併合する¶
昇順に整列済みの二つのレコード列 の長さを 、 とする。同じキーでは入力を の後に を連結した順序を保つ。添字は0から始まる。複数の処理器が同じ入力位置を読むことは許すが、同じ出力位置へ同時に書くことは許さない。1回の比較・読み書きを単位仕事とし、仕事量は全処理器の操作数の和、深さは依存関係に沿う最長操作数とする。必要な数の処理器を使用できる。
(1) 独立な出力位置の計算(5点)¶
各 と の出力位置を、相手側の二分探索で独立に求める式を導け。同キーの安定性のため、側は「未満」、側は「以下」を数える必要があることを説明せよ。
(2) 具体例と書込衝突(6点)¶
、 とする。各レコードの0始まりの出力位置と出力列を求めよ。一般にも出力位置の衝突が起こらないことを証明せよ。
(3) 仕事量と深さ(6点)¶
全要素で二分探索を同時実行する方法の仕事量・深さ・補助空間を示せ。単純な方法が浅い計算を実現していても、逐次の線形併合に比べ仕事量が大きくなる理由を述べよ。
(4) 分割による線形仕事量の併合(7点)¶
仕事量を に抑えるため、長い方の列の中央要素をピボットにし、他方でその順位を二分探索して、左右の二問題を並列に解く方法を書け。元の位置を加えた全順序で安定性を保ち、空列の場合も処理せよ。
(5) 深さと総仕事量の証明(6点)¶
(4)の各子問題の大きさが高々 となることを示し、深さ を導け。さらに大きさごとの節点数を使って、全二分探索とコピーの仕事量が であることを証明せよ。
参考解答・採点の観点 — 問題3
(1) 独立な出力位置の計算
の位置は 、すなわちで厳密に小さいキーの個数を加える。 の位置は 、すなわちで同じキー以下の個数を加える。同キーはの全レコードがより先なので、この非対称な境界が必要である。各列内の同キーの順序は元ので保持される。
(2) 具体例と書込衝突
の位置は 、の位置は 。出力は 。元の全入力位置をキーと組にして辞書式に全順序を作れば、各式は「そのレコードより小さい全レコードの個数」を数えている。相異なる全順序順位はを一度ずつ取るので衝突せず、排他的な出力書き込みとなる。
(3) 仕事量と深さ
仕事量 、深さ 。全要素を同時に扱うため 処理器と各処理器の定数個の局所変数、すなわち補助空間 。出力配列も だが別に数える。逐次併合は隣り合う順位を共有して全体 比較なのに対し、この方式は各要素が二分探索を独立に繰り返し、一般には の仕事を使う。
(4) 分割による線形仕事量の併合
組 (キー,元の全入力位置) を比較する。長い列の中央位置のレコードを選び、短い列で未満の個数を二分探索する。出力区間の開始をbaseとするとを へ書く。左は と 、右は と を別々の出力区間へ並列に併合する。どちらかの入力が空なら残りを各位置へ並列コピー。小さい定数長は直接併合する。左右区間は重ならず、組の順序で分割するので安定性も保つ。
(5) 深さと総仕事量の証明
長い列の長さが少なくともであり、その半分を左右へ分けるため、他方が全て片側へ入っても子の長さは高々。従って再帰深さは 、各段の二分探索の深さは なので全深さ 。大きさが [) にある節点は、各経路で高々定数個がこの範囲に留まり、互いに独立な問題は要素を共有しないため 個。各節点の探索費用は なので総和は 。基底のコピー対象は互いに素な区間で総数。従って仕事量は線形である。