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.

第18回 同率の選択・資源の競合・確率の保証

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

← 备考目录

試験時間(目安)満点問題数
210分100点全3問
問題分野テーマ配点
問題1グラフ理論最小全域木に必須の辺・選択可能な辺35点
問題2動的計画法二つの予算と辞書順の最適解35点
問題3整列アルゴリズムランダムなクイックソートは何を保証するか30点

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

最小全域木に必須の辺・選択可能な辺

連結単純無向グラフ G=(V,E)G=(V,E) に実数の辺重みが与えられる。各辺を「すべての最小全域木に含まれる」「一部には含まれるが一部には含まれない」「どの最小全域木にも含まれない」の3種類に分類したい。同じ重みの辺が多数あることを許す。重み ww の処理直前に、ww より小さい辺だけで連結される頂点を縮約する。残った重み ww の辺から作る補助グラフは平行辺を持ち得る。入力が単純グラフでも、縮約後まで単純とは限らない。各辺には固有の辺番号があるものとする。

(1) 小さい重みによる縮約(5点)

重み ww の辺の両端点が、ww より小さい辺だけですでに連結されている場合、その辺はどの最小全域木にも含まれないことを証明せよ。閉路上の最大辺に関する主張で、等重みの場合と混同しないこと。

(2) 補助グラフの橋と分類(7点)

縮約後の補助グラフで、橋となる辺はすべての最小全域木に必要であり、橋でない非ループ辺は一部に含まれ一部に含まれないことを証明せよ。補助グラフが非連結でも成分ごとに扱える理由を示せ。

(3) 同率辺と平行辺の反例(6点)

同じ重みの辺を1本ずつ追加し、そのたびに連結集合を更新して分類する方法が誤る例を示せ。また、補助グラフの DFS で親頂点への辺をすべて無視する実装が誤る平行辺の例を示し、正しい扱いを述べよ。

(4) 重みごとのバッチ処理(7点)

重み順のバッチ処理、連結集合の縮約、補助グラフでの橋検出を組み合わせた擬似コードを書け。各バッチの分類が完了してから集合を統合すること。全補助グラフのサイズ合計を用いて時間・空間を評価せよ。

(5) 辺分類の具体例(5点)

頂点 a,b,c,d,e,f,ga,b,c,d,e,f,g、重み1の辺 ab,bc,ca,deab,bc,ca,de、重み2の辺 cd,bd,ef,cf,fgcd,bd,ef,cf,fg、重み3の辺 ag を考える。各辺を3種類に分類し、重み2の補助グラフを描くか、頂点・平行辺を明記せよ。

(6) 同時選択と一意性(5点)

「一部に含まれる」辺がすべて同時に含まれる最小全域木は存在するか。一般には存在しないことを示せ。また、すべての辺の分類結果から最小全域木の一意性を判定する必要十分条件を述べよ。

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

二つの予算と辞書順の最適解

nn 個の品物について、二資源の消費量 ai,bia_{i},b_{i} は非負整数で ai+bi>0a_{i}+b_{i}>0、価値 viv_{i} は正整数である。各品物は高々1回選べる。資源の上限は A,BA,B で、価値和を最大化する。価値が等しい解では選択ビット列 (x1,…,xn)(x_{1},\ldots ,x_{n}) を辞書順最小にする。ただし 0<10<1 とし、選ばないことを0、選ぶことを1とする。これは選んだ品物番号の列の辞書順とは別の規則である。資源を使い切る必要はない。資源量と価値が異なる状態を、十分な根拠なく一つにまとめないこと。

(1) 二資源の状態と漸化式(5点)

Fi(a,b)F_{i}(a,b) を最初の ii 品物から消費量がちょうど (a,b)(a,b) となる最大価値として、境界と漸化式を導け。最後の答えに必要な最大値の範囲も述べよ。

(2) その場更新の順序(6点)

1枚の二次元表で価値だけを求める更新順を示せ。ai=0a_{i}=0 または bi=0b_{i}=0 の場合も同じ品物を再利用しないことを証明せよ。両方を昇順に更新すると失敗する具体例を与えよ。

(3) 辞書順最小の復元(6点)

前向き DP で等価値のとき常に「現在の品物を選ばない」候補を優先すると、要求した辞書順になるとは限らない。2品物の反例を示せ。後ろ向きの最適価値表を使い、最初のビットから正しく決める条件を導け。

(4) 支配関係と辞書順(6点)

同じ処理段階の状態 (a,b,v)(a,b,v) が (aa′,bb′,vv′) に対し a≤aa\le a′,b≤bb\le b′,v≥vv\ge v′ なら、価値のみの最大化には後者を削除できることを証明せよ。a+ba+b の小ささと価値だけで比較する誤りを反例で示し、辞書順の同率処理には追加情報が必要なことも述べよ。

(5) 二予算の具体例(7点)

上限 (A,B)=(3,3)(A,B)=(3,3)、品物が順に (a,b,v)=(2,1,6),(2,1,6),(1,2,6),(1,1,4),(0,2,3)(a,b,v)=(2,1,6),(2,1,6),(1,2,6),(1,1,4),(0,2,3) のとき、最適価値と辞書順最小ビット列を求めよ。最適な選択が他にある場合はそれも挙げ、最適性を説明せよ。

(6) 完全な復元と計算量(5点)

辞書順最小解を復元する完全な擬似コードを書け。価値だけの場合と、全後ろ向き表を保存して復元する場合の時間・空間を評価せよ。上限の数字ではなく入力のビット長に対して、擬多項式である理由を説明せよ。

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

ランダムなクイックソートは何を保証するか

互いに異なるキーを持つ N≥2N\ge 2 個の要素をクイックソートする。サイズ ss の部分配列では、その ss 要素から独立に一様ランダムなピボットを選び、残りの s−1s-1 個を各1回比較して左右に分ける。入力は乱数を引く前に固定され、乱数を見てから値を変更する相手はいない。比較回数を CC、最大分割深さを DD とする。平均の保証、最悪の保証、高確率の保証を区別したい。ln は自然対数、HN=∑i=1N1/iH_N=\sum _{i=1}^N 1/i とする。必要なら二項分布について Pr⁡[Bin⁡(t,1/2)≤t/4]≤exp⁡(−t/16)\Pr[\operatorname{Bin}(t,1/2)\le t/4]\le \exp(-t/16) を使ってよい。

(1) 二要素の比較確率(6点)

キーを順位1,…,N1,\ldots ,Nで表す。順位 i<ji<j の二要素が比較される確率が 2/(j−i+1)2/(j-i+1) となる理由を示せ。区間内で最初に選ばれるピボットを使い、区間外のピボットがこの議論を妨げないことを説明せよ。

(2) 期待比較数と最悪値(8点)

(1)から E[C]=2(N+1)HN−4NE[C]=2(N+1)H_N-4N を導け。最悪値 N(N−1)/2N(N-1)/2 が生じるピボット列とその確率も求め、期待値 O(Nlog⁡N)O(N \log N) が最悪 O(Nlog⁡N)O(N \log N) を意味しないことを説明せよ。

(3) 良いピボットの確率(5点)

サイズ ss の分割で両側のサイズが高々3s/43s/4なら、そのピボットを良いと呼ぶ。良い確率が少なくとも1/21/2であり、ある要素の経路上で ⌈log⁡4/3N⌉\lceil \log_{4/3}N\rceil 回の良い分割があれば経路が終了することを示せ。

(4) 深さの高確率保証(6点)

t=⌈64ln⁡N⌉t=\lceil 64 \ln N\rceil とする。各要素の経路上の良い分割数を二項分布で下から評価し、Pr⁡[D>t]≤N−3\Pr[D>t]\le N^{-3} を導け。その結果から高確率で比較回数が O(Nlog⁡N)O(N \log N) になることを示せ。定数64の最適化は不要である。

(5) スタックと最悪比較数(5点)

常に小さい側を再帰処理し、大きい側はループで続ければ、どのピボット列でも呼出しスタックが O(log⁡N)O(\log N) になることを証明せよ。この工夫が比較回数の最悪値も改善するか。また、ピボット位置を知ってから相手がキーを決められるモデルで、上の確率保証が使えない理由を述べよ。