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.

第4回 循環をどう有限化するか

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論依存関係と閉路の証明書35点
問題2動的計画法一周までの環状局所アラインメント35点
問題3整列アルゴリズムヒープ整列と優先度変更の契約30点

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

依存関係と閉路の証明書

有向グラフG=(V,E)G=(V,E)は作業の依存関係を表し、辺u→vu\to vはuuの完了後にvvを行う必要があることを意味する。自己辺はなく、辺の重複もない。全作業を実行できる順序、または依存関係に有向閉路があることを示す具体的な閉路のいずれかを出力したい。

(1) DFSによる閉路の復元(6点)

DFSの頂点状態を未訪問・探索中・完了の三つに分ける。探索中の頂点への辺から有向閉路を復元する方法を示せ。完了頂点への辺を閉路と判定してはいけない例も示せ。

(2) 完了時刻と実行順序(7点)

DFSで探索中頂点への辺が一つも見つからなかった場合、完了時刻の降順が依存関係を満たすことを証明せよ。連結でない場合も含め、全体の擬似コードと計算量を示せ。

(3) 入次数による除去と閉路(8点)

入次数0の頂点を順に除く別の方法を設計せよ。全頂点を除けなかったとき、残った頂点をすべて一つの閉路に含まれると断定できないことを例で示せ。残りから閉路を一つ復元する方法を示せ。

(4) 具体例(8点)

V={1,…,6},E={1→3,2→3,3→4,2→5,5→6}.V=\{1,\ldots,6\},\qquad E=\{1\to3,2\to3,3\to4,2\to5,5\to6\}.

について、番号最小の入次数0頂点を選ぶ順序を求めよ。辺 6→26\to2 を加えた場合、閉路を一つ示し、除去法で残る頂点も求めよ。

(5) 順序の検証と閉路の証明書(6点)

与えられた頂点列が正しい実行順序かを線形時間で検証する方法を示せ。また、一つの閉路を提示するだけで「全作業を実行する順序は存在しない」と証明できる理由を説明せよ。

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

一周までの環状局所アラインメント

直線文字列LLの長さをmm、環状文字列CCの長さをn≥2n\ge 2とする。CCの文字を順方向に高々nn個消費する局所アラインメントを求める。すなわち、環状配列を一周より長く使用してはならない。文字対得点SSは任意の実数で、ギャップ一列の得点は−g-g、g>0g>0。空のアラインメントも許す。CC側で消費する文字数には、LL側のギャップに対応するCCの文字も含める。

(1) 開始位置ごとの局所DP(6点)

CCを各開始位置ssで切って長さnnの直線文字列C(s)C^{(s)}を作る。各ssについて通常の局所アラインメントDPを行う方法の状態、初期値、漸化式を示し、全時間を評価せよ。

(2) 一周制約との同値性(7点)

上の方法で得られる最大値が問題の最適値と等しいことを証明せよ。アラインメントがC(s)C^{(s)}の先頭から始まることを強制する必要はない理由も説明せよ。

(3) 二重化だけでは不十分な反例(8点)

D=CD=Cを二回連結した長さ 2n2nの文字列とする。「DDとLLに通常の局所アラインメントを一度行えば十分」という方法を反例で否定せよ。反例ではn≥2n\ge 2を守り、最適得点の違いを計算せよ。

(4) 具体例(8点)

L=ABAL=\mathrm{ABA}、C=ABC=\mathrm{AB}、SS一致=3、不一致=−4、g=2g=2とする。高々一周という制約下の最適得点とアラインメントを求めよ。制約を外す場合の答えも求めよ。

(5) 最適解の復元と計算量(6点)

最適解の開始位置とアラインメントを復元する方法を示せ。得点のみ計算する場合と復元する場合を分け、時間と空間を評価せよ。開始位置ssを順に調べる最初の方法を用いてよい。

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

ヒープ整列と優先度変更の契約

最大ヒープを配列H[1…h]H[1\ldots h]に格納する。H[i]≥H[2i], H[i]≥H[2i+1]H[i]\ge H[2i],\ H[i]\ge H[2i+1]を、子が存在する範囲で満たすものとする。ヒープ整列を実装するとともに、任意位置のキーが外部から変更された場合の更新操作を設計したい。キー変更の前にはヒープ条件が成立している。

(1) ヒープ整列と不変条件(5点)

根と末尾を交換して有効サイズを1減らす操作を用いたヒープ整列の擬似コードを書け。未整列区間と確定した末尾区間について不変条件を示せ。

(2) 構築と整列の計算量(5点)

最初の最大ヒープ構築をO(n)O(n)で行う方法と証明を示せ。整列全体の最悪時間と補助空間を示し、入力が昇順でもこの実装がΘ(n)\Theta(n)時間になるとは限らない理由を説明せよ。

(3) キー変更後の修復方向(7点)

位置ppのキーをaaからbbへ変更した。b>ab>aの場合とb<ab<aの場合に分け、ヒープ条件をO(log⁡n)O(\log n)時間で回復する方法と、その方向だけ調べれば十分な理由を証明せよ。

(4) 具体例(7点)

H=[9,7,8,3,6,5,4]H=[9,7,8,3,6,5,4]で位置5のキーを10にした後のヒープを一つ求めよ。元のHHで位置2のキーを1にした後も求めよ。二つは独立した操作とする。

(5) 安定性と外部参照(6点)

ヒープ整列が安定でない具体例を示せ。元位置をキーに付加した安定化の時間・空間の代償を説明せよ。また、位置ppだけを記録していた外部参照が交換後に別要素を指す問題への対策を設計せよ。