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.

第19回 分解と再構成・状態の接続・並列の限界

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

← 备考目录

試験時間(目安)満点問題数
210分100点全3問
問題分野テーマ配点
問題1グラフ理論小さな境界で接続するグラフの最小カット35点
問題2動的計画法編集距離の最適経路を線形空間で復元する35点
問題3整列アルゴリズム整列ネットワークの正しさと仕事量30点

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

小さな境界で接続するグラフの最小カット

無向グラフ GG の辺容量は非負整数で、異なる端点 s,ts,t が指定される。頂点を0側と1側に分け、ssを0、ttを1に置くとき、両側を渡る辺容量和を最小にしたい。袋 Bx⊆VB_{x}\subseteq V を頂点にもつ根付き木が与えられ、(i)(i)全頂点がどこかの袋に入る、(ii)(ii)各辺の両端が同じ袋に入る、(iii)(iii)同じ頂点を含む袋は連結な部分木をなす、を満たす。各袋の大きさは w+1w+1 以下、袋数は bb とする。辺は両端を含む袋のうち最も根に近い袋に1回だけ割り当てる。この分解を使い、ww が小さい場合の最小カットを設計せよ。

(1) 袋の連結性と境界(5点)

同じ頂点を含む袋の連結性から、辺を割り当てる最も根に近い袋が一意であることを示せ。また、親袋 BxB_{x} と子袋 ByB_{y} の共通部分が、子の部分木と外部の色付けを接続する境界となる理由を証明せよ。

(2) 局所費用と子状態(6点)

Dx(σ)D_{x}(\sigma ) を、袋 BxB_{x} の0/10/1割当 σ\sigma を固定したとき、その袋の部分木に割り当てた辺の最小カット容量とする。局所辺費用と子の状態を用いた漸化式を導け。s,ts,t が袋に現れる場合の禁止状態も定めよ。

(3) 共通部分への投影(7点)

各子について全状態 τ\tau を親の各状態 σ\sigma と直接比較すると 4w+14^{w+1} が現れる。共通部分への投影表 My(ρ)M_{y}(\rho ) を作り、状態の結合を O((b+m)2w+1)O((b+m)2^{w+1}) 時間に改善する方法を示せ。局所辺費用の計算も含めて評価すること。

(4) 連結条件を外す反例(6点)

辺の被覆条件だけを残し、頂点を含む袋の連結条件を外すと DP が誤る。辺 s−as-a と a−ta-t の容量が各1、根袋 {s,t}\{s,t\}、子袋 {s,a},{a,t}\{s,a\},\{a,t\} の例で、誤った値と本当の最小カットを示せ。

(5) 袋ごとの具体例(6点)

根袋 {s,a,b}\{s,a,b\}、その子 {a,b,c}\{a,b,c\}、その子 {a,c,t}\{a,c,t\} を用いる。辺と容量は sa:4,sb:2,ab:1,ac:2,bc:3,at:1,ct:5sa:4,sb:2,ab:1,ac:2,bc:3,at:1,ct:5。根状態の s=0s=0 を固定した4通りの DD の値を求め、最小カットを一つ示せ。

(6) 割当の復元と計算量(5点)

最適な0/10/1割当を復元する情報と手順を示せ。同じ頂点が複数の袋に出現しても矛盾しない理由、全体時間、表の空間を述べよ。このアルゴリズムが一般の入力の大きさに対して常に多項式とは限らない理由も説明せよ。

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

編集距離の最適経路を線形空間で復元する

文字列 X,YX,Y の長さを m,nm,n とする。1文字の削除・挿入の費用は1、異なる文字への置換は2、同じ文字の対応は0である。最小編集費用と、それを達成する操作列を求めたい。通常の DP 表のセル (i,j)(i,j) は XX の先頭 ii 文字と YY の先頭 jj 文字を変換する最小費用であり、格子上の辺は削除・挿入・対応を表す。全表を保存する O(mn)O(mn) 空間の方法から、行を順方向・逆方向に計算して分割し、作業領域を大きく減らす方法を導け。空文字列の場合も含む。

(1) 通常の編集DPと逆追跡(5点)

通常の編集 DP の境界と漸化式を示し、得点だけなら行を2枚使えばよいことを説明せよ。その最後の2行だけから通常の逆追跡ができない理由も述べよ。

(2) 中間行での分割(6点)

a=⌊m/2⌋a=\lfloor m/2\rfloor とする。F[j]=dist⁡(X[1:a],Y[1:j])F[j]=\operatorname{dist}(X[1:a],Y[1:j])、R[j]=dist⁡(X[a+1:m],Y[j+1:n])R[j]=\operatorname{dist}(X[a+1:m],Y[j+1:n]) とおく。最適費用が min⁡j(F[j]+R[j])\min_j(F[j]+R[j]) であることを、格子経路が第 aa 行を通る事実から証明せよ。

(3) 逆向きDPと添字(6点)

RR を逆向きの2行 DP で計算する具体的な添字を示せ。誤って XX の後半と YY の接頭辞の距離を加える方法に対し、X=Y=ABX=Y=AB、a=1a=1 で最小の jj を選ぶと失敗することを示せ。

(4) 分割復元と基底処理(8点)

最小の分割位置 j∗j* を使って前半・後半を再帰復元する擬似コードを書け。m≤1m\le 1 または n≤1n\le 1、どちらかが0の場合のO(1)O(1)作業空間の基底処理も述べよ。行配列を解放してから再帰すること。

(5) 時間と補助空間(5点)

全計算時間が O(mn+m+n)O(mn+m+n) となることを、各分割後の部分問題の面積から証明せよ。作業空間と出力空間を区別し、列の側を短く選ぶことで O(min⁡(m,n)+log⁡(max⁡(m,n)+1))O(\min(m,n)+\log(\max(m,n)+1)) の補助空間となる条件を説明せよ。

(6) 編集列の具体例(5点)

X=ACGTX=ACGT、Y=AGTY=AGT、a=2a=2 とする。j=0,…,3j=0,\ldots ,3 の F,RF,R とその和を求め、最適分割と操作列を示せ。複数の最適経路がある入力でも、この方法がそのうち一つを必ず返すことを説明せよ。

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

整列ネットワークの正しさと仕事量

N=2qN=2^q 本の線に値を置く。比較器は指定した2線の小さい値を上側、大きい値を下側へ置き、比較器の位置と接続は入力値によらず固定される。同時に実行できる、線を共有しない比較器の集合を1層とする。総比較器数を仕事量、層数を深さと呼ぶ。バイトニック列とは、巡回回転すると非減少列と非増加列の連結になる列である。昇順バイトニック併合では前半 ii と後半 i+N/2i+N/2 を比較し、小さい側を前半へ置いて、両半分を再帰併合する。

(1) 閾値写像と0–1原理(4点)

任意の値を閾値 θ\theta 未満なら0、それ以外なら1に写すと、比較器の出力とこの写像が交換することを示せ。それを用いて、0/10/1入力をすべて整列できるネットワークは任意の全順序入力を整列できることを証明せよ。

(2) バイトニック併合の正しさ(5点)

0/10/1のバイトニック列では、巡回的に1が一つの区間をなす。(前半ii,後半i+N/2i+N/2) の比較後、両半分がバイトニックで、前半の全値が後半の全値以下となることを示せ。そこから一般値のバイトニック併合の正しさを導け。

(3) 仕事量と深さの漸化式(7点)

前半を昇順、後半を降順に再帰整列し、全体をバイトニック併合する整列ネットワークを構成せよ。併合と全整列の仕事量・深さの漸化式を立て、NN と qq の閉じた式を求めよ。

(4) 仕事量と深さの下界(6点)

固定ネットワークで任意の相異なる NN キーを整列する場合、仕事量 Ω(Nlog⁡N)\Omega (N \log N)、深さ Ω(log⁡N)\Omega (\log N) が必要であることを別々に証明せよ。後者では、深さ dd の出力線が影響を受け得る入力線数を考えよ。

(5) 具体例と番兵(4点)

N=8N=8 のバイトニック整列の仕事量と深さを求め、(4)の下界に対して何倍の対数因子を余分に使うかを述べよ。NN が2の冪でない場合に、番兵を使って拡張する方法も示せ。

(6) 安定性の反例と修正(4点)

各比較器が同キーを交換しなくても、ネットワーク全体の安定性は保証されない。3線の比較器列 (1,3),(1,2),(2,3)(1,3),(1,2),(2,3) と入力 (2,a),(2,b),(1,c)(2,a),(2,b),(1,c) で示せ。任意の正しいネットワークを安定整列にする修正を述べよ。