文書によるアルゴリズムの表現 (8 点)

文書によるアルゴリズムの表現方法の利点と欠点を細かく述べなさい。

利点: 文書なので情報テクノロジーの専門家だけではなく、一般の人にも分かりやすい可能性がある。 形式が決まってないので自由に書けるし、電子メールなどで簡単に交換もできる。

欠点: 自然言語の文書には多くの場合、曖昧さが付きます。曖昧さのない文書が非常に書きにくくて、不自然と感じる。 そのため、正確な表現に限界があります。アルゴリズムは多くの場合、構造 (例えば for ループなど) があるが、文書が流れるだけなので、構造が分かりにくいです。 さらに、文書は自然言語で書きますが、自然言語は多くの種類 (例： 日本語、英語) があるので、その自然言語がわからないとアルゴリズムもわからない。

計算量 (15 点)

下記左側にある C 言語のプログラム断片 (変数の定義など省略) について、それぞれの計算量とその理由を右側に書きなさい。

for (i=0; i<n; i++)
    for (j=0; j<i; j++)
        total += items[i] / items[j];

二重ループで、j は最初狭い範囲でしか動かないが、合計の割り算と足し算は n*n/2 回ぐらいあるので、O(n²)

---

int fun(n) {
    if (n<2)  total++;
    else for (i=0; i<n; i++) fun(n-1);
}

n が2以上の時にn 回繰り返して、さらに n-1 で自分を呼ぶので、n*(n-1)*... で O(n!)

---

a = b + q;
b = 20 + a;
q = 4 * b;

足し算二つ、掛算ひとつ、代入三つしかしないので、一定時間に終わるので、O(1)

---

total = 0;
while ((n/=2) >= 1)
    total += 1;

while ループを一回回ると n が半分に減って、さらにループごとの計算量が一定なので、O(log n)

---

for (w=2; w<=n; w++)
    for (i=0; i<n-w; i++)
        for (c=i; c<i+w; c++)
            total += items[c];

三つのループで、w が小さい時と大きい時には内部の二つのループは O(n) に近いが、w が中間の時に O(n²) なので、全体には O(n³)。(構造的には配列の連鎖乗算の動的計画法と同じ)

クイックソートの疑似コード (16 点)

ある配列 array の指数 left から right までの範囲をソートする単純なクイックソートのアルゴリズムを疑似コードで書きなさい。

algorithm simple_quicksort
  inputs: array of items (array),
          index of leftmost item (left),
          index of rightmost item (right)
  output: sorted array
  
  return if left ≥ right
  pivot ← a[right]
  r ← right-1
  l ← left
  loop
    while r>1 and array[r]>pivot do
      r ← r-1
    end
    while array[l]<pivot do
      l ← l+1
    end
    break if l>r
    array[l], array[r] ← array[r], array[l]
  end
  array[l], array[right] ← array[right], array[l]
  simple_quicksort(array, left, l-1)
  simple_quicksort(array, l+1, right)
end

用語の説明 (20 点)

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

tractable problem

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

open addressing

開番地法、ハッシュ表で激突が生じるときにもう一回ハッシュ関数を使う方法

memoization

履歴管理; 関数の計算結果を例えばハッシュに登録し、動的計画法の自動化に使える技

preorder

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

independent set

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

amortized analysis

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

dictionary

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

reduction

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

sentinel

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

decision problem

決定問題; 解とが「はい」か「いえ」だけの問題; 他の問題は決定問題に置き換え可能

キュー (待ち行列) を実装するためのデータ構造の選択 (15 点)

下記の三つの事情に合わせて、キューを実装するように頼まれた。 データ構造を選んで、そのデータ構造の名前、仕組みと選んだ理由を記述しなさい。

同時にキューに入っている項目の最大の数はある一定の数より大きくはならない。 追加は時間が少しでもかかると困るが、取り出しは少しでけ時間がかかってもよい:

配列を使う。配列の大きさを最大の項目の数に合わせる。 配列の先頭から出すので、後の項目をすらすのは O(n) の時間がかかるが、項目の追加は後ろの方にやるので、 一定時間で可能。
 

同時にキューに入っている項目の数の制限がないが、出すのも入れるのも素早く行って欲しい:

線形リストを使う。最初の項目と最後の項目へのポインタを持っていれば、前からの削除も後への追加も一定時間 (O(1)) で可能。 線形リストだと長さの制限もない。
 
 

普通のキューのではなく、項目に優先度が付いた順位キューが必要。項目の最大の数が限定されている:

ヒープを使います。ヒープは配列の中に二分木を埋め、k 番目の要素の子供は 2k と 2k+1 番目の場所にある。 親は常に子より優先だが、この間の順番は決まってないので、項目の追加、削除、優先度の変更も全て O(log n) で可能。
 

2-3-4 木と赤黒木 (12 点)

赤黒木は 2-3-4 木の「実装」といえる。子供が二個、三個、四個の 2-3-4 木の節とそれぞれに相当する赤黒木の部分を図で示しながら 2-3-4 木を赤黒木でどうやって実装するかを説明しなさい。普遍条件にも言及しなさい。

[図省略]
両方の木の普遍条件はまず探索木の普遍条件である。内部節のキーより小さいキーのデータ項目は左、キーが大きいデータ項目が右になります。
2-3-4 木の普遍条件は内部節の子供は二つから四つの間で、木の高さが一定であること。それに対し、赤黒木が二分木ですべての内部節の二つの子供がある。
赤黒木の場合、元の 2-3-4 木の辺が黒で、3個や4個の子供の節を二分木の赤黒木に変換する (図参照、3個の子供の時に、変換は二種類ある) ときにできる 辺は赤になる。2-3-4 木の一定の高さを保つために、赤黒木の場合、根から葉までの黒の辺を一定に保つ、かつ赤の辺を二つ連続にしないことが普遍条件になる。

ソートのアルゴリズムの説明 (20 点)

下記の左側にある図はソートのアルゴリズムの可視化の実行中に撮ったものである。図ごとにソートのアルゴリズムの名前、図にみられるアルゴリズムの特徴 (なぜそのアルゴリズムなのかの理由) を述べ、計算量などを含めアルゴリズムを説明しなさい。

ヒープソート。なぜかというと、ヒープソートは配列を使ってヒープ (優先順位キュー) を作成し、 一番「優先が高い」(大きい) ものを順次ヒープの根から取り出し、ヒープを小さくしながら取り出したものをヒープの後ろに回している。 図のところには完全に整列されている右側 (配列の後ろ) の12個ほどの要素、左側にヒープがみられる。 ヒープの根は一番左側で次に右に移動されるものが整列されてないもののなかの一番おおきもので、ヒープの右側の方は、 ヒープの特徴のせいで完全ではないが徐々に小さくなる傾向が見られる。計算量が O(n log n)。

---

挿入ソート。 左の部分ではその中が整列済みですが、まだまだ右側の方から左側の部分に挿入する要素が一杯残っている。 挿入ソートは整列済みの部分のすぐ右の要素を、適切な場所が見つかるまでに整列済みの要素を右から一つずつ左にすらしながら挿入するアルゴリズム。 計算量は O(n²) だが、既に殆ど整列されているデータの場合に非常に有効である。

---

選択ソート。左側に全く変更が必要なくてすでに完璧にソート済みの領域ができて、 右側に左側の領域の一番大きい要素より大きいものしか残らない。そこから選択ソートが次々と残りの一番小さい要素を選んで、 整列済みの領域のすぐ右にある要素と交換し、左側の領域を大きくする。計算量が O((n²) で、 他の同じ計算量のバブルソートや挿入ソートよりデータの移動が少ないので、特に一項目あたりのデータの量が大きい時に有利。

---

一番速い文字列照合のアルゴリズム (8 点)

授業で習った文字列照合アルゴリズムのうち、一番速いものを選んで、その速さの理由を中心に説明しなさい。

一番早い文字列照合アルゴリズムは Boyer-Moore アルゴリズムです。なぜかというと、一般の場合、計算量は O(n/m) である。この場合、n は文書の長さで、m は探しているパターンのながさ。Boyer-Moore アルゴリズムの決めては、パターンとの照合を前からのではなく、後ろから行うということです。 パーターンの一番後ろの文字が「合うか合わないか」だけでわなく、合わなかったら文書の文字はどの文字なのかも考慮する。 その文字がパターンのの中に全くない場合、パターン一個分にパターンをすらすことができるので、一番最前の場合、 一個の比較で m 文字進むので、O(n/m) になる。

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

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

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

問題: n 個の品 s₁, ..., s_n があって、 品 s_k の重さが w_k で、その値段が p_k の場合、最大の重さが w_t のナップサックにできるだけ品の合計の値段が高くなるように、どの品を詰めるかを求める。

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

品を「効率」のよい順番に並んで、一番効率のいいものから詰めてみて、 詰められないものを飛ばし、できるだけ一杯になるまで詰めてみる。 ここで品 s_k の「効率」は重さに対する価値、すなわち p_k/w_k にする。 計算量は,品順列が必要なため、O(n log n)。「効率」の順でやっているので結構いいところまで行くと期待されるが、 空きを残して最善解まで行かない可能性もあるのが問題点。

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

最初は乱数を使って一定の数の解を作る。繰り返し各解から複数の新しい解を作って、 今まで見つけた一番いい解を複数残す。新しい解を作るときに、複数の品を乱数で決め、入れ替える (突然変異)。 それによって幅広く解を試し、良い組み合わせをさらに組み合わせる。 計算量は O(n∙繰り返しの数∙作成する解の数)。組み換えなどにより最大の重さを簡単に超えられるのが一つの問題点。

分割統治法 (6 点)

品を二分に分け、それを再帰的に適用する。 部分の重さを計算し、ナップサックの最大の重さまで足し合わせる。それを超えたら、価値の高い方の部分だけを残す。 分割の回数が O(log n) のため、計算量が O(n log n)。 二つの部分の一つを残す可能性が多いので、荒すぎてあまりいい解が出ない可能性が高いのが問題。 検討した価値があるが、この問題に全く向いてないみたい。

総当たり法 (6 点)

s₁ から始まって、 すべての品について「入れる」と「入れない」の両方の選択肢を試す。 一番簡単な実装は再帰です。計算量は解の数の O(2ⁿ)。 全ての解をチェックするので、最適解を見つける保証がある。 計算量は指数的なので非常に遅いのが問題。 早く打ちきれるように少しでも早くする工夫が大事。 例えば今まで見つかった最大解の合計の値段と残りの品をすべて詰められる場合の最大の値段を考慮して打ち切るとか。