計算量の比較 (12 点)

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

O(1.001ⁿ), O(1000 log log n), O(n log n), O(n^1.1), O(n !), O(1.0001ⁿ), O(log₇ n), O(log_n n),
O(log nⁿ), O(nⁿ), O(n ! !), O(n^1.7), O(2015n), O(50¹⁰⁰⁰), O(n), O(log (n³))

O(50¹⁰⁰⁰) = O(log_n n) ⊂ O(1000 log log n) ⊂ O(log₇ n) = O(log (n³)) ⊂ O(n) = O(2015n) ⊂ O(n log n) = O(log nⁿ) ⊂ O(n^1.1) ⊂ O(n^1.7) ⊂ O(1.0001ⁿ) ⊂ O(1.001ⁿ) ⊂ O(n !) ⊂ O(nⁿ) ⊂ O(n ! !)

自然言語によるアルゴリズムの表現 (10 点)

アルゴリズムの表現方法の一つとして自然言語の文書があります。その利点と問題点を他の表現方法と比べながら詳細に説明しなさい。

利点： プログラム言語などに比べて、一般人にも分かりやすい可能性がある。
形式が自由なので、何でも自由に必要な精度で表せる。
図と比べると、保存、編集、交換 (例えば電子メールなど) が余裕である。

問題点： 自然言語の選択により、その言語が分かる人にしか通じない。
疑似コードやプログラム言語も色々あるが、自然言語のほどの幅ではない。
曖昧性も大きな問題だ。

ハッシュ表のチェイン法 (12 点)

ハッシュ表のチェイン法の用途と構造を図を使って詳細に説明しなさい。

ハッシュ関数によってデータ項目のハッシュ表内の場所が決まるが、 完全なハッシュ関数を作るのは多くの場合不可能なので、 激突 (複数のデータ項目が同じ場所に割り振られる) が起こります。 チェイン法はそのための一つの対策である。データ項目をハッシュ表に直接 格納するのではなく、ハッシュ表の各場所 (ビンと呼ばれる) から連結リスト (いわゆるチェーン) を連結してデータ項目を格納する方法。 チェーン内では線形探索を使うが、占有率がある一定 (例: 5) 以下に 保たれている場合、操作 (探索、挿入、削除) は平均で一定時間で可能。
[図省略]

選択ソートの疑似コード (16 点)

配列 array (長さ len) の中のデータ項目を選択ソートで整列するアルゴリズムを疑似コードで書きなさい。

algorithm selection_sort
  inputs: array (length len),
  output: array (sorted)
  
  for i from 0 to length-2 do
    small_pos ← i
    
    for k from i to length-1 do
      if array[k]<array[small_pos]
        small_pos ← k
      end_if
    end_for
    
    temp ← array[i]
    array[i] ← array[small_pos]
    array[small_pos] ← temp
  end_for
end

B+木の大きさの計算 (14 点)

ページの大きさが 1024バイト、キーの大きさが 8バイト、キーを抜く一項目あたりのデータの大きさが 120バイト、ページ番号の大きさが 8バイト、最低占有率が 0.5で、データ項目の数が 2¹⁵の B+木で次の値を計算しなさい。

葉のページの最大項目数: 8                        葉のページの最低項目数: 4

内部説節のページの最大の子供の数: 64            内部説節のページの最大最低の子供の数: 32

葉のページの最大の数: 8192                      葉のページの最低の数: 4096

葉より一層だけ上の内部説の最大の数: 256        葉より一層だけ上の内部説の最低の数: 64

葉より二層上の内部説の最大の数: 8            葉より二層上の内部説の最低の数: 1

B+木の最低の高さ: 3                            B+木の最大の高さ: 4

B+木の最大合計ページ数: 8457            B+木の最低合計ページ数: 4161

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

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

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

マージソートを選ぶ。マージソートはデータを再帰的に分割し、部分ごとに整列し、 整列済み部分を順番を考慮して併合するアルゴリズムなので、ハードディスクやテープなど二次メモリが必要な 時に最適です。計算量は O(n log n)。部分の整列ですが、メインメモリに入る大きさの部分に分け、 その部分にクイックソートなどを使うと全体の効率が上がる。ハードディスクの数に合わせて二分割のではなく、三分割なども考えられる。
 
 

扱うデータ項目が常にほとんど整列された順番にある。そのための素早く実装できる早いアルゴリズムが欲しい:

挿入ソートを選ぶ。挿入ソートは項目を左から一つ一つその左側にすでに整列できている部分に挿入する。 そのため、ほとんど整列されているデータの場合、非常に効果的である。実装もわりと簡単で、注意点が少ない。 しかし最悪の場合、計算量は O(n²) なので、本当にデータが常に殆ど整列されているかをよく確認しないといけない。
 
 
 

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

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

授業へのコメント (6 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)

@@@@
@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)

@@@@
@@@@

データ量の増加で早くなるアルゴリズム (10 点)

データの量が増えるとアルゴリズムの実行時間が長くなるアルゴリズムが一般的ですが、データ (の片方) が長くなると実行が早くなるアルゴリズムがあります。このアルゴリズムを明記の上、この現象を中心に詳しく説明しなさい。

アルゴリズムは Boyer-Moore の文字列照合アルゴリズムである。 長い文書の中にある程度の長さのパターンを見つけるのが目的である。 Boyer-Moore のアルゴリズムは他の文字列照合のアルゴリズムと 違って、パターンが長くなると早くなる傾向があります。文書の長さを n, パターンの長さを m とすると平均の実行時間が O(n/m) である。 なぜならば、アルゴリズムはパターンの頭ではなく、パターンの末尾を文書と 照合するところから始まる。パターンの末尾の文字と比較される文書の文字 がパターンに全くはいてないと、パターンを一期に m 文字分ずらして次の照合 が行われる。

用語の説明 (16 点)

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

invariant

普遍条件、データ構造など保たされる条件で、挿入や削除などで修復する必要がある

cryptographic hash function

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

postorder

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

amortized analysis

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

sentinel

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

brute force algorithm

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

independent set

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

simulated annealing

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

辞書の実装 (18 点)

辞書という抽象データ型には様々な実装がある。各実装の計算量を下記の表に記入しなさい。

方法	探索	挿入	削除
整列無し連結リスト	O (n)	O (1)	O (n)
整列済み連結リスト	O (n)	O (n)	O (n)
整列無し配列	O (n)	O (1)	O (n)
整列済み配列	O (log n)	O (n)	O (n)
二分探索木 (最悪)	O (n)	O (n)	O (n)
二分探索木 (平均)	O (log n)	O (log n)	O (log n)
赤黒木	O (log n)	O (log n)	O (log n)
ハッシュ (最悪)	O (n)	O (n)	O (n)
ハッシュ (平均)	O (1)	O (1)	O (1)

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

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

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

課題: 某会社の社長から、m 個の機械で n 個の作業 s₀ ... s_n-1 (それそれかかる時間が t₀ ... t_n-1) の、全部の作業ができるだけ早く終わるスケジュールを作るように依頼されている。 作業はどの機会機械でも実行可能で、どの機会機械でも同じ時間がかかる。m も n もかなり大きな数である (例えば機械百台、作業一千個)。

分割統治法

機械の数を二分割する。作業を合計時間が近くなるように二分割する。 再帰的に機械が一つになるまで実行する。計算量が O(n log n)。 問題は、分割によって最適解より悪い結果が得られることである。

動的計画法

作業を入力順にならべ、隣同士の作業一つ、二つ、三つ、… と 合計時間を計算する。それによって、できるだけ均等に機会に作業時間を分割するように調整する。 計算量は O(n² + n*m)。最適性の保証がないので、最適解に届くのが難しいです。

貪欲アルゴリズム

作業を大きい順に整列し、順番に早く終わりそうな機会に当てる。 整列が必要なので、計算量は O(n²)。 最適解を出す保証がないが、小さい作業が多い場合、最適解にかなり近くなる可能性がある。

遺伝的アルゴリズム

最初は乱数で機械に作業を振り分ける解をいくつか作る。 その後解の組合せ (有性生殖)、解内の情報交換 (交叉)、乱数による変換 (突然変異) を使って、世代ごとに解を作り直して、一番いい解を生き残らせる。計算量は O(n∙解の数∙世代の数)。 問題点: アルゴリズムの調整、最適解が得られる保証がない。

この問題が NP 困難であると分かりました。社長に「絶対に明日まで一番いい解を出してくれ。」と言われたときの返事の概略を書いてください。

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