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

次の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。
ただし、部分問題 11 以降は詳細に説明しなさい。

postorder

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

sentinel

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

asymptotic lower bound

漸近的下界; 最低でもこのぐらい増えること、アルゴリズムより問題の場合に多く使用

universal hash function

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

tractable problem

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

simulated annealing

焼き鈍し法; 解を乱数の変化で、「温度」を提げながら見つける近似アルゴリズム

brute force algorithm

総当たりアルゴリズム; 効率的なアルゴリズムとの比較に使われる単純なもの

radix sort

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

cryptographic hash function

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

decision tree

決定木; 問題の解決に必要な決定の構造を表す木

recurrence relation (4 点)

漸化式; 再帰的に定義されている数学的な関数、解けにくい場合がある
解き方の一つとしては繰り返しの展開によるパターンの発見が多い

traveling salesman problem (4 点)

巡回セールスマン問題; 配達などの最短 (最速、最安) ルートを認める問題
実用性が非常に高いだが、判定問題 (ある距離など以下が可能か） は NP 完全問題

optimal substructure (4 点)

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

memoization (4 点)

履歴管理; 関数の計算結果を例えばハッシュに登録し、再計算をしないで効率を上げる
純粋な関数 (引数にしか依存しない関数) が前提。動的計画法の自動化に使える技

reduction (4 点)

帰着; ある問題を別の問題に置き換えて解くことで問題の相対的な難しさを示す方法。
NP 完全問題は全部お互いに帰着可能なため、全部NP 困難問題のなかで一番難しいと分かる

ヒープ (39 点)

ヒープの主な用途を二つ書きなさい。 (4 点)

1. 優先順位キューという中小データ型の実装
2. ヒープソートの実装

ヒープの普遍条件を三つ説明しなさい。(9 点)

1. 二分木である (それぞれのノードには高々ニ個の子がある)
2. 完全二分木である (最低の層以外に層が全て一杯、最低の層では左よりの場所が埋まっている)
3. 子より親が優先度が高い (か同じ) (大きい方が優先でしたら親の方が大きいか同じ)

ヒープはよく配列で実装される。その場合、次の文が正しくなるように空欄を埋めなさい。(6 点)

合計の項目数が n のヒープで、あるデータ項目が配列の k 番目の場所にある場合、その親は k / 2     番目の場所で、
左の子が k*2       番目の場所で、右の子が k*2 + 1  番目の場所になる。 0          番目の場所は使用されない。
ヒープの普遍条件の修復には heapify_up 関数と heapify_down  関数が使われます。
両方の関数の計算量は一般的に O(log n)           である。

ヒープの普遍条件を修復するために、heapify_up 関数と heapify_down 関数が使われます。heapify_up の
疑似コードを書きなさい。ヒント: 前の部分問題 (穴埋め) が分からない場合、parent などの関数で表すとよい。 (12 点)

algorithm heapify_up (前提: 大きい方が優先度が高い)
  inputs: heap (as an array, length len)
          position p (of element to push down)
  output: heap (with position of data at original position p fixed)
  
  while true
    break_while if p = root
    parent_p = parent(p)

    if heap[p] > heap[parent_p] then
      heap[p], heap[parent_p] = heap[parent_p], heap[p]
      p = parent_p
    else
      break_while
    end
  end_while
end

heapify_up 関数などの一般的な計算量にもかかわらず、n 個のデータ項目から一気にヒープを作るときの計算量が O(n) で
可能ということが知られている。その理由を詳しく説明しなさい。(8 点)

ヒープの作成は、データを配列にいれ、そこから木下の項目からスタートして各項目で heapify_down を使って親子の順番を優先度に合わせる。n この項目に O(log n) の heapify_down を適応すると、一般には O(n log n) になるが、一番下の層では heapify_down は使わなくてもいいし、その次の層では O(1), その上の層では O(2),... と項目ごとに時間がかかる。逆に一番下の層の項目数は全体の半分で n/2 で、その次の層ではさらに半分の n/4 です。 そのため、全体の計算量は 0*n/2 + 1*n/4 + 2*n/8 + 3*n/16 + ... と表せる。これを総和として解くにはテイラー展開が必要ですが、結果は O(n) になる。

ハッシュ表 (37 点)

ハッシュ表の主な用途を書きなさい。 (2 点)

辞書という抽象データ型の実装

ハッシュ表の全ての実装に共通の仕組みを説明しなさい。(5 点)

データ項目の場所は、キーから計算されるハッシュ関数の結果で決まる。 ハッシュ関数はキーをできるだけバラバラに分散させるように設計されるが、ダブっている場合、激突が起き、その対応にはさまざまな種類がある。

ハッシュ表では実装上で激突が大きな課題となる。激突対策を一つ選んで、細かく説明しなさい。(6 点)

開番地法を選びます： データ項目をキーから計算したハッシュ関数を使って、大きな配列に収める。 激突の場合、再度別の結果をだすハッシュ関数 (簡単な場合、元のハッシュ関数+1) を使い、これを空いている場所が見つけるまで繰り返す。削除した場合は特別なキーを使う必要がある。占有率 α は <=0.5 がいい。

ハッシュ表と同じ用途で使える実用的なデータ構造を、 内部メモリ用・外部メモリ用に分けて合計5つの
名前と簡単な説明を書きなさい。 (10 点)

内部メモリ用

1. 2-3-4 木、探索木で、木の高さが一定で、内部節の子の数が2個から4個
2. 赤黒着、2-3-4 木を二分木に変形したもの、赤の偏は元の頂点の内部
3. AVL 木、左と右の再代の高さの差が高々1に限定された二分探索木

外部メモリ用

4. B-木、外部メモリのページの大きさに子供の数を合わせた2-3-4 木の変形
5. B+木、キー以外のデータが全て葉のページに収まれるB-木の効率のいい変形

ハッシュ表の利点を、同じ用途のデータ構造と比較して書きなさい。(4 点)

上記の五つのデータ構造はすべて探索木です。辞書の主な操作 (挿入、探索、削除) は探索期の場合は、すべて O(log n) ですが、ハッシュ表の場合 O(１) になります。

ハッシュ表の欠点を、同じ用途のデータ構造と比較して書きなさい。(2 点)

探索木の場合、通り掛け準でデータをキーの順で出せるが、ハッシュ表ではソートは別途発生する。

ハッシュ表にどんどんデータ項目を挿入すると激突対策の効率が落ち、表を拡大する必要がある。そのたび、O(n) の計算量が
発生するが、ハッシュ表の効率は落ちることがない。 その理由を分析し、分析の名前とその名前の理由とともに書きなさい。(8 点)

項目を入れるたびに表を拡大すれば、n 個のデータの挿入に 1+2+...+n で O(n²) がかかり、一つのデータ項目あたりに O(n) となる。そこで n が倍になるときだけ拡大を行うと、1+2+4+8+...+n/2+n で全体で O(n) で、データ項目ごとに O(1) になる。これを償却分析という。
償却分析の名前は会計学からきて、票の拡大の時に投資をし、その後の項目の追加でその投資を償却するのが名前の由来。

整列のアルゴリズムの選択 / Selection of Sorting Algorithms (合計 22 点)

下記の三つの事情に合わせて、整列アルゴリズムを実装するように頼まれた。 適切なアルゴリズムを選び、そのアルゴリズムの名前、
仕組み、選んだ理由と実装の際に特に注意すべき点を記述しなさい。
You have been asked to implement a sorting algorithm for each of three situations below. Select algorithms and give name, workings, the reason for the selection, and points that need special care during implementation.

今の時代だから、内部メモリは十分な余裕が。ライブラリの用の安定したソートが欲しい。
These days, there's always enough spare memory, but we need a stable sort for a library. (6 点):

マージソートを選ぶ。マージソートはデータを再帰的に半分に分割し、部分ごとに整列し、 整列済み部分を順番を考慮して併合するアルゴリズム。実装に注意すれば安定性を保証できる。 計算量の O(n log n) のアルゴリズムのうち、唯一安定性が実現できるもの。
 
 

ライブラリに組み込むために本格的でできるだけ早い実装が欲しい。
A serious and very fast implementation is needed, to become part of a library (10 点):

クイックソートを選ぶ。クイックソートはデータをできるだけ乱数で選んだ 分割要素を境界に再帰的二に分割する。 最悪の計算量は O(n²) だが、平均では O(n log n)。他にも同じ計算量のアルゴリズムはありますが、 クイックソートは操作が少ないので、その中で一番早い。注意すべき点は特に分割要素の選択 (三項目の中央値や乱数) だが、他に同値の項目の取り扱いやスタックが深すぎてオーバフローになる問題に対応しないと、本格的な実装にならない。
 
 
 

扱うデータの項目数は比較的少ないが、一つのデータ項目ごとのデータ量が多いので、 移動回数を最小限にする、
実装が簡単なアルゴリズムが欲しい。/ There are not really that many data items, but each data item is quite big.
We need a quick implementation that minimizes the number of data movements. (6 点):

選択ソートを選ぶ。選択ソートは一番小さい項目を選んで、一番左の項目と交換し、これを 残りのデータ項目で繰り返す。移動 (交換) の回数が O(n) で、ほかのどのアルゴリズムより少ない。全体の計算量は 実装もわりと簡単で、注意点が少ない。計算量は比較回数のため O(n²)。
 
 

授業へのコメント / 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)

@@@@
@@@@

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

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

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

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

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

上記のアルゴリズムが、アルファベットの大きさ (文字の種類の数) によって、どのように影響されるか論じなさい。(6 点)

アルファベットが大きい場合 (例えば東洋の言語で数千字) ではほとんどの場合、末尾での比較対象がパターンに 入ってない可能性が非常に高く、効率がいい。逆にアルファベッツが小さい (例えばヌクレオチド列で4字、ビット列で2字) 場合、 比較対象がパターンの他のところに存在する確率が高く、効率が落ちる。

行列の乗算の順番の最適化 (18 点)

四つの行列の連鎖乗算 ₀M₁ · ₁M₂ · ₂M₃ · ₃M₄ が与えられている。 行列の大きさは r₀=12, r₁=5, r₂=10, r₃=3, r₄=8 である。

最善の計算順とその場合のスカラー値同士の乗算の数を求めなさい。 計算の過程や途中結果も書きなさい。(10 点)

₀M₁ · ₁M₂ の乗算数は 600、 ₁M₂ · ₂M₃ は 150、 ₂M₃ · ₃M₄ は 240；
₀M₃ は ₀M₁ · ₁M₃ で乗算数が 0+150+180=330 で, ₀M₂ · ₂M₃ で 600+0+360=960 なので、 前者が 330 で最善；
₁M₄ は ₁M₂ · ₂M₄ で 0+240+400=640 で、 ₁M₃ · ₃M₄ で 150+0+120=270 なので、後者が 270 で最善。
₀M₄ は ₀M₁ · ₁M₄ で 0+270+480=750 で、 ₀M₂ · ₂M₄ で 600+240+960=1800 で、 ₀M₃ · ₃M₄ で 330+0+288=618 で、 ₀M₁ · ₁M₄ が 618 で最善。
よって、乗算の順番は (₀M₁ · (₁M₂ · ₂M₃) · ₃M₄ で最善。

逆に最悪の計算順とその場合のスカラー値同士の乗算の数を求めなさい。 計算の過程や途中結果も書きなさい。
前の部分問題の計算をもう一回書く必要がない。(8 点)

₀M₃ では ₀M₂ · ₂M₃ が 960 で最悪。
₁M₄ では ₁M₂ · ₂M₄ が 640 で最悪。
₀M₄ は ₀M₁ · ₁M₄ で 0+960+480=1440 で、 ₀M₂ · ₂M₄ で 600+240+960=1800 で、 ₀M₃ · ₃M₄ で 960+0+288=1248 で、 ₀M₂ · ₂M₄ が 1800 で最悪。
よって、乗算の順番は (₀M₁ · ₁M₂) · (₂M₃ · ₃M₄) で最悪。

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

下記の課題に対して、下記の最初の四つの部分問題のアルゴリズムの設計方針や原理を使った際の、 それぞれのアルゴリズムの
概略を提案しなさい。また、それぞれに対し、予想される計算量とその根拠、発生する問題点について述べなさい。
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.

課題: メモリの割り当て問題： 合計のメモリ量 m (単位： バイト) に対し、n 個のデータ (k 個目のデータは大きさ l_k のメモリを
時間 s_k から時間 t_k (単位： 秒) まで使用すること)でできるだけ最適なデータの割り当てを算出する問題。

分割統治法 / divide and conquer

データを再帰的に二つの集合に分け、最初は二つのデータだけの組み合わせの配置を作る。 その組み合わせを逆順で統合しておく。最善の計算量は O(n log n) だが、組み合わせがうまくいかないケースが所持る可能性がある。 分割のところで、できるだけ組み合わせしやすい分割を選ぼうとすると、いいかいが見つけやすくなるが、計算量が増える可能性もある。解を見つける保障がないのが問題。

貪欲アルゴリズム / greedy algorithm

データを大きさまたは時間の長さでソートする。大きいまたは時間的に長いデータの方から 割り当てを試してみる。大きさx長さの積の順でもいいかも。計算量はソートが必要なため O(n log n)。解を見つける保障がないのが問題。

遺伝的アルゴリズム / genetic algorithm

第1世代としてデータの割り当てをいくつか作る。次の世代を作るとき、 前の世代の案を二つ (以上) を組み合わせ、新しい解を作る。その時、乱数で突然変異みたいな変更も加える。 いい解を多めに残し、悪いかいを多めに捨てるように次の世代を構成する。計算量は O(世代数ｘ解の数ｘn） で相当大きい。細かい設定が課題です。

動的計画法 / dynamic programming

データを開始時間 (s_k) でソートする。最初は一秒ごとに局所的な配置を計画する。 そこから隣り合わせの解を組み合わせ、2秒、3秒、とどんどん長いスパンの解を作る。計算量は O(n*全体の時間²) で、解を見つける保障がないのが問題。

社長に「この問題を明日の朝まで解かないうちの部署が危ない。」と言われたときの返事の概略を書きなさい。
なお、メモリの割り当て問題を調べたところ、NP困難問題であることが判明した。

大変申し訳ございませんが、この問題は 3-SAT 問題、独立集合問題や巡回セールスマン問題をはじめ多くの問題と同様に NP 困難であり、いまだに必ず早い時間 (指数的時間で数年以上のではなく、多項式時間で明日の朝まで) で完璧に解けるアルゴリズム (方法) が見つかっていません。 万が一見つかったら世紀の大発見になり、一億円以上の賞金も貰える。 多くの専門家はそれが無理だと思っているが、その証明もいまだできていません。

O 記法 / Big-O Notation (20 点)

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

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

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

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

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

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

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

O 記法でどの場合に対数の底が無視できるのかを、次の O 記法の対で判断し説明しなさい。
Using the following pairs of big-O notations, decide whether the base of a logarithm can always be ignored or not and explain.

O(2^log₂n) と/and O(2^log₄n)                         O(n^log₂n) と/and O(n^log₄n)

前者の場合、2^log₂n = n ですが、2^log₄n = n^1/2 (n の平方根) なので、明らかに伸び率が違う。
後者の場合、log₄n を 1/2*log₂n と書き換えると、 n^log₄n = n^1/2*log₂n で、これも n^log₂n の平方根になって、明らかに伸び率が低い。 よって、O 記法では係数での log の底は無視できるが、指数では log の底は無視できません。

プログラミング言語によるアルゴリズムの表現 (8 点)

プログラミング言語によるアルゴリズムの表現方法の利点と欠点を書きなさい。

利点 (2 点): プログラミング言語は正確で、そのまま (コンパイル後) に実行可能。

欠点 (2 点): 場合によって細かすぎる。言語が分からない人にはわかりにくい。

プログラミング言語として C と Ruby を比べると、どちらがアルゴリズムの表現に向いているのか、
そしてその理由を詳しく書きなさい。(4 点)

Ruby だと思います。なぜかというと、行末にセミコロンが不要で、変数の宣言も不要で余計な記述がいらない。 関数や変数に型を指定する必要もないので、同じ記述を複数の型 (例: 整数と実数) に使える。高度でアルゴリズムの本質に近い記述可能です。