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.

第2回 数える・復元する・順序を測る

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論最短経路の本数と必須頂点35点
問題2動的計画法ちょうどr品を選ぶナップサック35点
問題3整列アルゴリズム転倒数から最小隣接交換回数へ30点

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

最短経路の本数と必須頂点

単純無向グラフGGに異なる頂点s,ts,tが与えられ、ssからttへの経路が存在する。辺の長さはすべて1。最短s−ts-t経路の本数を数え、すべての最短経路が通る頂点を調べたい。本数は指数的に大きくなり得るが、本問では正確な整数の加算・乗算・比較をO(1)O(1)とする算術演算回数を評価する。

(1) 最短経路に含まれる条件(6点)

ssとttからのBFSにより距離ds,dtd_s,d_tを求める。頂点vvがいずれかの最短経路に含まれる必要十分条件を示せ。最短経路に含まれる向き付き辺の条件も導け。

(2) 最短経路DAGと経路数(7点)

最短経路上の辺をssからの距離が増える向きに向ける。この有向グラフが非巡回であることを証明し、ssから各頂点への経路数P[v]P[v]を数える漸化式と計算順序を示せ。

(3) 必須頂点の判定(8点)

各頂点からttへの経路数Q[v]Q[v]も計算する。すべての最短経路がvvを通ることをP,QP,Qで判定せよ。二つの経路を連結したときに頂点の重複が生じない理由を証明せよ。

(4) 具体例と必須辺(8点)

V={s,a,b,c,d,t},E={{s,a},{s,b},{a,c},{b,c},{a,d},{c,t},{d,t}}.\begin{aligned}V&=\{s,a,b,c,d,t\},\\E&=\{\{s,a\},\{s,b\},\{a,c\},\{b,c\},\{a,d\},\{c,t\},\{d,t\}\}.\end{aligned}

について、距離表、P,QP,Q、最短経路数、必須頂点を求めよ。必須辺もすべて求めよ。

(5) 全体の計算量と剰余の反例(6点)

アルゴリズム全体の擬似コードと算術演算回数を示せ。「経路数を大きな整数MMで割った余りだけで比較すれば、必須頂点を常に正確に判定できる」という主張を否定せよ。

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

ちょうどr品を選ぶナップサック

nn個の品物があり、品物iiの正整数重量をwiw_i、整数価値をviv_iとする。価値は負でもよい。各品物は高々1回選べる。総重量WW以下、選ぶ個数がちょうどrrという制約の下で価値を最大化する。WWは非負整数、0≤r≤n0\le r\le n。実現不可能な場合はその旨を返す。

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

接頭品物数ii、重量上限cc、選択個数ttを用いて状態を定義し、負の価値と実現不可能性を正しく扱う初期値と漸化式を示せ。

(2) 正しさと擬多項式時間(7点)

漸化式の正しさを最後の品物を選ぶ場合と選ばない場合に分けて証明せよ。表の大きさと時間計算量を示し、この計算量が入力のビット長に対して多項式とは限らない理由を説明せよ。

(3) その場更新と走査順序(8点)

iiの次元を取り除き、二次元表をその場で更新する擬似コードを書け。個数と容量の走査順序を示せ。個数を昇順に走査すると同じ品物を複数回選ぶ可能性があることを具体例で示せ。

(4) 具体例と復元(8点)

(wi,viw_i,v_i)が順に(2,5),(3,6),(4,8),(1,−1)、W=5, r=2W=5,\ r=2とする。最適価値と選ぶ品物を求めよ。W=1, r=2W=1,\ r=2の場合も答えよ。表から最適な品物集合を復元する手順を示せ。

(5) 状態の支配条件(6点)

容量がWW以下の状態を、重量と価値の組で保持する方法を考える。選択個数が同じ状態についての安全な支配条件を示せ。選択個数の異なる状態にも同じ支配規則を適用できない反例を示せ。

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

転倒数から最小隣接交換回数へ

nn個の互いに異なるキーからなる配列AAについて、i<ji<jかつA[i]>A[j]A[i]>A[j]となる対(i,ji,j)を転倒と呼ぶ。転倒数をI(A)I(A)とする。隣接する二要素の交換だけを用いて配列を昇順に整列したい。後半では同値キーも許し、同値対を転倒には数えない。

(1) 隣接交換と転倒数(5点)

一度の隣接交換によって転倒数がどのように変化するかを証明し、昇順整列に必要な隣接交換回数の下界を示せ。

(2) 挿入整列の交換回数(5点)

挿入整列がちょうどI(A)I(A)回の隣接交換で整列できることを示せ。その比較回数と移動回数をn,I(A)n,I(A)で評価し、整列済み入力と逆順入力を比較せよ。

(3) 併合による転倒数の計算(7点)

併合整列を用いてI(A)I(A)をO(nlog⁡n)O(n \log n)時間で求める擬似コードを書け。右半分の要素を先に出すときに加算する数を示し、分割・併合の正しさを証明せよ。

(4) 具体例と同値キー(7点)

A=[5,1,4,2,3]A=[5,1,4,2,3]の転倒数と最小隣接交換回数を求めよ。同値キーを許す場合、併合時の比較をどのように変更すれば、厳密な転倒数を数えながら安定性も保てるか説明せよ。

(5) 二つの順列の順序差(6点)

同じnn個の識別子をそれぞれ一度含む二つの順列P,QP,Qの順序の相違を、PPからQQへ変える最小隣接交換回数で測る。QQの順位を用いて一つの転倒数問題へ帰着し、時間計算量を示せ。