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.

第1回 基本手法を「故障」に適用する

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論頂点の故障と分断の規模35点
問題2動的計画法不一致の個数を指定した大域的アラインメント35点
問題3整列アルゴリズム安定性を証明する多路併合30点

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

頂点の故障と分断の規模

単純連結無向グラフ G=(V,E)G=(V,E) の頂点 vv を除いたグラフの連結成分数を c(v)c(v)、最大の連結成分の頂点数を b(v)b(v) とする。GG は隣接リストで与えられ、∣V∣≥2|V|\ge 2 である。

DFS の発見番号を d[v]d[v]、親を parent⁡[v]\operatorname{parent}[v]、vv を根とする部分木の頂点数を size⁡[v]\operatorname{size}[v] とする。low⁡[v]\operatorname{low}[v] は vv の部分木から木辺を下り、非木辺を高々1本用いて到達できる頂点の発見番号の最小値である。

(1) DFS木と各頂点の値(6点)

V={1,…,8},E={{1,2},{2,3},{3,1},{3,4},{4,5},{5,6},{6,4},{4,7},{7,8}}.\begin{aligned} V &= \{1,\ldots,8\},\\ E &= \{\{1,2\},\{2,3\},\{3,1\},\{3,4\},\{4,5\},\\ &\qquad \{5,6\},\{6,4\},\{4,7\},\{7,8\}\}. \end{aligned}

頂点1を根とし、隣接頂点を番号順に調べるDFS木を示せ。すべての dd、low⁡\operatorname{low}、size⁡\operatorname{size} を求めよ。

(2) 分離条件の証明(7点)

非木辺の両端がDFS木上で祖先と子孫の関係になることを証明せよ。これを用いて、根でない vv の子 uu について、low⁡[u]≥d[v]\operatorname{low}[u]\ge d[v] のとき、uu の部分木が G−vG-v の他の頂点から分離されることと、その逆を証明せよ。

(3) 連結成分数と最大成分の式(8点)

根の場合と根でない場合を分けて、c(v)c(v) と b(v)b(v) を size⁡\operatorname{size} と low⁡\operatorname{low} から求める式を導け。特に、分離されない複数の子の部分木が、親側の成分にまとめて含まれる理由を説明せよ。

(4) 線形時間アルゴリズム(8点)

すべての vv の c(v),b(v)c(v),b(v) を O(∣V∣+∣E∣)O(|V|+|E|) 時間で求める擬似コードを書け。(1)のグラフについて、各 vv の値を求め、c(v)c(v) が最大となる頂点をすべて挙げよ。

(5) 次数による評価の反例(6点)

「次数が最大の頂点を除けば、連結成分数が最大になる」という主張を反例で否定せよ。反例における次数と c(v)c(v) を示し、関節点の判定と被害規模の評価の違いを説明せよ。

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

不一致の個数を指定した大域的アラインメント

文字列 X=x1⋯xmX=x_1\cdots x_m と Y=y1⋯ynY=y_1\cdots y_n の全体をアラインメントする。文字同士の列の得点は一致なら 3、不一致なら -2、長さ k≥1k\ge 1 の同じ側の連続ギャップ区間の得点は −(go+kge)-(g_o+k g_e) とする。go,ge>0g_o,g_e>0。

両側がギャップの列は禁止するが、ギャップの側を次の列で切り替えることは許す。不一致の列をちょうど qq 個含むアラインメントの最大得点を求めたい。qq は非負整数とし、条件を満たす解が存在しない場合は実現不可能と答える。

(1) 状態と初期値(6点)

末尾列の種類と不一致数を記憶する動的計画法の状態を定義せよ。文字同士・X側ギャップ・Y側ギャップの三つの末尾状態が必要となる理由を説明し、実現不可能な状態と空列の初期値を示せ。

(2) 漸化式(7点)

三つの状態の漸化式を導け。長さ1のギャップの費用は go+geg_o+g_e である。異なる側のギャップへ切り替える場合、既存区間の延長と区別せよ。

(3) 正しさと計算量(8点)

漸化式の正しさを、最終列を取り除く操作と最適部分構造を用いて証明せよ。全表を計算する順序、時間計算量、得点だけを求める場合の補助空間計算量を示せ。

(4) 具体例(8点)

X=ABX=\mathrm{AB}、Y=ACY=\mathrm{AC}、q=1q=1、go=2g_o=2、ge=1g_e=1 とする。最適得点とアラインメントを求めよ。次に q=0q=0 の場合を求めよ。

「不一致を禁止すれば同じ位置の異なる文字を一つのギャップで置き換えればよい」という説明の誤りを指摘せよ。

(5) 復元と省メモリ化の反例(6点)

最適解を一つ復元する方法を示せ。また、「各 (i,j)(i,j) で、qq の異なる状態のうち得点最大の一つだけを残せばよい」という省メモリ化を反例で否定せよ。

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

安定性を証明する多路併合

k≥2k\ge 2 本の空でない配列 A1,…,AkA_1,\ldots,A_k が、それぞれキーの昇順に整列されている。全要素数を NN とする。元の入力順序は配列を A1A_1 から AkA_k の順に連結した順序である。

キーが等しい要素について元の順序を保つ安定な併合を、最小ヒープで実現する。各配列は添字でアクセスし、要素そのものは削除せず次の未出力位置だけを更新する。

(1) 比較規則と安定性(5点)

キー、配列番号、配列内位置を持つヒープ要素の比較規則を定義せよ。キーだけで比較する場合に安定性が失われる例を示せ。

(2) 根の更新と削除(5点)

根の更新と、入力配列が空になったときの根の削除の擬似コードを書け。削除時には末尾のヒープ要素を根へ移す。交換回数の上界を示せ。

(3) 線形時間のヒープ構築(7点)

最初の kk 要素をヒープにする線形時間の処理を示し、高さごとの頂点数を用いて O(k)O(k) を証明せよ。挿入を kk 回繰り返す方法の上界との違いを説明せよ。

(4) 併合全体とループ不変条件(7点)

併合全体の擬似コードとループ不変条件を示せ。

A1=[1a,4a],A2=[1b,2b,4b],A3=[1c,3c]A_1=[1_a,4_a],\qquad A_2=[1_b,2_b,4_b],\qquad A_3=[1_c,3_c]

を併合した順序を示し、全時間・補助空間計算量を求めよ。添字の文字は要素の識別子である。

(5) 比較回数の下界(6点)

各配列の長さが rr で、全キーが相異なる場合を考える。可能な併合順序の数から比較回数の下界を導き、ヒープ併合の最適性を論じよ。kk が変数であることを明記し、N=krN=kr を用いよ。