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.

第10回 二重故障・区間の個数・桁の並列処理

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

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論二つの木辺を失ったときの連結性35点
問題2動的計画法ギャップ区間をちょうどq個にする35点
問題3整列アルゴリズム符号付き整数の安定基数整列と並列化30点

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

二つの木辺を失ったときの連結性

単純連結無向グラフ G=(V,E)G=(V,E)、全域木 TT、相異なる木辺 e,fe,f が与えられる。n=∣V∣≥3n=\vert V\vert \ge 3、m=∣E∣m=\vert E\vert とする。非木辺 gg を TT に加えるとできる閉路を基本閉路と呼ぶ。木辺 xx について、基本閉路が xx を含む非木辺の集合を AxA_{x} とする。GG から e,fe,f を同時に除いたときの連結性を、これらの集合だけで判定したい。集合は辺番号ごとの0−10-1配列で厳密に保持し、ハッシュ衝突の可能性を正しさの根拠にしてはならない。

(1) 基本閉路と橋(6点)

非木辺ggがAxA_{x}に属することと、T−xT-xの二成分をggが結ぶことが同値であると証明せよ。さらに、AxA_{x}が空であることが、xxがGGの橋であるための必要十分条件であることを示せ。

(2) 三成分の縮約(7点)

TTからe,fe,fを除くと三成分になる。これらを頂点に縮約し、非木辺を加えた補助グラフを考える。三成分間の辺を「AeA_{e}だけに属する」「AfA_fだけに属する」「両方に属する」の三種類と対応付け、e,fe,fが入れ子の位置と別の枝の位置にある場合を説明せよ。

(3) 二重故障の必要十分条件(8点)

G−{e,f}G-\{e,f\}が非連結であるための必要十分条件が、Ae=∅A_{e}=\varnothing、Af=∅A_f=\varnothing、Ae=AfA_{e}=A_fのいずれかであることを証明せよ。「各辺が単独では橋でないなら、二本同時に消しても連結」という主張を反例で否定せよ。

(4) 木パスの具体例(8点)

TTを1−2−3−41-2-3-4のパスとする。非木辺が14だけの場合と、13,2413,24の二本の場合について、各AxA_{x}を求め、相異なる木辺二本の全ての組の故障結果を判定せよ。ijは辺{i,j}\{ i,j \}の略記である。

(5) 前処理と分断の証明書(6点)

全てのAxA_{x}を前処理する方法と、問い合わせ(e,f)(e,f)に答える手順を示せ。素朴な木パス探索による時間、集合の記憶量、一問い合わせの最悪時間を評価せよ。非連結と判定した際、三成分の縮約を使って分断を証明する頂点集合を出力する方法も示せ。

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

ギャップ区間をちょうどq個にする

文字列X,YX,Yの長さをm,n≥1m,n\ge 1とする。全体をアラインメントし、同字の文字対は3、異字の文字対は-4、ギャップ一列は-1の得点とする。両側ギャップは禁止する。「ギャップ区間」は、同じ側のギャップが連続する極大の列区間である。異なる側のギャップが隣接することは許し、その場合は別の二区間と数える。非負整数qqが指定され、ギャップ区間がちょうどqq個の最大得点を求める。解がなければ−∞-\inftyとする。

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

消費済み文字数i,ji,j、ギャップ区間数tt、最後の列の種類を記録する三状態M,E,FM,E,Fを定義せよ。空の開始状態と実現不可能な状態の初期値を示し、接頭辞の片方だけが空の場合も扱え。

(2) 区間数を数える漸化式(7点)

三状態の漸化式を導け。同じ側のギャップの延長、文字対の後の開始、反対側のギャップからの切替を区別し、どの場合にttが増えるかを示せ。

(3) 正しさと計算量(8点)

最後の列を除くことに基づいて正しさを証明せよ。計算順序と時間・得点だけの場合の空間を示せ。q>m+nq>m+nなら計算せず実現不能と答えてよい理由も述べよ。

(4) 具体例と実現不可能性(8点)

X=AB,Y=ACX=AB,Y=ACについてq=0,1,2q=0,1,2の最適得点と、可能な場合のアラインメントを求めよ。q=1q=1が不可能となることは表の数値だけでなく、両文字列の長さから説明せよ。

(5) 末尾状態と復元(6点)

同じ(i,j,t)(i,j,t)で最大得点一つだけを残し、末尾の種類を忘れる方法が不適切な理由を示せ。(1,1,2)(1,1,2)に到達するX1−/−Y1X_{1}-/-Y_{1}と−X1/Y1−-X_{1}/Y_{1}-を比べ、次のXX側の文字をギャップへ対応させると何が異なるか説明せよ。最適解一つの復元方法と必要領域も示せ。

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

符号付き整数の安定基数整列と並列化

N≥1N\ge 1個のレコードのキーはwwビットの2の補数整数で、範囲は−2(w−1)-2^(w-1)から2(w−1)−12^(w-1)-1である。wwは正整数。キーのビット表現から最上位の符号ビットを反転した非負整数uuを作り、bbビットずつの桁を下位から処理する。1≤b≤w1\le b\le w、基数R=2bR=2^b、段数L=⌈w/b⌉L=\lceil w/b\rceil。最上位の不足ビットは0で補う。wwビット語のビット抽出と整数添字演算をO(1)O(1)とする。各段では安定な計数整列を用いる。

(1) 符号ビットの反転(5点)

符号ビットの反転が符号付きキーの昇順を非負整数uuの昇順へ変える理由を証明せよ。負のキーを通常の非負ビット表現としてそのまま整列すると誤る例を示せ。

(2) 安定な一桁計数整列(5点)

一桁の安定な計数整列の擬似コードを書け。計数、各桁値の出力開始位置、入力の走査方向を明記し、時間・作業領域を評価せよ。

(3) 下位桁からの不変条件(7点)

下位からtt桁を処理した後の不変条件を示し、LL段後に安定整列されることを証明せよ。上位桁の段が安定でないと失敗する例を、二桁の非負整数で構成せよ。

(4) 符号付き整数の具体例(7点)

w=8,b=4w=8,b=4として[-1,0,−128,127,−21,0,-128,127,-2]を処理する。符号ビット反転後の値を16進数で示し、各桁の段の終了時のレコード順と最終結果を求めよ。同キーの識別子付きレコードを加えた場合の順序も説明せよ。

(5) 衝突のない並列化(6点)

入力をp≤Np\le N個の連続ブロックに分け、各ブロックの走査は一つの処理器で行う。ヒストグラム処理では必要な数の処理器を利用できる仕事・深さモデルとする。桁別ヒストグラム、同桁の先行ブロック数、ブロック内の先行同桁数を使い、書込衝突のない並列一桁整列を設計せよ。長さssのprefix sumは仕事O(s)O(s)、深さO(log⁡(s+1))O(\log(s+1))で行えると仮定し、一段と全LL段の仕事量・深さ・空間を評価せよ。