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.

第3回 局所選択が正しい条件

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論最小全域木と同じ重みの落とし穴35点
問題2動的計画法重み付き共通部分列と辞書式復元35点
問題3整列アルゴリズム重複キーに強い三分割クイックソート30点

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

最小全域木と同じ重みの落とし穴

連結単純無向グラフGGの各辺eeに実数重みw(e)w(e)がある。全域木の重みは辺重みの和であり、最小全域木をMSTと略す。同じ重みの辺は許す。部分集合S⊂VS\subset V、S≠∅, S≠VS\ne\varnothing,\ S\ne Vをまたぐ辺をカット辺という。利用する最小辺の性質は証明してから用いること。

(1) カットの最軽量辺(6点)

あるカットの最軽量辺eeが、少なくとも一つのMSTに含まれることを交換法で証明せよ。eeがカットの唯一の最軽量辺なら、すべてのMSTに含まれることも証明せよ。

(2) 閉路の最重量辺(7点)

閉路上の唯一の最重量辺は、どのMSTにも含まれないことを証明せよ。「閉路上の最重量辺は、同重みがあってもすべてMSTから除外できる」を反例で否定せよ。

(3) MSTの列挙と辺の分類(8点)

V={a,b,c,d}V=\{a,b,c,d\}、辺の重みを次のようにする。

辺ababacacbcbcbdbdcdcdadad
重み122336

すべてのMSTを列挙し、どのMSTにも含まれる辺、少なくとも一つに含まれる辺、どれにも含まれない辺を分類せよ。

(4) 辺の採用と成分管理(8点)

辺を重み順に整列し、閉路を作らない辺を順に加える方法を示せ。連結成分を管理する素朴なラベル更新法でもよい。その正しさを示し、整列部分と成分管理部分の計算量を分けて評価せよ。

(5) 最適性条件と一意性(6点)

ある全域木TTについて、すべての非木辺e={u,v}e=\{u,v\}の重みがTT上のu−vu-v経路の最大辺重み以上なら、TTがMSTであることを証明せよ。全辺の重みが異なる場合、MSTの一意性を導け。

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

重み付き共通部分列と辞書式復元

X,YX,Yは長さm,nm,nの文字列で、文字集合Σ\Sigmaには全順序がある。文字aaを一つ選ぶ得点を正整数w(a)w(a)とする。共通部分列ZZの得点は各文字得点の和。まず最大得点を求め、さらに最大得点の共通部分列のうち辞書式で最小の文字列を出力する。辞書順では一方が他方の接頭辞なら短い方を小さいとする。

(1) 接尾辞DPと漸化式(6点)

接尾辞X[i…m],Y[j…n]X[i\ldots m],Y[j\ldots n]の最大得点をD[i,j]D[i,j]とする。境界条件と漸化式を導け。同じ文字の場合にも、不採用側の候補を残してよいことを説明せよ。

(2) 正しさと得点の比較(7点)

漸化式の正しさを証明し、最大得点だけを求める時間・空間計算量を示せ。「長い共通部分列ほど高得点である」という主張を反例で否定せよ。

(3) 辞書式最小の貪欲復元(8点)

各位置以降で文字aaが最初に現れる位置をnextX⁡[i,a],nextY⁡[j,a]\operatorname{nextX}[i,a],\operatorname{nextY}[j,a]として前計算する。残り得点RRを保ちながら辞書式最小の最適解を貪欲に復元する方法を示し、その選択が安全であることを証明せよ。

(4) 具体例(8点)

X=ABACX=\mathrm{ABAC}、Y=BAACY=\mathrm{BAAC}、w(A)=2, w(B)=5, w(C)=1w(A)=2,\ w(B)=5,\ w(C)=1とする。最大得点と辞書式最小の最適共通部分列を求めよ。すべての文字得点を1にした場合の答えも求めよ。

(5) 計算量と非正得点(6点)

前計算と復元を含む時間・補助空間計算量をm,n,∣Σ∣m,n,|\Sigma|,出力長ℓ\ellで示せ。得点0で復元を停止できる理由を説明せよ。文字得点が0または負でもよい場合、同じ停止規則と貪欲復元が正しいかを検討し、正しいなら理由、誤るなら反例を示せ。

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

重複キーに強い三分割クイックソート

配列AAには同じキーが複数現れてよい。部分配列からピボットppを一つ選び、キーがppより小さい区間、等しい区間、大きい区間へその場で三分割する。等しい区間は再帰的に整列しない。比較と交換はO(1)O(1)。後半の期待値分析では各再帰部分配列の要素位置を一様に選ぶ。

(1) 三分割と不変条件(5点)

三分割の擬似コードを書き、走査中の三つの確定区間と未分類区間を表す不変条件を示せ。走査時間と補助空間を評価せよ。

(2) 全キーが等しい場合(5点)

すべてのキーが同じ場合の三分割法の計算量を示せ。等しいキーをすべて片側へ送る二分割法との違いを、再帰式を用いて説明せよ。

(3) 期待比較回数(7点)

キーがすべて異なる場合、順位i,ji,jの二要素が直接比較される確率を求め、それを用いて期待比較回数O(nlog⁡n)O(n \log n)を導け。再帰木を平均的に釣り合うと仮定するだけの説明では不十分である。

(4) 具体例と安定性(7点)

A=[3,1,3,2,3,1]A=[3,1,3,2,3,1]をピボット3で三分割した結果の各区間の多重集合を示せ。この整列法が一般に安定でない具体例を示し、元の位置を比較キーに付加する安定化が「重複キーに強い」という性質へ与える影響を論じよ。

(5) 最悪時間と再帰空間(6点)

常に先頭要素をピボットにする場合の最悪入力を示せ。ランダム化でも最悪時間O(n2)O(n^2)が残る理由と、再帰の深さを抑えるため小さい区間だけを再帰し大きい区間をループで処理する方法の空間上界を説明せよ。