ヒープと二分探索木の比較 (30 点)

ヒープと二分探索木は両方とも二分木で、各節にキーを含むデータ項目を格納するデータ構造である。

全ての二分木に共通の「ルール」を書きなさい。(5 点)

二分木は、各親に最大二個の子しかない木であり、 木はルートと呼ばれる節以外各節が一つの親と呼ばれる節に辺で結ばれていて、親から見て結ばれる節を子という、グラフである。

木の形を制限する「ルール」をそれぞれ書きなさい。(5 点)

ヒープ: 完全に分木である、すなわち最低の層以外は全層が埋まっていて、最後の層の節は左に寄り、子が1個しかない節は最大一つ。

二分探索木: 特になし
 

それぞれの応用例を書きなさい。(4 点)

ヒープ: 優先順位キュー、ヒープソート

二分探索木: 辞書という抽象データ型

キーによるデータ項目の配置についての「ルール」をそれぞれ書きなさい。(5 点)

ヒープ: 親より子 (のキー) の優先度が低い

二分探索木: 親より左の部分木のキーが低くて、右の部分木のキーが高い

この問題で「ルール」と書いてあるものの正式な専門用語を書きなさい。(2 点) 不変条件

それぞれの木の平衡を保つための対策を説明しなさい。 (6 点)

ヒープ: 完全二分木である以上、
平衡である。

二分探索木: 赤黒木や AVL 木のように、追加の条件が必要。例えば赤黒木では辺を赤と黒に染め、ルートから葉までで連続に赤の変を禁止する。

両方のデータ構造の「ルール」を同時に守った木を描きなさい。各節のキーには、お互いに異なる、できるだけ小さい自然数を使いなさい。(3 点)

  0 (小さい値の方の優先度が高い前提の場合)
 /
1

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

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

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

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

扱う文字列は短く、文字数も少ないが、急いで実装したいので、できるだけすぐに作れるものが欲しい:

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

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

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

授業へのコメント / Comment about Course (9 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)
What was most difficult to understand in this course? (there is no definite answer)

@@@@
@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)
What topic in this course was most interesting for you? (there is no definite answer)

@@@@
@@@@

一回目の授業では参考書の購入 (又は貸出) と熟読が強く薦められました。熟読した参考書の詳細を書きなさい。参考書を読まなかった場合、その理由を書きなさい。

石畑清著、アルゴリズムとデータ構造、
岩波講座ソフトウェア化学、岩波書店

用語の説明 / Explanation of Terms (40 点)

次の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。部分問題 1.11 以降は説明を長くしなさい。
For each of the English terms below, write the corresponding Japanese term and give a short explanation. For the Japanese terms, avoid Katakana as much as possible. For subproblem 1.11 and later, give a longer explanation.

linked list

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

radix sort

基数整列; 小さい桁から桁ごとにソートする, O(n log n) より速い

recurrence relation

@@@

universal hash function

万能ハッシュ関数; 攻撃を防ぐために、プログラムの実行ごと結果が違うハッシュ関数

sentinel

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

memoization

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

genetic algorithm

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

secondary storage

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

postorder

帰りがけ順、全ての子の後に親を処理する木の辿り方で

local optimum

局所的な最適解; 山登り法という近似アルゴリズムの場合発生する問題

optimal substructure

部分構造の最適性; 問題の部分の解が全体の解の一部になる問題の特徴
部分構造の最適性によって、分割統治法、貪欲法、動的計画法だ設計方針として最適

polynomial time

多項式時間; 計算量が多項式で表せるということ。多項式時間の問題は
「手に負える」という。対して、指数的時間の問題は「手に負えない」という。

recurrence relation

漸化式; 再帰的に定義されている数学的な関数、解けにくい場合がある
@@@

open addressing

開番地法、ハッシュ表で激突が生じるときにもう一回ハッシュ関数を使う方法。 占有率は 0.5 以下にしないと、効率が低い。削除のために特別な対策が必要。

independent set

独立集合; NP 完全問題で、グラフのつながってない最多の頂点を取り出す問題
3-SAT 問題は独立集合問題に帰着可能

アルゴリズムの設計方針 / Algorith Design Strategies (25 点)

下記の「ポストの対応問題」の課題のため、下記の最初の四つの部分問題のアルゴリズムの設計方針や原理を使った際の、 それぞれのアルゴリズムの概略を提案しなさい。また、それぞれに対し、予想される計算量とその根拠、設計方針を使った場合の問題点について述べなさい。
For the problem explained below, in the first four subproblems propose ideas for algorithms using the respective algorithm design strategies. In each case, indicate the expected time complexity and the reason for it, and the problems when using this design strategy.

注： この問題の目的は、最適な結果をもたらすアルゴリズムの発見よりも、設計方針の知識の応用である。
Caution: The purpose of this problem is to show you can apply your knowledge about design strategies, rather than to design the best algorithm.

課題: ポストの対応問題では、n 個のカードの種類が与えられ、カードの表の上方と下方にそれぞれ文字列が書かれている。 目的はカードの横並びで文字列を連続に読むときに、上方全体の文字列と下方全体の文字列が同じになるようにすること。 このような並びが可能であればカードの種類の順番、不可能であればその旨を出力する。

動的計画法 / dynamic programming

@@@

貪欲アルゴリズム / greedy algorithm

@@@

分割統治法 / divide and conquer

@@@

シミュレーテッドアニーリング / simulated annealing

@@@

ゲーム会社に勤務しているとする。社長から、 「委託先から来月末までにどの入力に対しても正しい結果が出せるプログラムを出さないと契約が打ち切られる。」 と言われたときの返事の概略を書いてください。

大変申し訳ございませんが、ポストの対応問題に対し、完璧なアルゴリズムが存在しないことが証明され、広く知られています。 ポストの対応問題は、正確に定義できる問題の中で最も難しくて、ある意味で有名な難問の NP 問題よりも無限倍に難しいです。 多くの入力に対し正しい出力を出すアルゴリズムは作れるが、完璧なものは論理的に無理なので、委託先と再交渉したほうがいいです。

計算量 (15 点)

下記左側にある C 言語のプログラム断片 (変数の定義などは省略) について、それぞれの計算量とその理由を右側に書きなさい。
For each of the C fragments below to the left (without variable definitions,...), on the right write the time complexity and the reason for it.

for (i=0; i<k; i++)
    for (j=0; j<k; j++)
        sum += detail[i] * detail[j];

二重ループで、全体で 内部の掛け算と足し算が合計 k*k 回実行されるので、O(k²)

---

for (x=0; x<10; x++)
  a = x + x*x + x*x*x;

10 回繰り返されるが、10は定数なので、一定時間で終わるので、O(1)

---

int fun(n) {
    if (n<2)  return 1;
    else return fun(n-1) + fun(n-2);
}
fun(n);

これは fibonacci 関数の再帰的な計算で、fun(n) には fun(n) の計算時間がかかって、よって O(fibonacci(n))

---

for (x=1; x<=n; x++)
    for (y=1; y<x; y++)
        for (z=1; z<y; z++)
            total += items[z];

三重ループで、内部のループは外部の指数の範囲に制限され、 形は裏害されている三角錐になる。内部の計算の回数はおよそ n³/6 で、 O(n³)。

---

for (k=n; k>0; k/=3)
    total += k;

for ループを一回回ると k が三分の一に減るので、およそ log₃n 回るので、O(log n)

---

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

四つの行列の連鎖乗算 ₀M₁ · ₁M₂ · ₂M₃ · ₃M₄ を行う際、スカラ値同士の乗算の回数と、最善の計算順を求めなさい。計算の過程や途中結果も書きなさい。 行列の大きさは r₀=3, r₁=30, r₂=4, r₃=20, r₄=5 で与えられている。

₀M₁ · ₁M₂ の乗算数は 360、 ₁M₂ · ₂M₃ は 2400、 ₂M₃ · ₃M₄ は 400；
₀M₃ は ₀M₁ · ₁M₃ で乗算数が 0+2400+1800=4200 で, ₀M₂ · ₂M₃ で 360+0+240=600 なので、 後者が 600 で最善； ₁M₄ は ₁M₂ · ₂M₄ で 0+400+600=1000 で、 ₁M₃ · ₃M₄ で 2400+0+3000=5400 なので、前者が 1000 で最善。
₀M₄ は ₀M₁ · ₁M₄ で 0+1000+450=1450 で、 ₀M₂ · ₂M₄ で 360+400+60=820 で、 ₀M₃ · ₃M₄ で 600+0+300=900 で、 ₀M₂ · ₂M₄ が 820 で最善。
よって、乗算の順番は (₀M₁ · ₁M₂) · (₂M₃ · ₃M₄) で最善。

二分挿入ソート (30 点)

二分探索を使用する挿入ソートを二分挿入ソートという。二分探索を使用しない挿入ソートを単純挿入ソートともいう。

配列 data (長さ len) の中のデータ項目を単純挿入ソートで整列するアルゴリズムを疑似コードで書きなさい。 (12 点)

algorithm insertion_sort
  inputs: data (length len),
  output: data (sorted)
  
  for i from 2 to len-1 do
    move ← data[i]
    
    for k from i-1 to 1 do
      if move < data[k]
        data[k+1] ← data[k]
      else
        break
      end_if
    end_for
    
    data[k] ← move
  end_for
end

単純挿入ソートのデータ項目の移動回数と、データ項目同士の比較回数を、それぞれ O 記法で表しなさい。 2 点)

移動回数: O(n²)     比較回数: O(n²)

二分探索の使用により、挿入ソートの比較回数を減らすことが可能である。そのやり方を考え、説明しなさい。(4 点)

二分探索を、挿入する項目の場所を決めるために使う。挿入済み領域の中で、挿入する項目より大きい最初の項目を探す。 その項目を先頭にした挿入済み領域の右側の項目を全て一項目分右側に移動する。

(最悪の場合における、) 二分挿入ソートの場合、データ項目の移動回数とデータ項目同士の比較回数、 それにアルゴリズム全体の計算量をそれぞれ O 記法で表しなさい。(4 点)

移動回数: O(n²)     比較回数: O(n log n)     全体の計算量: O(n²)

最善の場合における、二分入ソートの場合、データ項目の移動回数とデータ項目同士の比較回数、 それにアルゴリズム全体の計算量をそれぞれ O 記法で表しなさい。(4 点)

移動回数: O(n)      比較回数: O(n log n)     全体の計算量: O(n log n)

データや比較関数の違いによって、単純挿入ソートよりも二分挿入ソートの実際の実行時間が短くなる可能性がある。 実際に実行時間が大幅に縮む場合の、データや比較関数の特徴を説明しなさい。(4点)

移動回数が二分挿入ソートの場合、データがすでにほぼソート済みの場合低いので、データがあまりソートされていない場合、二分挿入ソートが有利。 さらに、二分探索により、比較回数が減るので、比較関数が重いデータの場合に有利。移動回数が変わらないので、データ項目の大きさは影響なし。

O 記法の理由 / The Reason for the Big-O Notation (15 点)

O 記法は定義上いくつかの特徴をもつ。以下の特徴がなぜアルゴリズムの評価に適しているのか、それぞれ説明しなさい。
Big-O notation by definition has a number of properties. For each property, explain why it is suitable for the evaluation of algorithms.

対数の底が不要。 / The base of a logarithm is irrelevant.

これは次の特徴の「定数の倍数を無視できる」ことの結果である。対数の場合、底の変更は定数との掛け算で可能で。 例えば log_ax = log_bx * log_ab である。この場合、log_ab は定数なので、無視してもよい。

定数の倍数が無視される。 / A constant multiple is ignored.

様々な計算機の実行速度のさにより、プログラム言語や実装によっても速度の差が出るし、 最近は並列化も注目されているが、それによって一定の倍数の差が出るが、それ以上の差が出ません。 アルゴリズムの評価では実装の詳細のではなく、アルゴリズム (すなわちアイディア) そのものを評価したいので、定数の倍数を無視した方がいい。

一定数までの差が無視される。 / Difference up to a constant is ignored.

一定の差 (例えば数ミリ秒や数秒) は初期化や準備の実装の差などで出る可能性があるが、 データの項目数が増えると全体の実行時間がどんどん伸びるので、一定時間の差はアルゴリズムの比較に必要な根本的な差のではなく、 実装の詳細による差に過ぎないので、無視した方がいいです。

アルゴリズムの表現方法 / Expression of Algorithms (12 点)

プログラミング言語 Ruby をアルゴリズムの表現に使う授業がある。Ruby を教材に選ぶことによる様々な利点と問題点を説明しなさい。 / There are courses that use the programming language Ruby to express algorithms. Explain the various advantages and problems of using Ruby.

利点 / advantages: Ruby の文法が単純で (例: 行末のセミコロンが不要)、多くの部分 (例: 演算子) が他のプログラム言語と似ていて、 変数の宣言が不要で、データ構造 (例: 配列) とデータ型 (例： 整数) の組み合わせも 自由で、高度なメソッド (例: each) があるので、アルゴリズムの概念に近い記述が可能なので、実行可能な疑似コードとも言われている。。

問題点 / problems:プログラミング言語一般の問題であるが、 Ruby の場合でも一部、アルゴリズムのアイディアに必要ない細かい記述が必要。さらに、C や Java に比べて、 あらかじめ知っている学生が少ない。さらに、一部のメソッド (例： shift) は一定時間 (O(1)) で実行されるように見えるが、 実はそうでもないので、注意が必要。