平均の分析 (14 点)

クイックソートも二分探索木も平均を分析すると結構有力なものです。 しかしクイックソートが幅広く使われるのに、(単純な) 二分探索木はほとんど使われない。 次の項目に答えてその理由を考えなさい。

クイックソートの平均計算量: O(n log n)

クイックソートの平均計算量の前提: 全ての順番が同じ割合で出現

クイックソートの最悪の計算量: O(n²)

クイックソートの最悪の計算量の条件: 項目の順番が既に降順または昇順

二分探索木の探索の平均計算量: O(log n)

二分探索木の探索の平均計算量の前提: 全ての挿入順番が同じ割合で出現

二分探索木の探索の最悪の計算量: O(n)

二分探索木の探索の最悪の計算量の条件: 項目の挿入順番が降順または昇順

クイックソートで最悪の計算量を避けるためにとられる対策 (二種類):
1) 三つの項目の中央値をピボットとして選択
2) 乱数でピボットを選択

クイックソートで最悪の計算量を避けるためにとられる対策が二分探索木でなぜとれないのかの理由:
クイックソートではすべての項目を配列で同時に扱うに対し、二分探索木で順番の挿入は変えない

(単純な) 二分探索木をもとに、挿入と削除の時に工夫して効率が保証できる木の種類 (二種類): 1) ALV 木
2) 赤黒木

流れ図とその特徴 (8 点)

アルゴリズムの表現に流れ図がよく使われる。流れ図の具体例を書いたうえで、流れ図の利点と問題点について述べなさい。

[具体例省略]

利点: 図として非常に直観的な表現で、素人にも説明可能。

問題点: コンピュータ上での作成には手間がかかって、データの交換も困難。 流れ図の矢印は goto に相当するが、これは構造化プログラミングの繰り返しや分岐と隔たりがある。

Rabin-Karp のアルゴリズムとハッシュ関数 (合計 22 点)

Rabin-Karp のアルゴリズムを疑似コードで書きなさい。なお、ハッシュ値の計算に使われるアルファベットの基数 b と法 d は定数として与えられていると仮定して良い。 (16 点)

algorithm rabin_carp
  inputs: text t of length n (t[1]...t[n]),
          pattern p of length m (p[1]...p[m])
  output: position of match or -1 when no match found
  
  hp ← ht ← 0
  for pi from 1 to m do
    hp ← (hp*b + p[pi]) mod d
    ht ← (ht*b + t[pi]) mod d
  end
  for ti from 1 to n-m+1 do
    if hp = ht then
      match ← TRUE
      for pi from 1 to m do
        match ← FALSE if p[pi] ≄ t[ti+pi-1]
      end
      return ti if match
    end
    ht ← ht - t[ti] * (bm-1 mod d)
    ht ← (ht*b + t[ti+m-1]) mod d
  end
end

ハッシュ表に使われるハッシュ関数の注意点を三つ列挙し、説明しなさい。(6 点)

• キーの全部分を考慮しないといけない。一部に限定すると激突が非常に多くなる可能性がある。
• キー以外のデータは関数に使ってはならない。そうしないと項目が見つからなくなる可能性がある。
• キーの同値性を考量しないといけない。(例: 囲碁の定石の場合、白黒上下左右の対称性。)

計算量の比較 (10 点)

次の計算量を小さい順に並びなおしなさい。「<」または「=」で小さい場合と同等な場合を区別しなさい。
(例: O(1)=O(2)<O(nⁿ)。)

O(1.001ⁿ), O(1000 log log n), O(n log n), O(n^1.001), O(n!), O(1.1ⁿ), O(log₇ n),
O(log_n n), O(nⁿ), O(n^1.1) O(1000n) O(7¹⁰⁰), O(n), O(log (n²)),

O(7¹⁰⁰) = O(log_n n) < O(1000 log log n) < O(log₇ n) = O(log (n²)) < O(n) = O(1000n) <
< O(n log n) < O(n^1.001) < O(n^1.1) < O(1.001ⁿ) < O(1.1ⁿ) < O(n!) < O(nⁿ)

整列のアルゴリズムの選択 (合計 18 点)

下記の三つの事情に合わせて、順列のアルゴリズムを実装するように頼まれた。 アルゴリズムを選んで、そのアルゴリズムの名前、仕組み、選んだ理由と実装の場合特に注意すべき点を記述しなさい。

なせかは不明だが、特殊ハードウェアによる非常に速い順位キューの実装があり、それを使って欲しい:

ヒープソート (の変形) をお勧めします。順位キュー だと常に最優先 (最小または最大) の項目が簡単に取り出せるので、データを全部順位キューに 入れてから順次に出しておけば整列は出来上がりです。これはヒープソートで使われる原理と 同じです。計算量は、「非常に速い」を一定時間と仮定する (ハードを使うと十分可能) と、 O(n) とらる。
 
 

扱うデータの量が膨大で、計算機のメインメモリに入りきらない:

マージソートを選ぶ。マージソートはデータを再帰的に部分分けし、部分ごとに整列し、 整列済み部分を順番を考慮して合流させるアルゴリズムなので、ハードディスクなど二次メモリを使う必要がある 時に最適です。計算量は O(n log n)。部分の整列ですが、メインメモリに入る大きさの部分に分け、 その部分にクイックソートなどを使うと全体の効率が上がる。
 
 

入力の全てはすでにほとんど整列され、局所的にだけばらばらになっている:

挿入ソートを選ぶ。計算量は最悪も平均も O(n²) ですが、 順次ソートされている領域を拡大し、ソートされている領域の次の項目をソートされている領域の どこに挿入するかという操作でソートを行っているので、すでにほとんど整列されている場合に非常に速いです。
 
 
 

アルゴリズムとデータ構造についての豆知識 (10 点)

下記の発言の後、正しければ ○、間違いであれば × を書きなさい。

例: 線形探索の計算量は O(n) である: ○
NP 完全問題でも、具体的なデータの場合意外と簡単に溶解ける場合もある: ○
Google は一つのアルゴリズムのおかげで大企業になった: ○
NP 完全問題はアルゴリズムでは解けない: ×
Ruby で変数の方型宣言が不要なので疑似コードに向いている: ○
どんなアルゴリズムでも解けない問題が存在する: ○
「普通」のヒープで合併は O(log n) で可能: ×
最初のアルゴリズムは西暦800年辺りに Muhammad ibn Mūsā al-Khwārizmī に発見された: ×
整列は条件によって O(n) でも実装が可能: ○
アルゴリズムを実装しないと評価できない: ×
NP=P を証明できれば2億円ンの賞金がもらえる: ×

用語の説明 (20 点)

次の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。

invariant

普遍条件; あるデータ構造やアルゴリズムの場合、定義上に常に保たれるべき条件

tractable problem

手に負える問題; 計算量が多項式である問題 (指数的計算量との区別のため)

sentinel

番兵; 配列などの範囲を超えるチェックが不要になるために追加する疑似的な項目

inorder

通り掛け順； 、左の部分木、親、右の部分木の順の (二分) 木の辿り方

genetic algorithm

遺伝的アルゴリズム； 問題の解を遺伝的情報にたとえ、交叉と突然変異で解を近似する

independent set

独立集合; NP 完全問題で、グラフのつながってない最多の頂点を取り出す問題

reduction

帰着; NP 問題などの調査に使われる、ある問題を別の問題に置き換えて解く手法

amortized analysis

償却分析; たまにだけ必要の時間のかかる操作を他の操作に分散させる計算量の分析

dictionary

辞書; データ項目をキーを使って探索、挿入、削除できる抽象データ型

insertion sort

挿入ソート; 項目を次々とすでにソートされている領域の挿入により行われるソート方法

B+木の容量 (14 点)

高さ h (h≥1) の B+木の最少と最多のデータ項目の数を計算し、細かく説明しなさい。次の記号を使って、切り上げや切り捨ても考慮しなさい。

• n: データ項目の総数
• L_p: ページの大きさ
• L_k: キーの大きさ
• L_d: (一項目の) データの大きさ (キーを抜く)
• L_pp: ページ番号 (ポインタ) の大きさ
• α_min: 最低占有率 (普通は 0.5)
•   a  : a の単数の切り上げ
•   a  : a の単数の切り捨て

葉の最大項目数: ⌊L_p / (L_k+L_d)⌋
（ページの大きさをキーとデータの大きさで割ったもの)

葉の最低項目数: ⌊α_min⋅⌊L_p / (L_k+L_d)⌋⌋
（最低占有率掛ける葉の最大項目数)

内部節の最大の子供の数: ⌊L_p / (L_k+L_pp)⌋
（ページの大きさをキーとデータの大きさで割ったもの)

内部節の最低の子供の数: ⌊α_min⋅⌊L_p / (L_k+L_pp)⌋⌋
（最低占有率掛ける内部節の最大の子供の数)

高さ hの最大のデータ項目数: ⌊L_p / (L_k+L_pp)⌋^(h-1)⋅ ⌊L_p / (L_k+L_d)⌋
((h-1)は内部節の層の数。内部節の最大の子供の数を(h-1)にすると葉の数になって、
これを葉ごとの最大の項目数と書ける。)

高さ hの最低のデータ項目数: ⌊α_min⋅⌊L_p / (L_k+L_pp)⌋⌋^(h-1)⋅ ⌊α_min⋅⌊L_p / (L_k+L_d)⌋⌋
(最大のデータ項目数のところと同じが、最低占有率も考量する必要がある。

アルゴリズムの設計方針 (合計 24 点)

下記の問題のため、下記のアルゴリズムの設計方針や原理を使って、それぞれアルゴリズムの概略を提案し、予想される計算量、設計方針を使った場合の問題点について述べなさい。

注： この問題の目的は、できるだけ最適解な結果のアルゴリズムの発見よりも、設計方針の知識の応用である。

問題: 距離が三角不等式を満たす巡回セールスマン問題。詳細: 町 (頂点) m₁ から m_n があって、m_i から m_j までの距離 (辺の長さ) が _id_j で与えられた場合、m₁ から出発して、どの順番でもいいがすべての町を一回訪問して m₁ にもどるできるだけ短い巡回になる順番を求める。ただし _id_j + _jd_k ≥ _id_k。

分割統治法 (6 点)

町の二次元配置を見て、南北又は東西に町を二つのほぼ同じ数のグルーブに分け、 それぞれのグループにできるだけ短い巡回を探す。両方の巡回でもう一つの巡回に近い直接つながっている町を見つけ、 二つの巡回を一つの大きい巡回につなぐ。アルゴリズムを再帰的に適用する。町の数が小さい (例： 6以下) の場合、総当たり法で解く。 計算量は O(n log n)。二つの巡回を効率よくつなげるかどうかが課題。

焼き鈍し法 (6 点)

最初は乱数を使って一定の数の解を作る。繰り返し各解から複数の新しい解を作って、 今まで見つけた一番いい解を複数残す。新しい解を作るときに、複数の辺を乱数で決め、つなぎ直す。 繰り返しが進むにつれ、つなぎ直す辺の数 (温度) を少しずつ下げる。それにより、 早いうちに局所的な最適解に陥ることを避けられる。計算量は O(n∙繰り返しの数∙作成する解の数)。 問題点は温度の下げ具合などの調整の必要性。

貪欲アルゴリズム (6 点)

スタートする町を任意で決める。そこから次々と次に一番違い町を見つけ、つなぐ。最後の町から最初の町に戻る。 計算量は O(n²) (町ごとに残りの一番近い町を計算するため)。 部分的には特に最初の方では結構いい結果が期待できるが、最後の方は場合によって相当距離が増える可能性もある。

動的プログラミング (6 点)

町を東西または南北の方向 (又は両方向) に小さいグループに分ける。 グループごとの最適解を総当たり法で決める。隣り合わせのグループを大きいグループと合併する (方法は分割統治法の同等)。 それぞれの大きいグループの場合、どの分割を合併する場合にグループ全体の道が一番短くなるかを検討、記録する。 課題も分割統治法と同じ。