第4回 循環をどう有限化するか
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
依存関係と閉路の証明書¶
有向グラフは作業の依存関係を表し、辺はの完了後にを行う必要があることを意味する。自己辺はなく、辺の重複もない。全作業を実行できる順序、または依存関係に有向閉路があることを示す具体的な閉路のいずれかを出力したい。
(1) DFSによる閉路の復元(6点)¶
DFSの頂点状態を未訪問・探索中・完了の三つに分ける。探索中の頂点への辺から有向閉路を復元する方法を示せ。完了頂点への辺を閉路と判定してはいけない例も示せ。
(2) 完了時刻と実行順序(7点)¶
DFSで探索中頂点への辺が一つも見つからなかった場合、完了時刻の降順が依存関係を満たすことを証明せよ。連結でない場合も含め、全体の擬似コードと計算量を示せ。
(3) 入次数による除去と閉路(8点)¶
入次数0の頂点を順に除く別の方法を設計せよ。全頂点を除けなかったとき、残った頂点をすべて一つの閉路に含まれると断定できないことを例で示せ。残りから閉路を一つ復元する方法を示せ。
(4) 具体例(8点)¶
について、番号最小の入次数0頂点を選ぶ順序を求めよ。辺 を加えた場合、閉路を一つ示し、除去法で残る頂点も求めよ。
(5) 順序の検証と閉路の証明書(6点)¶
与えられた頂点列が正しい実行順序かを線形時間で検証する方法を示せ。また、一つの閉路を提示するだけで「全作業を実行する順序は存在しない」と証明できる理由を説明せよ。
参考解答・採点の観点 — 問題1
(1) DFSによる閉路の復元
探索中頂点は再帰スタック上にある。辺でが探索中なら、親をからへ逆にたどって得られるとが閉路。は非巡回だが2が完了後にを調べる可能性がある。
(2) 完了時刻と実行順序
辺でが未訪問ならはより先に完了し、が完了済みなら同様。探索中は除外されている。したがって。全未訪問頂点からDFSを開始して、補助。
(3) 入次数による除去と閉路
入次数0をキューへ入れ、除去するたびに後続の入次数を減らす。閉路からが伸びる例では4も残るが閉路上でない。残存グラフの各頂点は残存入辺を持つので、入辺の前任をたどれば頂点が反復し、逆向きに並べ直して閉路が得られる。
(4) 具体例
順序1,2,3,4,5,6。追加後はが閉路。1だけを除き、残りは2,3,4,5,6。3,4は閉路からの後続のため残る。
(5) 順序の検証と閉路の証明書
頂点列の重複・欠落を調べpositionを作り、各辺についてを確認。。閉路では順序位置が一周すべて厳密増加する必要があり矛盾する。
問題2 · 動的計画法(35点)¶
一周までの環状局所アラインメント¶
直線文字列の長さを、環状文字列の長さをとする。の文字を順方向に高々個消費する局所アラインメントを求める。すなわち、環状配列を一周より長く使用してはならない。文字対得点は任意の実数で、ギャップ一列の得点は、。空のアラインメントも許す。側で消費する文字数には、側のギャップに対応するの文字も含める。
(1) 開始位置ごとの局所DP(6点)¶
を各開始位置で切って長さの直線文字列を作る。各について通常の局所アラインメントDPを行う方法の状態、初期値、漸化式を示し、全時間を評価せよ。
(2) 一周制約との同値性(7点)¶
上の方法で得られる最大値が問題の最適値と等しいことを証明せよ。アラインメントがの先頭から始まることを強制する必要はない理由も説明せよ。
(3) 二重化だけでは不十分な反例(8点)¶
を二回連結した長さ の文字列とする。「とに通常の局所アラインメントを一度行えば十分」という方法を反例で否定せよ。反例ではを守り、最適得点の違いを計算せよ。
(4) 具体例(8点)¶
、、一致=3、不一致=−4、とする。高々一周という制約下の最適得点とアラインメントを求めよ。制約を外す場合の答えも求めよ。
(5) 最適解の復元と計算量(6点)¶
最適解の開始位置とアラインメントを復元する方法を示せ。得点のみ計算する場合と復元する場合を分け、時間と空間を評価せよ。開始位置を順に調べる最初の方法を用いてよい。
参考解答・採点の観点 — 問題2
(1) 開始位置ごとの局所DP
境界0。各は、開始位置で。
(2) 一周制約との同値性
許される環上の有限区間は、最初に消費する文字から切った長さの文字列内に収まる。逆に各長さ文字列内の部分アラインメントは高々文字しか消費しない。内部開始も他の環上区間を表すので合法。
(3) 二重化だけでは不十分な反例
,=ABAB、一致3、不一致−4、。への通常局所アラインメントは4文字一致で12。高々一周では側文字対は高々2で、ギャップは負なので最大6。二重化だけでは消費長制約が消える。
(4) 具体例
| 条件 | 最適アラインメント | 得点 |
|---|---|---|
| 高々一周 | AB / AB、または BA / BA | 6 |
| 制約なし | ABA / ABA | 9 |
のは切れ目をまたぐ。
(5) 最適解の復元と計算量
各を行二本で計算し最大得点とそのを記録。最良について全表と前状態を再計算し最大セルから0まで逆追跡。全時間、復元用、得点のみ。末尾と先頭の座標を元の環上添字に変換する。
問題3 · 整列アルゴリズム(30点)¶
ヒープ整列と優先度変更の契約¶
最大ヒープを配列に格納する。を、子が存在する範囲で満たすものとする。ヒープ整列を実装するとともに、任意位置のキーが外部から変更された場合の更新操作を設計したい。キー変更の前にはヒープ条件が成立している。
(1) ヒープ整列と不変条件(5点)¶
根と末尾を交換して有効サイズを1減らす操作を用いたヒープ整列の擬似コードを書け。未整列区間と確定した末尾区間について不変条件を示せ。
(2) 構築と整列の計算量(5点)¶
最初の最大ヒープ構築をで行う方法と証明を示せ。整列全体の最悪時間と補助空間を示し、入力が昇順でもこの実装が時間になるとは限らない理由を説明せよ。
(3) キー変更後の修復方向(7点)¶
位置のキーをからへ変更した。の場合との場合に分け、ヒープ条件を時間で回復する方法と、その方向だけ調べれば十分な理由を証明せよ。
(4) 具体例(7点)¶
で位置5のキーを10にした後のヒープを一つ求めよ。元ので位置2のキーを1にした後も求めよ。二つは独立した操作とする。
(5) 安定性と外部参照(6点)¶
ヒープ整列が安定でない具体例を示せ。元位置をキーに付加した安定化の時間・空間の代償を説明せよ。また、位置だけを記録していた外部参照が交換後に別要素を指す問題への対策を設計せよ。
参考解答・採点の観点 — 問題3
(1) ヒープ整列と不変条件
buildMaxHeap(H)
h = n
while h > 1:
swap(H[1], H[h])
h = h - 1
siftDown(1, h)有効区間は最大ヒープ、末尾は昇順確定、末尾各値は有効区間の全値以上。
(2) 構築と整列の計算量
内部節点を下からsiftDownする。高さ別の費用和は。その後回の取り出し各、最悪、反復siftDownなら補助。昇順入力でもヒープ化後の取り出し時には根を下へ移す必要が繰り返される。
(3) キー変更後の修復方向
増加なら子との大小関係は悪化しないため親方向にsiftUp。減少なら親との関係は悪化しないため子方向にsiftDown。交換後、元々正しかった他の枝の条件は保たれる。
(4) 具体例
二つは独立した操作。
| 操作 | 修復後のヒープ | 移動位置 |
|---|---|---|
| 位置5のキーを10へ増加 | ||
| 位置2のキーを1へ減少 |
(5) 安定性と外部参照
を最大ヒープとして整列するとになる例がある。(key,元位置)の全順序なら最終出力は安定で時間、元位置保存。外部参照は不変IDを用い、ID→現在位置の表を各交換時に更新する。