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.

第15回 証明書と並列化

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

← 备考目录

試験時間(目安)満点問題数
200分100点全3問
問題分野テーマ配点
問題1グラフ理論指定された木はDFS木になり得るか35点
問題2動的計画法環状配置でちょうどr個を選ぶ35点
問題3整列アルゴリズム並列に安定併合する30点

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

指定された木はDFS木になり得るか

単純連結無向グラフ G=(V,E)G=(V,E)、根 rr、GG の全域木 TT が与えられる。TT の辺を根から子へ向け、祖先・子孫を定義する。DFS が隣接頂点を調べる順序は自由に選べる。本問では、ある隣接順序の下で DFS の探索木がちょうど TT になるかを判定し、可能なら具体的な隣接順序、不可能なら矛盾を証明する辺を出力したい。木TTを検査するための走査と、GGのDFS実行は区別すること。

(1) 非木辺の必要条件(5点)

GGのDFS木では、すべての非木辺の両端点が祖先・子孫の関係になることを証明せよ。片方の部分木の探索が完了したとき、未訪問の他方へ辺が残っている可能性を考えよ。

(2) 隣接順序による実現(6点)

「TT のすべての非木辺の両端点が祖先・子孫の関係なら、TT をDFS木として実現できる」という逆命題を証明せよ。各頂点で木の子への辺を先に調べる順序を用い、部分木外へ逸れない理由を説明せよ。

(3) 違反辺と具体的な順序(7点)

TT の辺を 12,13,24,25,36,3712,13,24,25,36,37、根を1、GGの追加辺を 14,17,4514,17,45 とする。実現不可能の証拠を求めよ。追加辺45だけを除いたグラフでは、TT を実現する各頂点の隣接順序を一つ示せ。

(4) 時刻による祖先判定(6点)

TTを一度走査して各頂点の入時刻 tin、出時刻 tout を求める。祖先関係を定数時間で判定する式を示し、すべての非木辺を検査するアルゴリズムと時間・空間を述べよ。

(5) 証明書と検証(6点)

可能な場合・不可能な場合の出力を「証明書」として定義せよ。受け取った隣接順序または違反辺を第三者が線形時間で検証できる理由を述べ、隣接順序の出力サイズも評価せよ。

(6) 有向グラフの反例(5点)

有向グラフで同じ必要十分条件を使うことはできるか。有向全域木の辺は根から子へ向くものとする。祖先関係にない非木辺を含むが、指定木をDFS木として実現できる小さな反例を作れ。

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

環状配置でちょうどr個を選ぶ

n≥3n\ge 3 個の位置が円環上にあり、位置iiの価値は整数 wiw_{i} である。負の価値も許す。隣接する位置を同時に選ばず、ちょうど rr 個を選んで価値和を最大化したい。位置1と位置nnも隣接する。0≤r≤n0\le r\le n、実現不能なら −∞-\infty を返す。本問では最大値だけでなく、最適集合の一つと、最適集合の個数も考える。集合は選んだ位置番号によって区別し、選ぶ順番は区別しない。

(1) 実現可能な個数と貪欲法(4点)

実現可能な rr の範囲を求め、必要性と十分性を示せ。また最大価値の位置から順に選ぶ貪欲法が誤る例を、n=6,r=2n=6,r=2 で作れ。

(2) 直線DPと境界(6点)

まず直線上の jj 個の位置からちょうど tt 個選ぶ状態 P(j,t)P(j,t) を定める。直前位置を選ばない制約を使った漸化式と、j=0j=0およびj=−1j=-1に対する境界条件を示せ。

(3) 円環の二場合(6点)

円環の問題を「位置1を選ばない」と「位置1を選ぶ」の二場合に分け、直線DPに帰着せよ。n=3n=3、r=0r=0、実現不能な個数も正しく扱う式にせよ。

(4) 最適集合の具体例(7点)

n=6n=6、価値 (8,−2,7,6,5,9)(8,-2,7,6,5,9) とする。r=2r=2 に対する二場合の最適値と最適集合を求めよ。さらに r=3r=3 の最適値・集合を求め、負の価値があるときも個数を守る必要性を説明せよ。

(5) 空間削減と復元(6点)

最適値の計算を O(nr)O(nr) 時間で行う擬似コードを示せ。直線の直前2行を利用する空間削減と、最適集合を復元する場合の記憶量・復元時間を区別して評価せよ。

(6) 最適集合の個数(6点)

各DP状態に最適集合の個数を追加する。候補値が同じ場合の加算と、円環の二場合の結合を示せ。重複を数えない理由と、個数が最大 nn ビット程度で格納できる理由を述べよ。

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

並列に安定併合する

昇順に整列済みの二つのレコード列 A,BA,B の長さを m,n≥1m,n\ge 1、N=m+nN=m+n とする。同じキーでは入力を AA の後に BB を連結した順序を保つ。添字は0から始まる。複数の処理器が同じ入力位置を読むことは許すが、同じ出力位置へ同時に書くことは許さない。1回の比較・読み書きを単位仕事とし、仕事量は全処理器の操作数の和、深さは依存関係に沿う最長操作数とする。必要な数の処理器を使用できる。

(1) 独立な出力位置の計算(5点)

各 A[i]A[i] と B[j]B[j] の出力位置を、相手側の二分探索で独立に求める式を導け。同キーの安定性のため、AA側は「未満」、BB側は「以下」を数える必要があることを説明せよ。

(2) 具体例と書込衝突(6点)

A=[(2,a1),(4,a2),(4,a3),(9,a4)]A=[(2,a_{1}),(4,a_{2}),(4,a_{3}),(9,a_{4})]、B=[(1,b1),(4,b2),(7,b3)]B=[(1,b_{1}),(4,b_{2}),(7,b_{3})] とする。各レコードの0始まりの出力位置と出力列を求めよ。一般にも出力位置の衝突が起こらないことを証明せよ。

(3) 仕事量と深さ(6点)

全要素で二分探索を同時実行する方法の仕事量・深さ・補助空間を示せ。単純な方法が浅い計算を実現していても、逐次の線形併合に比べ仕事量が大きくなる理由を述べよ。

(4) 分割による線形仕事量の併合(7点)

仕事量を O(N)O(N) に抑えるため、長い方の列の中央要素をピボットにし、他方でその順位を二分探索して、左右の二問題を並列に解く方法を書け。元の位置を加えた全順序で安定性を保ち、空列の場合も処理せよ。

(5) 深さと総仕事量の証明(6点)

(4)の各子問題の大きさが高々 3N/4+O(1)3N/4+O(1) となることを示し、深さ O(log⁡2(N+1))O(\log^{2}(N+1)) を導け。さらに大きさごとの節点数を使って、全二分探索とコピーの仕事量が O(N)O(N) であることを証明せよ。