第10回 二重故障・区間の個数・桁の並列処理
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
二つの木辺を失ったときの連結性¶
単純連結無向グラフ 、全域木 、相異なる木辺 が与えられる。、 とする。非木辺 を に加えるとできる閉路を基本閉路と呼ぶ。木辺 について、基本閉路が を含む非木辺の集合を とする。 から を同時に除いたときの連結性を、これらの集合だけで判定したい。集合は辺番号ごとの配列で厳密に保持し、ハッシュ衝突の可能性を正しさの根拠にしてはならない。
(1) 基本閉路と橋(6点)¶
非木辺がに属することと、の二成分をが結ぶことが同値であると証明せよ。さらに、が空であることが、がの橋であるための必要十分条件であることを示せ。
(2) 三成分の縮約(7点)¶
からを除くと三成分になる。これらを頂点に縮約し、非木辺を加えた補助グラフを考える。三成分間の辺を「だけに属する」「だけに属する」「両方に属する」の三種類と対応付け、が入れ子の位置と別の枝の位置にある場合を説明せよ。
(3) 二重故障の必要十分条件(8点)¶
が非連結であるための必要十分条件が、、、のいずれかであることを証明せよ。「各辺が単独では橋でないなら、二本同時に消しても連結」という主張を反例で否定せよ。
(4) 木パスの具体例(8点)¶
をのパスとする。非木辺が14だけの場合と、の二本の場合について、各を求め、相異なる木辺二本の全ての組の故障結果を判定せよ。ijは辺の略記である。
(5) 前処理と分断の証明書(6点)¶
全てのを前処理する方法と、問い合わせに答える手順を示せ。素朴な木パス探索による時間、集合の記憶量、一問い合わせの最悪時間を評価せよ。非連結と判定した際、三成分の縮約を使って分断を証明する頂点集合を出力する方法も示せ。
参考解答・採点の観点 — 問題1
(1) 基本閉路と橋
木上のの両端間パスがを含むことは、その両端がの異なる成分にあることと同値。が非空ならその辺で両成分を再接続でき、空なら木辺以外に基本カットを渡る辺がないのでは橋。
(2) 三成分の縮約
の三成分は、で結ぶと三頂点のパスになる。端の二成分を結ぶ非木辺は両方の木辺を必要とし、に属する。中央と一方の端を結ぶ辺は該当する片方だけに属する。両方に属さない辺は成分内のループ。入れ子では祖先側・中間・子孫側が三成分、別枝では根側と二つの枝が三成分であり、同じ三頂点パスの議論が使える。
(3) 二重故障の必要十分条件
三頂点のグラフが連結である条件は、三種類の成分間辺のうち少なくとも二種類が存在すること。が非空で相異なるなら、両方と片方、または二つの片方という少なくとも二種類が存在する。逆に片方が空なら対応する基本カットが切れ、両者が等しく非空なら端同士の辺だけで中央が孤立する。四角形では単独のどの辺も橋でないが、相異なる木辺二本を消すと非連結。
(4) 木パスの具体例
14だけならで、三つの故障組全てが非連結。なら。各集合は非空で相異なるので、のどの組を消しても連結。
(5) 前処理と分断の証明書
根付きの親と深さを作り、各非木辺の両端から共通祖先まで上がり、通過木辺の集合ビットを立てる。ゼロ初期化を含め時間・ビット(通常の配列実装なら語)の記憶。各集合の空判定は前保存し、集合一致の厳密比較は、問い合わせも。証明書はの三成分をで求め、非木辺を走査して補助グラフの連結成分の一つを選ぶ。その元頂点の和集合は、削除後に外へ出る辺を持たない真部分集合であり、追加時間で検証可能。
問題2 · 動的計画法(35点)¶
ギャップ区間をちょうどq個にする¶
文字列の長さをとする。全体をアラインメントし、同字の文字対は3、異字の文字対は-4、ギャップ一列は-1の得点とする。両側ギャップは禁止する。「ギャップ区間」は、同じ側のギャップが連続する極大の列区間である。異なる側のギャップが隣接することは許し、その場合は別の二区間と数える。非負整数が指定され、ギャップ区間がちょうど個の最大得点を求める。解がなければとする。
(1) 三状態と初期値(6点)¶
消費済み文字数、ギャップ区間数、最後の列の種類を記録する三状態を定義せよ。空の開始状態と実現不可能な状態の初期値を示し、接頭辞の片方だけが空の場合も扱え。
(2) 区間数を数える漸化式(7点)¶
三状態の漸化式を導け。同じ側のギャップの延長、文字対の後の開始、反対側のギャップからの切替を区別し、どの場合にが増えるかを示せ。
(3) 正しさと計算量(8点)¶
最後の列を除くことに基づいて正しさを証明せよ。計算順序と時間・得点だけの場合の空間を示せ。なら計算せず実現不能と答えてよい理由も述べよ。
(4) 具体例と実現不可能性(8点)¶
についての最適得点と、可能な場合のアラインメントを求めよ。が不可能となることは表の数値だけでなく、両文字列の長さから説明せよ。
(5) 末尾状態と復元(6点)¶
同じで最大得点一つだけを残し、末尾の種類を忘れる方法が不適切な理由を示せ。に到達するとを比べ、次の側の文字をギャップへ対応させると何が異なるか説明せよ。最適解一つの復元方法と必要領域も示せ。
参考解答・採点の観点 — 問題2
(1) 三状態と初期値
は文字対で終わる最大、は、はで終わる最大とする。空を特別にと置き、それ以外の初期値は。負添字とは。ならだけ、ならだけが漸化式で作られる。最後は。
(2) 区間数を数える漸化式
、は3または-4。。
。
。開始・切替は新しい極大区間なので1増え、同じ側の延長は増えない。文字対は区間を増やさない。
(3) 正しさと計算量
最終列の三場合は全アラインメントを覆い、ギャップの直前の種類で個数の増加が一意に決まる。同じ状態のより良い接頭解に置換しても将来の区間数は変わらない。昇順に処理してを列挙すれば依存先が先に完成する。時間、行を2枚なら補助空間。各区間は少なくとも一文字を消費するので区間数。
(4) 具体例と実現不可能性
はで。は不可能。長さが等しいので、ギャップが存在すれば片側のみのギャップでは文字消費数が釣り合わず、両側に少なくとも一区間ずつ必要。はで。一致列はの一つしか作れず、ギャップを使うなら少なくとも二列必要なので1が上界となり達成される。
(5) 末尾状態と復元
二つの接頭解はともに得点-2、区間数2だが、前者は側文字の列()、後者は側文字の列()で終わる。次ので前者は新区間を開始して、後者は延長して。得点と個数だけでは将来の合法性を決められない。各状態に選んだ前状態と添字を保存し、終端から文字対・ギャップを逆追跡する。全記録、復元。
問題3 · 整列アルゴリズム(30点)¶
符号付き整数の安定基数整列と並列化¶
個のレコードのキーはビットの2の補数整数で、範囲はからである。は正整数。キーのビット表現から最上位の符号ビットを反転した非負整数を作り、ビットずつの桁を下位から処理する。、基数、段数。最上位の不足ビットは0で補う。ビット語のビット抽出と整数添字演算をとする。各段では安定な計数整列を用いる。
(1) 符号ビットの反転(5点)¶
符号ビットの反転が符号付きキーの昇順を非負整数の昇順へ変える理由を証明せよ。負のキーを通常の非負ビット表現としてそのまま整列すると誤る例を示せ。
(2) 安定な一桁計数整列(5点)¶
一桁の安定な計数整列の擬似コードを書け。計数、各桁値の出力開始位置、入力の走査方向を明記し、時間・作業領域を評価せよ。
(3) 下位桁からの不変条件(7点)¶
下位から桁を処理した後の不変条件を示し、段後に安定整列されることを証明せよ。上位桁の段が安定でないと失敗する例を、二桁の非負整数で構成せよ。
(4) 符号付き整数の具体例(7点)¶
として[-]を処理する。符号ビット反転後の値を16進数で示し、各桁の段の終了時のレコード順と最終結果を求めよ。同キーの識別子付きレコードを加えた場合の順序も説明せよ。
(5) 衝突のない並列化(6点)¶
入力を個の連続ブロックに分け、各ブロックの走査は一つの処理器で行う。ヒストグラム処理では必要な数の処理器を利用できる仕事・深さモデルとする。桁別ヒストグラム、同桁の先行ブロック数、ブロック内の先行同桁数を使い、書込衝突のない並列一桁整列を設計せよ。長さのprefix sumは仕事、深さで行えると仮定し、一段と全段の仕事量・深さ・空間を評価せよ。
参考解答・採点の観点 — 問題3
(1) 符号ビットの反転
負数のビット表現は、非負数は。符号ビット反転で負数を前半へ、非負数を後半へ移し、各範囲内の大小は保存される。例えば8ビットの-1はFF、0は00で、未変換の非負順では0を-1より前に置いてしまう。反転後は-1が7F、0が80。
(2) 安定な一桁計数整列
各桁値のcountを0にして入力を数える。を累積和で求め、のコピーを作る。入力を左から右へ走査し、とする。同桁は入力順に連続位置を占める。時間、出力を除く領域、出力配列。
(3) 下位桁からの不変条件
段後は下位桁の値の非減少順で、その値が等しいレコードの元順を保つ。次の安定整列は新しい桁を主キーにし、同桁内の既存の下位順を保つので帰納成立。例えば入力の下位桁処理後はだが、上位桁1の同値群を不安定に逆転するとへ戻ってしまう。全時間。
(4) 符号付き整数の具体例
変換後は順に。下位桁の安定整列後は()。上位桁後は()。同キーはすべての桁で同値なので、各安定段により最初の識別子順を保つ。
(5) 衝突のない並列化
ブロックの桁個数を、、、とする。ブロック内を左から走査し、同桁の既出数を用いてへ書く。順位は「小さい桁全体同桁の先行ブロックブロック内部」の順で一意、書込衝突がなく安定。pR個のヒストグラムセルの初期化は並列に行い、各ブロックの計数と出力は順次走査する。一段の仕事、深さ、補助領域。ここでは入力走査のブロック数であり、prefix sum等には問題文で許した追加の処理器を利用する。全段の仕事・深さは各一段の倍、空間は再利用でき同じ。