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.

第14回 幅と制約を状態にする

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

← 备考目录

試験時間(目安)満点問題数
200分100点全3問
問題分野テーマ配点
問題1グラフ理論幅2のグラフで求める最小カット35点
問題2動的計画法長すぎるギャップを禁止する局所アラインメント35点
問題3整列アルゴリズム整列済みの鎖が与える情報30点

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

幅2のグラフで求める最小カット

2行 nn列の階梯グラフを考える。列iiの頂点は ai,bia_{i},b_{i}、縦辺 aibia_{i}b_{i} の重みは ri>0r_{i}>0。横辺 aiai+1,bibi+1a_{i}a_{i+1},b_{i}b_{i+1} の重みはそれぞれ ui,li>0u_{i},l_{i}>0。n≥2n\ge 2、s=a1s=a_{1}、t=ant=a_{n} とする。頂点を側0と側1に分け、ssを0、ttを1へ置く。異なる側を結ぶ辺の重み和をカット値と呼ぶ。最小 s−ts-t カットを、汎用の最大流アルゴリズムを使わず、左から列を処理して求めたい。

(1) 頂点分割と分離辺集合(5点)

異なる側を結ぶ辺を削除すれば s,ts,t が分離することを示せ。逆に任意の s−ts-t 分離辺集合から、それ以下の重みを持つ頂点分割のカットが得られることを証明せよ。

(2) 列の状態と遷移(6点)

第 ii 列の側を (α,β)∈{0,1}2(\alpha ,\beta )\in \{0,1\}^{2} とし、最初の ii 列内の辺だけを数える最適値 Di(α,β)D_{i}(\alpha ,\beta ) を定義する。D1D_{1} の初期値、列間の遷移式、最終解の式を示せ。

(3) 四状態の具体例(6点)

n=3n=3、縦辺の重みが (4,1,4)(4,1,4)、上横辺が (3,5)(3,5)、下横辺が (2,3)(2,3) の場合、各列の四状態の値を表にせよ。最小カット値と削除する辺を一つの解として求めよ。

(4) 状態の十分性と復元(7点)

各列の側だけを保持すれば十分であることを、未処理部分への接続に注目して証明せよ。擬似コード、時間、最小値だけの場合の空間、カットの復元に必要な空間と時間を示せ。

(5) 一状態だけ残す貪欲法(5点)

「各列で、それまでの最小値を持つ一状態だけ残す」という貪欲法が誤ることを、(3)の数値を用いて示せ。将来の辺の費用が捨てた状態を有利にする仕組みを説明せよ。

(6) 幅wへの拡張(6点)

各列に ww 個の頂点があり、辺は同じ列内または隣接する列の間にのみ存在するグラフへ拡張せよ。各列対に高々 w2w^{2} 辺があるとして、状態数・遷移数・単純な実装の時間計算量を示せ。

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

長すぎるギャップを禁止する局所アラインメント

文字列 L,RL,R の長さを m,nm,n とし、任意の連続部分文字列間で局所アラインメントを行う。空のアラインメントはスコア0。文字対応のスコアは S(x,y)S(x,y)、同じ側に連続する長さ kk の最大ギャップ区間は −(go+kge)-(g_{o}+kg_{e})、go,ge>0g_{o},g_{e}>0。ただし各最大ギャップ区間の長さは KK 以下でなければならない。K≥1K\ge 1。両側ギャップの列は禁止し、異なる側のギャップが隣接することは許す。状態は消費済み接頭辞の長さ i,ji,j で終わるものとし、局所的な開始位置は任意とする。

(1) 末尾状態と境界(5点)

最後が文字同士の対応である状態 M(i,j)M(i,j)、LLの文字対RRのギャップである E(i,j)E(i,j)、LLのギャップ対RRの文字である F(i,j)F(i,j)、および H(i,j)=max⁡{0,M,E,F}H(i,j)=\max\{0,M,E,F\} を定義する。境界を定め、MM の漸化式と全体の答えを示せ。

(2) 長さ上限付きのギャップ(7点)

EE を新しく始める直前の状態は EE であってはならない。A=max⁡{0,M,F}A=\max\{0,M,F\}、B=max⁡{0,M,E}B=\max\{0,M,E\} を用い、最終ギャップ長 kk を明示した E,FE,F の式を導け。HH から同じ側のギャップを「開き直す」式では、長さ上限を破る理由を説明せよ。

(3) 単調両端キュー(6点)

EE の式を −go−ige+max⁡(A(t,j)+tge)-g_{o}-ig_{e} + \max(A(t,j)+tg_{e}) の形に変形し、tt の有効範囲を示せ。FF についても同様に変形し、各最大値を単調両端キューで更新する方法を説明せよ。

(4) 行列の処理と補助空間(6点)

行を上から下へ、各行を左から右へ処理する擬似コードを書け。各列の縦キューと現行の横キューを区別し、全体 O(mn)O(mn) 時間となる理由と、値だけを求める補助空間の上界を述べよ。

(5) ギャップ長の具体例(6点)

L=AXXYL=AXXY、R=AYR=AY、一致スコア4、不一致-6、go=ge=1g_{o}=g_{e}=1 とする。K=1K=1 の HH 表を作り最適値を求めよ。K=2K=2 ではより良いアラインメントが得られることを、具体的な列とスコアで示せ。

(6) 最適アラインメントの復元(5点)

最適アラインメントを復元するため、各状態に保存する情報を述べよ。ギャップの先頭位置と直前の状態を使う復元手順を示し、記憶量・復元時間を評価せよ。

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

整列済みの鎖が与える情報

相異なるキーを持つ NN 個のレコードが、k≥1k\ge 1 本の整列済み配列(鎖)に分かれている。鎖 ii の長さは ni≥1n_{i}\ge 1、∑ni=N\sum n_i=N。各鎖内の順序だけが既知で、鎖間の大小関係は未知である。全体を併合する際の比較回数とレコード移動回数を区別して考える。後半では2本の鎖に絞り、短い鎖の中央値で長い鎖を分割する方法を考える。比較回数を鎖の長さの不均等さに適応させたい。

(1) 併合順序の数(5点)

各鎖の内部順序を保つ全体の順序の数が N!/(n1!…nk!)N!/(n_{1}!\ldots n_k!) となることを証明せよ。同じ長さの鎖も、鎖番号によって区別するものとする。

(2) 情報量による下界(6点)

比較決定木による最悪比較回数の下界を、(1)の式で表せ。ni=N/kn_{i}=N/k の均等な場合に Ω(Nlog⁡k)\Omega (N \log k) となることを述べ、k=1k=1 も別に扱え。

(3) 一本だけ短い場合(6点)

k=2k=2、長さが N−1N-1 と1のとき、下界とそれを達成する比較回数の方法を示せ。その場合にも出力を別配列へ作る移動時間は Ω(N)\Omega (N) となることを説明せよ。

(4) 短い鎖の中央値による併合(7点)

2本の鎖A,BA,Bの長さをs,Ls,Lとし1≤s≤L1\le s\le Lとする。AAの中央要素をピボットとし、現在のBB区間で順位を二分探索して左右を再帰的に併合する方法を書け。再帰中もA,BA,Bの役割は交換しない。ピボットと左右の出力区間、および空列の処理を明記せよ。

(5) 不均等な鎖への適応(6点)

(4)の比較回数が O(slog⁡(1+L/s)+s)O(s \log(1+L/s)+s) となり、情報量下界に一致することを示せ。各深さのBB区間の長さの和と対数の凹性を使え。A=[3,7,12],B=[1,4,5,8,9,10,13,15,18]A=[3,7,12],B=[1,4,5,8,9,10,13,15,18] の各AA要素の出力位置も求め、移動回数を評価せよ。