第1回 基本手法を「故障」に適用する
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
頂点の故障と分断の規模¶
単純連結無向グラフ の頂点 を除いたグラフの連結成分数を 、最大の連結成分の頂点数を とする。 は隣接リストで与えられ、 である。
DFS の発見番号を 、親を 、 を根とする部分木の頂点数を とする。 は の部分木から木辺を下り、非木辺を高々1本用いて到達できる頂点の発見番号の最小値である。
(1) DFS木と各頂点の値(6点)¶
頂点1を根とし、隣接頂点を番号順に調べるDFS木を示せ。すべての 、、 を求めよ。
(2) 分離条件の証明(7点)¶
非木辺の両端がDFS木上で祖先と子孫の関係になることを証明せよ。これを用いて、根でない の子 について、 のとき、 の部分木が の他の頂点から分離されることと、その逆を証明せよ。
(3) 連結成分数と最大成分の式(8点)¶
根の場合と根でない場合を分けて、 と を と から求める式を導け。特に、分離されない複数の子の部分木が、親側の成分にまとめて含まれる理由を説明せよ。
(4) 線形時間アルゴリズム(8点)¶
すべての の を 時間で求める擬似コードを書け。(1)のグラフについて、各 の値を求め、 が最大となる頂点をすべて挙げよ。
(5) 次数による評価の反例(6点)¶
「次数が最大の頂点を除けば、連結成分数が最大になる」という主張を反例で否定せよ。反例における次数と を示し、関節点の判定と被害規模の評価の違いを説明せよ。
参考解答・採点の観点 — 問題1
(1) DFS木と各頂点の値
発見順は 。木辺は 。
| 頂点 | |||
|---|---|---|---|
| 1 | 1 | 1 | 8 |
| 2 | 2 | 1 | 7 |
| 3 | 3 | 1 | 6 |
| 4 | 4 | 4 | 5 |
| 5 | 5 | 4 | 2 |
| 6 | 6 | 4 | 1 |
| 7 | 7 | 7 | 2 |
| 8 | 8 | 8 | 1 |
親への木辺を非木辺として扱わない。
(2) 分離条件の証明
探索中の頂点から未訪問頂点へ進むと、その頂点は当該部分木内で探索される。別の完了済み部分木へ辺があれば、その部分木の探索時に逆側も探索されていたはずなので矛盾する。
は の真の祖先への出口がないことを表す。 なら非木辺と木上の経路で親側へ到達できる。
(3) 連結成分数と最大成分の式
非根では
とおくと
親側の成分の大きさは 。分離されない子の部分木は、 の真の祖先への出口を持つため、すべて親側の成分に含まれる。
根では子部分木ごとに成分ができ、
(4) 線形時間アルゴリズム
DFSの帰りがけに を加算して を更新する。全頂点について子を一度ずつ調べれば式を評価できる。補助空間は 。
| 頂点 | ||
|---|---|---|
| 1 | 1 | 7 |
| 2 | 1 | 7 |
| 3 | 2 | 5 |
| 4 | 3 | 3 |
| 5 | 1 | 7 |
| 6 | 1 | 7 |
| 7 | 2 | 6 |
| 8 | 1 | 7 |
が最大となるのは 頂点4のみ。
(5) 次数による評価の反例
反例: の頂点 に辺 を付け、 に葉 を付ける。
| 頂点 | 次数 | 除去後の連結成分数 |
|---|---|---|
| 5 | ||
| 4 |
が唯一の最高次数頂点。しかし最大の分断を生む頂点は である。次数は隣接辺数、分断規模は別の経路で接続できるかに依存する。
問題2 · 動的計画法(35点)¶
不一致の個数を指定した大域的アラインメント¶
文字列 と の全体をアラインメントする。文字同士の列の得点は一致なら 3、不一致なら -2、長さ の同じ側の連続ギャップ区間の得点は とする。。
両側がギャップの列は禁止するが、ギャップの側を次の列で切り替えることは許す。不一致の列をちょうど 個含むアラインメントの最大得点を求めたい。 は非負整数とし、条件を満たす解が存在しない場合は実現不可能と答える。
(1) 状態と初期値(6点)¶
末尾列の種類と不一致数を記憶する動的計画法の状態を定義せよ。文字同士・X側ギャップ・Y側ギャップの三つの末尾状態が必要となる理由を説明し、実現不可能な状態と空列の初期値を示せ。
(2) 漸化式(7点)¶
三つの状態の漸化式を導け。長さ1のギャップの費用は である。異なる側のギャップへ切り替える場合、既存区間の延長と区別せよ。
(3) 正しさと計算量(8点)¶
漸化式の正しさを、最終列を取り除く操作と最適部分構造を用いて証明せよ。全表を計算する順序、時間計算量、得点だけを求める場合の補助空間計算量を示せ。
(4) 具体例(8点)¶
、、、、 とする。最適得点とアラインメントを求めよ。次に の場合を求めよ。
「不一致を禁止すれば同じ位置の異なる文字を一つのギャップで置き換えればよい」という説明の誤りを指摘せよ。
(5) 復元と省メモリ化の反例(6点)¶
最適解を一つ復元する方法を示せ。また、「各 で、 の異なる状態のうち得点最大の一つだけを残せばよい」という省メモリ化を反例で否定せよ。
参考解答・採点の観点 — 問題2
(1) 状態と初期値
| 状態 | 末尾の列 | 意味 |
|---|---|---|
| 文字対で終わる最大得点 | ||
| Y側ギャップで終わる最大得点 | ||
| X側ギャップで終わる最大得点 |
いずれも の先頭 文字と の先頭 文字を使い、不一致がちょうど 個ある状態である。
を空の特別な開始状態とし、他は 。 または のギャップ状態も漸化式で構成する。 は 。末尾が同じ側のギャップか否かで開始費用が変わる。
(2) 漸化式
、(一致)または -2(不一致)とする。
は 、 は 、 は の範囲で計算する。空の 状態からも開始できる。終値は 。これが なら実現不可能である。
(3) 正しさと計算量
末尾の列を除くと、 は両添字、 は 、 は が減る。ギャップの継続時だけ開設費用が不要であり、全候補は必要十分。
を外側、 を内側、 を最内側として計算できる。時間 、行を二つ保持すれば補助空間 。境界も含め厳密には時間 。
(4) 具体例
| 不一致数 | 最適アラインメント(上段 / 下段) | 得点 |
|---|---|---|
AB / AC | ||
AB- / A-C、または A-B / AC- |
一つのギャップ列は片側の文字しか消費しないため、BとCの双方を消費するには両側に各一つのギャップ列が必要。
(5) 復元と省メモリ化の反例
各状態に選んだ前状態を保存し、 から逆にたどる。保存量 、復元 。
反例:、、、、。不一致1個の文字対は得点 -2 で、同じ終端にある不一致0個の合法解 A- / -B の得点 -6 より高い。
個数の異なる最大得点だけを残すと、目標 の最適解を失う。個数は将来の許容性を変えるので得点のみで比較してはならない。
問題3 · 整列アルゴリズム(30点)¶
安定性を証明する多路併合¶
本の空でない配列 が、それぞれキーの昇順に整列されている。全要素数を とする。元の入力順序は配列を から の順に連結した順序である。
キーが等しい要素について元の順序を保つ安定な併合を、最小ヒープで実現する。各配列は添字でアクセスし、要素そのものは削除せず次の未出力位置だけを更新する。
(1) 比較規則と安定性(5点)¶
キー、配列番号、配列内位置を持つヒープ要素の比較規則を定義せよ。キーだけで比較する場合に安定性が失われる例を示せ。
(2) 根の更新と削除(5点)¶
根の更新と、入力配列が空になったときの根の削除の擬似コードを書け。削除時には末尾のヒープ要素を根へ移す。交換回数の上界を示せ。
(3) 線形時間のヒープ構築(7点)¶
最初の 要素をヒープにする線形時間の処理を示し、高さごとの頂点数を用いて を証明せよ。挿入を 回繰り返す方法の上界との違いを説明せよ。
(4) 併合全体とループ不変条件(7点)¶
併合全体の擬似コードとループ不変条件を示せ。
を併合した順序を示し、全時間・補助空間計算量を求めよ。添字の文字は要素の識別子である。
(5) 比較回数の下界(6点)¶
各配列の長さが で、全キーが相異なる場合を考える。可能な併合順序の数から比較回数の下界を導き、ヒープ併合の最適性を論じよ。 が変数であることを明記し、 を用いよ。
参考解答・採点の観点 — 問題3
(1) 比較規則と安定性
の辞書式順序。同じキーなら小さい配列番号を先に、同配列なら小さい位置を先に出す。
例えば ではヒープの同値要素の処理次第で が先に出てしまう。
(2) 根の更新と削除
新根を二つの子の小さい方と比較し、子が小さければ交換して下る。削除時は末尾を根へ移し、ヒープの要素数 を1減らして同じ処理。 なら終了。
高さは なので 回以内。
(3) 線形時間のヒープ構築
の順に siftDown。高さ の頂点数は であるため、費用の和は
逐次挿入は各回 なので という上界になり、線形構築を使う方が初期化の保証がよい。
(4) 併合全体とループ不変条件
不変条件:各未完了配列の先頭未出力要素がちょうど一つヒープ内にある。根が残り全体の最小となる。
根を出して所属配列の次要素で置換するか削除する。出力は
時間 、補助空間 。
(5) 比較回数の下界
候補数は
二分比較決定木の高さはその 以上。
が2のべき乗なら鎖集合を半分ずつ再帰分割する。各節点で総長 の二群を並べる二項係数は
であり、各層の 候補数の和は 以上。 層で 。
一般の では最大の2のべき乗 本だけを自由に併合し、残りを末尾に固定する。 より同じ下界の定数倍が得られる。
なので初期化も含めた 時間は下界と一致する。