手に負えない問題 (10 点)

問題は難しさによって、手に負える問題と手に負えない問題に分けられる。分ける基準と基準の理由三つを説明しなさい。

手に負える問題の基準 (2 点)

問題を解くには多項式時間しかかからない (例: O(n), O(n³) など)

手に負えない問題の基準 (2 点)

問題には指数的時間がかかる (例: O(2ⁿ), O(n!) など)

手に負える問題の基準の理由三つ (6 点)

1. 指数が大きい (例: O(n¹⁰⁰)) 問題はほとんどない
2. 多項式時間のアルゴリズムの組み合わせも多項式時間になる
3. 多項式時間の中の分岐点は決めにくい

用語の説明 (16 点)

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

preorder

行きがけ順、(二分) 木の辿り方で、親を全ての子の前に処理する

abstract datatype

抽象データ型； データ上の操作だけが定義; 実装はいろいろ

magnetic tape

磁気テープ; 昔よく使われた外部大量記憶装置の一つ

radix sort

基数整列; 小さい桁から桁ごとにソートする

cryptographic hash function

暗号技術的ハッシュ関数; 電子著名などに使う強いハッシュ関数

optimal substructure

部分構造の最適性; 問題の部分の解が全体の解の一部になる問題の特徴

traveling salesman problem

巡回セールスマン問題； お互いの距離が決まった町を最速で回る問題

simulated annealing

焼き鈍し法; 「温度を下げる」ふりをする一般的な最適近似法

アルゴリズムの表現 (8 点)

アルゴリズムの表現に Ruby を使う利点と問題点をそれぞれ複数説明しなさい。

利点: プログラム言語をアルゴリズムの表現が正確かつ実現可能。Ruby 特有の利点として、単純な記法 (例: 変数の宣言や括弧が不要) などがあるので、Ruby が「動く疑似コードともいわれる。
問題点: 場合によって必要以上に細かい、Ruby を知らない人には最初読みにくい、プログラミングができない人には分からない

ヒープソートの疑似コード (16 点)

ヒープソートのアルゴリズムを疑似コードで書きなさい。(heapify_up と heapify_down は前提としてよい)

algorithm heapsort
  input: array a[] of length len (a[1]...a[len])
  output: array a[], sorted with lowest-priority element first
  
  for i from len/2 downto 1 do
    heapify_down(i)
  end for
  
  for i from len downto 2 do
    temp ← a[1]
    a[1] ← a[len]
    a[len] ← temp
    len ← len-1
    heapify_down(i)
  end for
  
  return a
end

赤黒木の普遍条件 (12 点)

二分木と探索木を含め、赤黒木の普遍条件を列挙しなさい。

• 二分木の普遍条件は、各内部節に子がちょうど二つ
• 探索木の普遍条件は、各節にあるデータ項目のキーとデータが保持され、木を通りがけ順で辿るとキーが昇順になる
• 赤黒木の普遍条件は、各辺が黒か赤で、根から葉に行くときに赤が連続しないし、黒の辺だけ数えると木の高さが一定

行列の乗算の順番の最適化 (合計 10 点)

四つの行列の連鎖乗算 ₀M₁ · ₁M₂ · ₂M₃ · ₃M₄ の順番を決め、その場合のスケーラ乗算の数を求めなさい。

乗算の順番 (括弧で指定、4 点): (₀M₁ · (₁M₂ · ₂M₃)) · ₃M₄

最少のスケーラ乗算の数 (6 点): 4300
(₀M₁ · ₁M₂ は乗算 1800； ₁M₂ · ₂M₃ は乗算 180； ₂M₃ · ₃M₄ は乗算 6000；
₀M₁ · ₁M₂ · ₂M₃ は最善で ₀M₁ · (₁M₂ · ₂M₃) で 300;
₁M₂ · ₂M₃ · ₃M₄ は最善で (₁M₂ · ₂M₃) · ₃M₄ で 780)

文字列照合アルゴリズムの選択 (合計 24 点)

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

扱う文字列が短くて、数が少ないが、急いで実装したいので、できるだけ早く作れるものが欲しい (8 点):

単純な実装にします。文字列の書く文字から、パターンがそこに
合っているかどうか順番にチェックします。文字列の長さ n で、パターンの長さ m だと
計算量は最悪で O(mn)。しかし実装が非常に単純ですぐ出来上がり、
バグの可能性が少なくない。
本格的なところに使われないように注意しないといけない。

ライブラリに組み込むためあらゆる条件下でも最善で本格的な実装が欲しい (8 点):

Boyer-Moore のアルゴリズムを選びます。
パターンの後ろから文字を照合し、「合わない」ということだけではなくて、
文字列の中で合わない文字によって、一気にパーターンを何文字も進む可能性がある
計算量は最悪で O(n) だが、多くの場合、O(n/m) で、パターンが長いほど早い
細かいところが多いので念入りにテストしないといけないです。

特殊装置用で、文書の中で一文字ずつしか見えなくて、後戻りができない (8 点):

Knuth-Morris-Pratt のアルゴリズムを選びます。
他のアルゴリズムは後戻りもあるのに、必ず文字列の中で進むか、パターンをすらすので
計算量は O(n) になる。パターンをパターンと比較して、最善のすらし方を
事前に計算して準備しないといけない。
細かいところが多いので念入りにテストしないといけないです。

計算量の比較 (12 点)

次の表を埋めなさい。O(g(n)) が記入されてない場合、一番小さく簡単なものを記入しなさい。

番号	f(n)	O(g(n))	n0	c
例	2.2n2	O(n2)	0	2.2
	log4n+log16n	O(log2n)	1	3/4
	5n	O(n !)	5	625/24
	1010	O(1)	0	1010
	7n1.5 · 20n2.5	O(n4)	0	140
	2 log2 log2 n	O(log2 n)	16	1

ランダム化アルゴリズム (12 点)

出力が一意に決まっているのにアルゴリズムの一部として乱数を使うランダム化アルゴリズムが存在する。 ランダム化アルゴリズムの一例を選んで、アルゴリズムそのものと乱数の役割を説明しなさい。

選んだアルゴリズムはクイックソート。クイックソートではソートする項目の中から一つ選んで (これをピボットという)、 それより小さいものを左側、大きいものを右側に入れ替える。左側と右側を再帰的にソートすると全体がソートされる。 クイックソートは平均で O(n log n) ですが、ピボットの選び方に非常に弱い。ソート済みのデータで最初の項目をピボットに選ぶなどで O(n² になる。そこで乱数を使うとどのデータの場合でも時間を O(n log n) におさえることが可能。

O(n²) の整列法の比較 (10 点)

授業で扱った三つの O(n²) の整列法の実行の速さを比較し、原因を説明しなさい。

バブルソート、挿入ソート、選択ソートがある。一般には選択ソートが一番早いくて、バブルソートが 一番遅い。なぜなら、バブルソートは隣り合っている項目は何回も (O(n²) 程度) 入れ替える。 挿入ソートは挿入の空きを作るため、項目を何回も (O(n²) 程度) すらすが、入れ替えよりすらすだけのほうが早い。 選択ソートは入れ替えを O(n) 回しかしないので一般には一番早い。しかし、挿入ソートは項目がほとんどソートされているときに 他の整列法 (O(n log n) のものも含む) より早いことがある。

2-3-4 木の容量 (合計 14 点)

高さ n の 2-3-4 木の最少と最多の節の数を計算し、説明しなさい。

次の表を埋めなさい。(5 点)

n	最多の節の数	最少の節の数
1	1	1
2	5	3
3	21	7
4	85	15
5	341	31
6	1365	63

最少の節の数の式 (3 点)

最少の場合、各内部説に二つの子がある。層ごとの個の数が二倍。高さ 1 (根だけ) の場合、節の数が 1. n の場合は Σⁿ_i=12^i-1=2ⁿ-1。

最多の節の数の式 (6 点)

最多の場合、各内部説に四つの子がある。層ごとの個の数が四倍。高さ 1 (根だけ) の場合、節の数が 1. n の場合は A=Σⁿ_i=14^i-1。4A = Σⁿ_i=14ⁱ。 3A = Σⁿ_i=14ⁱ - Σⁿ_i=14^i-1 = 4ⁿ - 1。 よって、A = (4ⁿ-1) / 3。

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

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

注： この問題の目的は正しいアルゴリズムの発見ではなく、設計方針の知識の応用である。正しいアルゴリズムがない場合もある。

問題: n 個の用事 y₁,..., y_n のできるだけ数多くを m 個の部屋 (m≦n) で行うように計画を頼まれている。用事 y_i には開始時間 s_i と終了時間 e_i がある。ある部屋では同時に一つの用事しか行えないが、ある用事の開始時間は直前の用事の終了時間と同じでよい。

分割統治法 (6 点)

部屋の数と用事の数をできるだけ半々に分け、分けた分に再帰的にアルゴリズムを適用する。部屋の数が 1 の場合、用事をある時点で半々に分け、それを用事が 1 になるまでに繰り返す。用事が時間帯に入れば行い、そうでなかったら取りやめる。半々に分けるのは log n 回程度なので、計算量は O(n log n) と考えられる。問題点は、例えば時間的な分割点をまたぐ用事が可能でも取りやめられる。

遺伝的アルゴリズム (6 点)

簡単な方法を使って、複数の解を作る。解を「世代」ごとに組み合わせて (例えば解 1 から部屋 A の予定、解 2 から部屋 B の予定) 交叉し、「突然変異」で予定されてない用事と予定されている用事を入れ替えるなどする。 今まで最適でした解は必ず取っておくが、その他の解は悪いほど消す確率を高く設定する。 統計的なやり方なので、どこまで計算させるのは人間が決めるべきだが、他の方法より遅くなるのは確実。 問題点は、最適解を見つける保証はない。

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

用事を何かの基準でソートして、その順に部屋に割り当てる。割り当てが不可能な用事は行わないことにする。 ソートの基準としては短い方から、開始点が早い方から、他に重なる用事が少ない方から、終了点が早い方からのがあるが、最後のほうがよさそう。 計算量は順番でやるだけなので、O(n)。 問題点は、いったん決まったところは再検討ができないため、最適解が見つからない可能性がある。

総当たり法 (6 点)

各用事を各部屋に行うか、行わないかの組み合わせを全部試す。矛盾のある組み合わせを捨てて、残るものから最適解を選ぶ。 用事毎に m+1 の選択肢があるので、計算量は O(n^m+1)。問題点は、時間がかかりすぎる可能性がある。