第17回 削除の影響・禁止パターン・入力構造への適応
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 210分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
頂点需要を用いた分離被害と感度¶
頂点数 の連結単純無向グラフ に正の整数の頂点需要 が付く。総需要を とする。頂点 の削除後の各連結成分の需要和を とし、 と定める。これは分断される頂点対 の需要積 の総和であり、頂点数だけでは被害を測れない。DFS の発見番号 、親の木辺を除く後退辺から計算する low、部分木需要 を用いる。全頂点の被害を一括計算し、需要の変化に対する感度も調べよ。
(1) 分離条件の証明(5点)¶
根でない頂点 の子 について、 なら の部分木が の一つの成分になることを証明せよ。 の子の部分木が、 の親を含む側と連結していることも証明せよ。
(2) 成分需要と根の扱い(6点)¶
根でない を削除したときの成分需要を を用いて表せ。「残りの成分」の需要が正である理由を述べよ。DFS 根の場合の式を別に示し、同じ成分サイズでも需要によって被害が違う例を与えよ。
(3) 全頂点の被害計算(6点)¶
を導け。全頂点について と成分需要一覧を 時間で計算する擬似コードを書け。一覧の総出力長と、必要な整数の桁数にも触れよ。
(4) 関節点と橋の不等号(6点)¶
を に置き換える誤った方法が見落とす関節点を、5頂点以上の具体的なグラフで示せ。同時に、橋の判定に厳密な不等号が必要である理由を説明せよ。
(5) 需要付きグラフの具体例(7点)¶
根1、番号順の DFS とし、辺は 、頂点需要は順に である。各 と、関節点の削除後の成分需要・ を求め、被害最大の頂点を答えよ。
(6) 連結問い合わせと感度(5点)¶
は相異なる頂点とする。多数の の連結判定を で答える前処理を設計せよ。 を保つ単一変更の の感度も求め、 と を区別せよ。変更自体は実行しない。
参考解答・採点の観点 — 問題1
(1) 分離条件の証明
無向 DFS の非木辺は祖先と子孫だけを結ぶ。 なら、 の部分木から の真の祖先への辺はなく、別の子の部分木への辺もない。 を削除した後、部分木内は木辺で連結したまま、外部には出られない。 なら、部分木のある頂点から の真の祖先への後退辺がある。その後は を通らない祖先の木辺を使って親の側へ到達できる。
(2) 成分需要と根の扱い
とすると成分需要は各 の と、。非根なら残り側に正需要の親があるため 。分離しない子の部分木はその側に属する。根ではすべての子の だけで、子1個なら 。たとえば二成分のサイズが同じ でも、需要和 なら被害4、 なら20。サイズのみの重要度と需要を考慮した重要度は別である。
(3) 全頂点の被害計算
と二乗の展開から式を得る。
DFS で d,low,parent,t を計算(t[v] は μ(v) から開始)
for v in V:
if v==root: masses=[t[c] for c in children(v)]
else:
masses=[t[c] for c in children(v) if low[c]>=d[v]]
masses.append(M-μ(v)-sum(masses))
I[v]=((M-μ(v))**2-sum(a*a for a in masses))/2子の総数 と、非根の残り成分の追加 回以下から、一覧の総長 。時間 、補助空間 (入力・出力を除く)。需要和とその積が入る ビットの定数倍の語による算術を と仮定した評価である。ビット演算を数えるなら、その算術費用を別に掛ける。
(4) 関節点と橋の不等号
三角形 と三角形 を頂点3で共有するグラフを、根1から番号順で DFS する。3 の子4の low は と等しい。3 を除くと と に分かれるが、厳密な > だけでは3を見落とす。一方、 なら子孫から3へ戻る辺があり、木辺 自体を除いてもその迂回で連結できる。したがって橋には が必要である。
(5) 需要付きグラフの具体例
| 頂点 | low | ||
|---|---|---|---|
| 1 | 1 | 1 | 13 |
| 2 | 2 | 1 | 12 |
| 3 | 3 | 1 | 10 |
| 4 | 4 | 4 | 9 |
| 5 | 5 | 4 | 3 |
| 6 | 6 | 4 | 2 |
| 7 | 7 | 7 | 3 |
| 8 | 8 | 8 | 2 |
| 関節点3の成分需要は 、。4は 、。7は 、。その他は一成分で 。最大は4。需要が均一のときの結果と混同せず、各成分の需要を先に合計する。 |
(6) 連結問い合わせと感度
DFS の入・出時刻と祖先ジャンプ表を準備する。 が の部分木外なら非根 の残り成分。内部なら を まで上げて直下の子 を得る。根 ならラベル 、非根なら の場合だけラベル 、それ以外は残り成分。 のラベルが等しいことが連結と同値。各ラベルの需要も保存する。 のとき、 が属する成分の需要を とすれば、 の増分 により は だけ変わる。同じ成分内の対は分断されず、他成分の需要和だけが係数となる。 ではその頂点を削除するため変化0。前処理 時間・ 補助空間、問い合わせと単一変更の感度は 。これは多数の変更後の表を維持する動的アルゴリズムを主張するものではない。
問題2 · 動的計画法(35点)¶
禁止パターンを含まない共通部分列¶
二つの文字列 、 は文字 からなる。両方の共通部分列であり、その結果の文字列の連続部分文字列として ABA を含まないもののうち、最長のものを求める。入力に ABA が含まれるかどうかではなく、選んだ文字を連結した結果に対する制約である。結果の接尾辞が ABA の真の接頭辞のどれと一致するかを状態にし、 をそれぞれ空、、AB に対応させる。ABA が完成すると禁止状態へ入る。空部分列は許され、実現不能状態は とする。
(1) 禁止パターンの遷移表(5点)¶
各状態 と新しい文字 に対する遷移表を作れ。たとえば で を読むとき、状態を0に戻すのが誤りである理由を説明せよ。
(2) 後処理が最適でない反例(5点)¶
通常の最長共通部分列を一つ求め、その中の最も左の ABA の中央の を消す操作を繰り返す方法は最適とは限らない。 でこの方法と最適解を比較し、制約を後処理にできない理由を述べよ。
(3) 状態を追加したLCS(8点)¶
を の長さ の接頭辞と の長さ の接頭辞から得られ、状態 で終わる合法な共通部分列の最大長と定義する。境界値と全遷移を示し、状態 が最適部分構造を回復させることを証明せよ。
(4) 最適部分列の具体例(5点)¶
、 について最適長と最適部分列を一つ求め、双方で選ぶ位置を示せ。最適長を証明するため、最後のセルの3状態の値、または同等の上界を示せ。
(5) 一般の禁止語への拡張(7点)¶
禁止語を任意の長さ の1語 に置き換える。状態を「結果の接尾辞と一致する の最長の真の接頭辞の長さ」とするオートマトンを定義し、遷移の構築方法と DP の時間・空間を評価せよ。 の完成を避ける遷移のみを採用すること。
(6) 復元と相異なる部分列の個数(5点)¶
最適部分列を一つ復元するための情報を説明せよ。DP の経路数を数えることが、相異なる最適部分列の個数を数えることと一致しない具体例を与え、この二つを区別せよ。
参考解答・採点の観点 — 問題2
(1) 禁止パターンの遷移表
| 0 | 1 | 0 |
| 1 | 1 | 2 |
| 2 | 禁止 | 0 |
| 状態1で を加えると末尾は AA となるが、最後の が接頭辞 と一致するので状態1のままである。AB の後に を加えた ABB の末尾には も AB も残らないので状態0。 |
(2) 後処理が最適でない反例
ABABA の最左の ABA から中央 を消すと AABA。再び中央 を消すと AAA で長さ3。一方、元の位置を選ぶ ABBA は ABA を含まず長さ4である。長さ5は元の語そのもので禁止なので4が最適。捨てる場所の選択は将来の文字との組合せに影響し、普通の LCS の得点だけではその情報が失われる。
(3) 状態を追加したLCS
、 の境界は 。各セルでは、 を使わない 、 を使わない をまず候補にする。 のとき、各生存状態 について が禁止でなければ を に緩和する。最後の答えは 。末尾を使わないか、同じ文字を両列から選ぶかに分ければ全共通部分列を覆う。将来に対する合法性は既存の結果全体ではなく だけから決まり、同じ ならより短い結果を保持する利点はない。これが状態を追加する理由である。
(4) 最適部分列の具体例
最適長は4。ABBA は の位置 と の位置を選べば得られる。ほかに AAAA、AAAB も最適である。DP の最後の状態別値は 、、。長さ5以上がないことはこの値により保証される。数字を再確認する場合は、全接頭辞の漸化式を評価するか、双方の全長5部分列を列挙して禁止語を検査すればよい。
(5) 一般の禁止語への拡張
状態集合は 。現在の接尾辞代表 に文字 を追加し、その末尾と一致する の最長接頭辞の長さを求める。長さ なら禁止遷移、それ以外ならその長さを次状態とする。すべての候補長を直接照合する素朴な構築でも 時間で可能であり、接頭辞の失敗リンクを使えば にできる。DP は各セル・各 から遷移先が1個なので 時間であり、 を掛ける必要はない。得点のみなら2行で 、全復元表なら 空間。 でも状態0と禁止遷移として同じ定義が使える。
(6) 復元と相異なる部分列の個数
各 に、上・左・文字採用のいずれの候補と、採用時の前状態 を記録する。最大の最終状態から戻り、文字採用時に文字を出力し最後に逆順にする。復元は 。、 では文字列 は1種類だが、 の第1文字と第2文字のどちらを使うかで経路が異なる。さらに不要なスキップの順序でも経路が増える。したがって経路の和を取っただけでは相異なる結果語の個数にならない。
問題3 · 整列アルゴリズム(30点)¶
区間の長さに適応する安定整列¶
元の配列中の 本の連続区間は、それぞれ整列済みで長さ が知られている。、、 とする。隣接区間の安定併合の費用は要素数の和である。 の一律の評価から進み、長さが偏っている場合にも有利な の手順を設計したい。二進語 を、[) の長さ の二進区間に対応させる。互いに交わらない二進区間に対応する語は、相互に接頭語にならないという性質を利用してよい。
(1) 下降区間と安定性(4点)¶
任意の配列から非減少区間と厳密な減少区間を取り出し、減少区間を反転して整列済み区間にする方法を説明せよ。減少区間に等号を認めて反転すると安定性が失われる具体例を示せ。
(2) 均等葉数の併合木(4点)¶
葉数を均等に二分する併合木の費用が となる理由を述べよ。長さ について、その上界が を用いた評価より粗くなり得ることを示せ。
(3) 中点を使う接頭語符号(7点)¶
とし、区間 [) の中点を含む長さ の二進区間を選ぶ。ただし とする。この二進区間が元の区間内に収まることと、得られる語が葉順を保つ接頭語符号となることを証明せよ。
(4) 葉順を保つ木の構築(7点)¶
(3)の語から二分木を作り、子が1個だけの頂点を縮約して合法な隣接併合木を得よ。総費用が 未満となることを示せ。木の構築も含めて 時間に収まる理由を説明せよ。
(5) 情報量の下界(4点)¶
キーがすべて異なり、各区間内の順序だけが既知である比較モデルを考える。可能な全併合順序の数を求め、比較回数の下界を示せ。 と を使い、下界と NH の関係を評価せよ。
(6) 長さに適応する具体例(4点)¶
すべての要素を書き出す時間も費用に含める。(5)の下界から最悪時間 を導き、(4)までのアルゴリズムがこの入力の約束に対してオーダー最適であることを説明せよ。
参考解答・採点の観点 — 問題3
(1) 下降区間と安定性
左から走査し、非減少が続く範囲を区間にする。最初の下降を選ぶ場合は、その後も厳密な下降だけを取り出して反転する。キーが同じ要素は厳密な下降区間に同居しないので順序を壊さず、後の併合でも左を優先すれば安定である。非増加区間を反転すると、入力 が となり、同キーの が逆転する。
(2) 均等葉数の併合木
各葉の深さが高々なので、全要素がその回数以下の併合に参加する。長さが の場合、。たとえば ≈√ なら √) である一方、 は 。前者に線形の読み書き費用を加えると の目標となる。
(3) 中点を使う接頭語符号
幅 。中点から元の区間の両端までの距離は で、選んだ二進区間のどちらの端も中点から幅以内にあるため区間内に収まる。境界で中点が二進区間の左端に来る場合も半開区間として右側を選べばよい。元の区間は互いに交わらず順序も の順なので、選んだ二進区間も交わらず同じ順。二進区間が包含関係にあることは語の接頭語関係に対応するため、語は相互に接頭語にならない。
(4) 葉順を保つ木の構築
語の共通接頭辞を共有する圧縮トライを直接作る。葉順の隣接語の共通接頭辞長を調べ、その深さで分岐を挿入するスタック構築なら、1子頂点を保存する必要がない。葉順は変わらず、各内部頂点の左右の葉集合は連続区間なので隣接併合で実現できる。縮約後の深さ 、ゆえに 。語長は 、構築は 時間。 の凹性より、固定した で NH が最小となる長さ分布は一つを 、他を1とする分布なので 。よって 。実際の併合もその費用に比例し、補助空間は の作業配列と の圧縮トライ・スタックを使える。
(5) 情報量の下界
区間内の順序を固定したまま 個の順位を 区間へ割り当てる数は 。決定木の葉は少なくとも 必要なので最悪比較数。与えられた不等式により 。単に「常に NH 回の比較が必要」と言うのは誤りで、偏った区間では比較数が線形未満になる場合がある。
(6) 長さに適応する具体例
出力だけで 。 が定数範囲なら なのでこの下界で十分。 の場合、 だから 。二つを合わせると となる。これは与えられた区間長を持つすべての可能な値の並びに対する最悪下界であり、特定の1入力の比較数の下界ではない。上で得た手順は総時間 なので、この約束に対してオーダー最適。