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.

第13回 制約・近似・記憶階層

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

← 备考目录

試験時間(目安)満点問題数
200分100点全3問
問題分野テーマ配点
問題1グラフ理論必須辺と禁止辺を持つ最小全域木35点
問題2動的計画法価値を丸めるナップサック近似35点
問題3整列アルゴリズムブロック転送を減らす多路併合30点

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

必須辺と禁止辺を持つ最小全域木

連結な単純無向グラフ G=(V,E)G=(V,E) に非負の辺重みが与えられている。辺集合 FF の各辺は必ず採用し、辺集合 BB の各辺は採用してはならない。この条件を満たす全域木のうち、総重みが最小のものを求める。条件を満たす木が存在しない場合には、その理由を証明する情報も出力したい。F,BF,B は EE の部分集合であり、両者が重なる入力も許す。集合の指定は辺番号の列で与えられる。

(1) 実現可能性の必要条件(4点)

実現可能性のために F∩B=∅F\cap B=\varnothing と、FF が閉路を含まないことが必要な理由を示せ。これら二条件だけでは十分でない具体例も一つ与えよ。

(2) 必須森の縮約(6点)

FF が森であるとする。FF の各連結成分を一つの頂点に縮約し、BB の辺と縮約後の自己ループを除く。得られる多重グラフの連結性が、実現可能性の必要十分条件であることを証明せよ。

(3) 重みと全域木の対応(6点)

縮約による最適化が重みを保存することを示せ。元の条件付き全域木と縮約後の全域木の対応を述べ、平行辺を残してよい理由を説明せよ。

(4) 制約付きMSTの具体例(7点)

辺と重みを 12:8,23:2,13:1,34:4,45:3,25:6,15:7,24:512:8,23:2,13:1,34:4,45:3,25:6,15:7,24:5、F={12,34}F=\{12,34\}、B={13}B=\{13\} とする。縮約後の頂点・辺を示し、条件付き最小全域木とその総重みを求めよ。

(5) 集合管理とKruskal法(7点)

互いに素な集合を根付き木で表し、小さい集合の根を大きい集合の根へ結ぶ方法を用いる。縮約グラフを明示的に作らず、必須辺を先に併合して残りを重み順に処理する擬似コードを書け。木の深さの上界を証明し、正しさと最悪時間を述べよ。

(6) 実現不能の証明書(5点)

実現不能を証明する証拠を、F∩B≠∅F\cap B\ne \varnothing、FF に閉路がある、残ったグラフが非連結、の三場合について示せ。証拠を受け取った第三者が O(∣V∣+∣E∣)O(\vert V\vert +\vert E\vert ) 時間で検証できることも説明せよ。

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

価値を丸めるナップサック近似

nn 個の品物に正の整数重量 wiw_{i} と非負整数価値 viv_{i} があり、容量 WW 以下で価値和を最大化したい。WWは非負整数であり、各品物は高々1回選べる。wi>Ww_{i}>W の品物を除いた後の個数を改めて nn とし、n≥1n\ge 1、vmax⁡=max⁡vi>0v_{\max}=\max v_{i}>0 と仮定する。それ以外は空集合を返せばよい。誤差係数は有理数 0<ε<10<\varepsilon <1。K=εvmax⁡/nK=\varepsilon v_{\max}/n、丸め価値 ai=⌊vi/K⌋a_{i}=\lfloor v_{i}/K\rfloor とする。有理数の演算・整数の加算比較を1操作とするモデルで評価せよ。

(1) 丸め価値と状態(5点)

P=∑aiP=\sum a_i が n2/εn^{2}/\varepsilon 以下であることを示せ。価値を状態とし、各状態で必要な最小重量を保持する動的計画法を、境界条件を含めて定義せよ。

(2) 丸めた目的関数の最適化(6点)

丸め価値の和が最大になる実現可能な集合 XX を得るアルゴリズムを書け。元の価値の和が最大になる集合を直接探すのではないことを明確にし、時間計算量を示せ。

(3) 加法誤差の証明(6点)

任意の集合 YY について K∑i∈Yai≤∑i∈YviK\sum_{i\in Y} a_{i}\le \sum_{i\in Y} v_{i} と、K∑i∈Yai≥∑i∈Yvi−∣Y∣KK\sum_{i\in Y} a_{i}\ge \sum_{i\in Y} v_{i}-\vert Y\vert K を示せ。この不等式と丸めた問題の最適性を用い、v(X)≥OPT−nKv(X)\ge OPT-nK を証明せよ。

(4) 相対保証と計算モデル(7点)

前処理後には vmax⁡≤OPTv_{\max}\le OPT が成立する理由を説明し、v(X)≥(1−ε)OPTv(X)\ge (1-\varepsilon )OPT を導け。実行時間が入力価値の大きさでなく nn と 1/ε1/\varepsilon の多項式になることの意味も述べよ。

(5) 近似解の具体例(6点)

品物を (w,v)=(2,6),(3,9),(4,13),(5,15)(w,v)=(2,6),(3,9),(4,13),(5,15)、W=7W=7、ε=1/2\varepsilon =1/2 とする。KK、aa の列、丸め問題で選ばれる集合と元の価値を求め、厳密な最適集合・最適値と比較せよ。

(6) 一次元更新と復元(5点)

最小重量だけなら価値方向の1次元配列で更新できる。更新を降順にする理由を説明し、ai=0a_{i}=0 の扱いも述べよ。選択集合を確実に復元するための記憶方法と、その空間・復元時間を示せ。

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

ブロック転送を減らす多路併合

N≥1N\ge 1 個のレコードを外部記憶で安定に整列する。1ブロックは B≥1B\ge 1 個のレコードを持ち、1回のブロック読み書きを1I/O1 I/O と数える。内部にはデータ用バッファ MM 個分を置け、M≥3BM\ge 3B とする。管理用 O(M/B)O(M/B) 語も利用でき、全内部記憶は O(M)O(M)。比較・移動の内部計算時間と I/O を区別せよ。各レコードには元の入力位置を付けられる。まず連続する高々 MM 個ずつを内部で整列し、外部の整列済みランとして保存する。

(1) 初期ランとI/O(6点)

初期ランの数と生成時の I/O・内部比較回数を示せ。ランはブロック境界に保存し、最後のブロックは未使用部分を含んでもよい。N<MN<M の場合も含めて式を示せ。

(2) バッファと多路併合(6点)

f=⌊M/B⌋−1f=\lfloor M/B\rfloor -1 本のランを一度に併合する方法を、入力バッファ・出力バッファ・最小ヒープに分けて説明せよ。バッファが空または満杯になったときの処理と安定性も示せ。

(3) 併合段数と端数ブロック(7点)

R=⌈N/M⌉R=\lceil N/M\rceil とする。すべてのランを ff 本ずつ併合する段数を求め、整列全体の I/O の上界を N,M,BN,M,B で示せ。ラン末尾の不完全ブロックが追加する費用も無視せず評価せよ。

(4) I/Oの具体例(6点)

N=4096N=4096、B=16B=16、M=256M=256 とする。初期ラン数、ff、併合段数、全体の I/O を求めよ。この例では全ラン長が BB の倍数である。2本ずつの併合を繰り返す方式の I/O と比較せよ。

(5) 内部比較回数(5点)

多路併合の1段と全体の内部比較回数を評価せよ。比較回数のオーダーが通常の比較整列と変わらなくても、ff を増やすことが外部記憶上で有利になる理由を説明せよ。