スタックの定義 (12 点)

スタックという抽象データ型には new, empty?, size, push, pop と top の操作がある。 その操作の間の、スタックを公理的に定義する六つの公理を書いて、簡単に説明しなさい。

• Stack.new.empty? ↔ true (新規のスタックは空である)
• s.push(e).empty? ↔ false (何か乗せたスタックは空ではない)
• Stack.new.size ↔ 0 (新規のスタックの大きさは 0 である)
• s.push(e).size ↔ s.size + 1 (スタックに何か乗せると大きさが一つ増える)
• s.push(e).top ↔ e (項目をスタックにのせるとそのすぐ後に top で返される)
• s.push(e).pop ↔ s (項目をのせた後にポップすると元の状態に窓路)

トップダウン 2-3-4 木の作成 (10 点)

トップダウン 2-3-4 木を作成しなさい。入力項目を一つ一つ挿入するごとにその途中経過を書きなさい。 入力項目とその順番: A, O, Y, M, G, K.

用語の説明 (16 点)

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

linked list

連結リスト、データ項目が参照 (ポインター) で連結されたデータ構造

exponential time

指数時間、データ項目の指数関数 (例: 2ⁿ) のように増加する事項時間

amortized analysis

償却分析、データ構造をたまに時間をかけて大幅に作り直す場合の計算量の分析

average running time

平均の計算量、色々な入力を考慮して平均にかかる計算量

postorder

帰りがけ順、(二分) 木の辿り方で、親を全てのこの後に処理する

secondary storage

二次記憶装置、ハードディスクなど、遅いのでアルゴリズムの選定で考慮が必要

open addressing

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

greedy algorithm

貪欲アルゴリズム、部分的な選択で最適な解をえられようとするアルゴリズム

二分探索の疑似コード (15 点)

ニ分探索のアルゴリズムを疑似コードで書きなさい。

algorithm binary_search
  input: array a[] of length l (a[0]...a[l-1]), key k
  output: index of key in a, or not_found if not found
  low ← 0
  high ← l
  repeat while low < heigh
    middle ← (low+heigh)/2
    if a[middle] = k
      return middle
    else if a[middle] < k
      low ← middle
    else
      high ← middle
    end
  end
  return not_found
end

ヒープの普遍条件 (12 点)

ヒープの普遍条件を列挙しなさい。

• 二分木である (それぞれのノードには高々ニこの子がある)
• 完全二分木である (最低の層以外に層が全て一杯、最低の層では左よりの場所が埋まっている)
• 子供より親が必ず優先 (小さい方が優先でしたら親の方が小さい)

ヒープの普遍条件を修復するアルゴリズムは条件によって二つある。そのうちの一つを選んで説明しなさい。

現所と親を比べて順番が合わない場合に使う heapify_up では現所と親を入れ替え、親を現所にし、新現所と親を比べて順番が合うまで繰り返す。

文字列照合のアルゴリズム (12 点)

授業で説明した四つの文字列照合アルゴリズムを計算量を中心に比較しなさい。

文字列照合アルゴリズムの計算量は文書の長さ n と探しているパターンの長さ m に関係する。m より n がはるかに大きい想定で説明する。

• 素朴な実装は多くな場合に O(n) に近いが、最悪の場合 (例えば a....ab の中に a..ab を探すとき) には O(m*n) になる。
• Rabin-Karp のアルゴリズムは次々のハッシュ関数の計算が早く、O(n) である。
• Knuth-Morris-Pratt のアルゴリズムは後戻りがないため、O(n) である。
• Boyer-Moore のアルゴリズムはパターンの後ろから照合を試しているので、多くの場合 0(n/m) である。

辞書のためのデータ構造の選択 (合計 24 点)

下記の三つの事情に合わせて、辞書 (抽象データ構造) のためのデータ構造を実装するように頼まれた。 データ構造を選んで、そのデータ構造の名前、仕組み、選んだ理由と実装の場合特に注意すべき点を記述しなさい。

扱うデータ項目の数が少ないが、急いで実装したいので、できるだけ早く作れるものが欲しい (8 点):

 
 
 
 

ライブラリに組み込むために本格的な実装が欲しい (8 点):

 
 
 
 

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

 
 
 
 

計算量の比較 (10 点)

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

O(n log n), O(10¹⁰), O(2ⁿ), O(n!), O(n), O(log₂ n), O(nⁿ), O(log_n n), O(log₇ n), O(n²), O(n^0.1),
O(n log log n), O(n^0.5), O(10¹⁰n), O(n³)

O(10¹⁰) = O(log_n n) < O(log₂ n) = O(log₇ n) < O(n^0.1) < O(n^0.5) < O(n) = O(10¹⁰n) < O(n log log n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

挿入整列法と選択整列法 (16 点)

挿入整列法と選択整列法は似たような点が多いが違う。 元のデータがばらばらであったという前提のもとで、整列全体にかかる時間のちょうど半分の時点を考える。 その時点でそれぞれのアルゴリズムについて、データ全体のどのぐらいの部分がどのように整列されているかとその理由を文章と図両方を使って説明しなさい。

挿入整列法: 整列されてない部分から項目を選んで、整列された部分に挿入するので、 整列された部分が大きくなるにつれ作業が遅くなる。したがって半分の時間ではデータの 1/√2 分までに既に整列されているが、 その整列は完璧なものではなく、そこにまだ整列されてない項目が更に導入される可能性もある。

  [図欠落]
  
  
  

選択整列法: 整列されてない部分から一番小さいものを選ぶ。その部分はどんどん小さくなるので、 最初はあまり進まない。半分の時間ではデータの 1-1/√2 分のところまでしか進まない。しかしその部分が完全し整列され、 残りのものは全てそれより大きいものばかりしか残ってない。

  [図欠落]
  
  
  

3-SAT 問題と帰着 (12 点)

NP 完全問題は全てお互いに帰着できる。次の 3-SAT 問題を独立集合問題に帰着しなさい。

(￢x ∨ ￢y ∨ z) ∧ (x ∨ ￢y ∨ ￢z) ∧ (￢x ∨ y ∨ z)

3-SAT 問題の難しさについて三つの場合に分けて簡単に説明しなさい。

1. 変数の数が項の数に比べて多い場合、解ける可能性が高いので、解けそうな可能性を優先したアルゴリズムで解けてみた方がよい。
2. 変数の数が項の数に比べて少ない場合、解がない可能性が高い。解けない部分問題を早く見つけそうなアルゴリズムを使った方がよい。
3. 変数の数に比べ項の数が中ぐらいの場合、3-SAT 問題が本当に難しい。