アルゴリズムとデータ構造についての豆知識 (12 点)

下記の発言の前、正しければ ○、間違いであれば × を書きなさい。

例	○	線形探索の計算量は O(n) である。
	×	開番地方よりも連鎖法で占有率が高い。
	×	NP=P を証明できれば3億円以上の賞金がもらえる。
	○	Ruby で型宣言が不要なので疑似コードに向いている。
	×	アルゴリズムを実装しないと評価できない。
	×	最初のアルゴリズムは西暦800年辺りに Muhammad ibn Mūsā al-Khwārizmī に発見された。
	○	NP 完全問題でも、具体的なデータの場合、意外と簡単に解けることもある。
	○	Google は特定のアルゴリズムのおかげで大企業になった。
	×	クイックソートで番兵を使う価値がない。
	×	NP 完全問題はアルゴリズムでは解けない。
	○	どんなアルゴリズムでも解けない問題が存在する。
	×	「普通」のヒープで合併は O(log n) で可能。
	○	整列は条件によって O(n) でも実装が可能。

計算量の比較 (10 点)

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

O(1000 log log n), O(1.2ⁿ), O(10000n) O(32⁶⁴), O(log₈ n), O(n), O(n log n),
O(log (n³)), O(n^1.02), O(n!), O(log_n n), O(1.05ⁿ), O(nⁿ), O(n^1.1)

O(32⁶⁴) = O(log_n n) ⊂ O(700 log log n) ⊂ O(log₈ n) = O(log (n³)) ⊂ O(n) = O(10000n) ⊂
⊂ O(n log n) ⊂ O(n^1.02) ⊂ O(n^1.1) ⊂ O(1.05ⁿ) ⊂ O(1.2ⁿ) ⊂ O(n!) ⊂ O(nⁿ)

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

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

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

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

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

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

stable sorting

安定な整列法; 整列基準において同等の様子の順番を入れ替えない整列法

cryptographic hash function

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

local optimum

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

inorder

通りがけ順、(二分) 木の辿り方で、親を左のこの後、右のこの前に処理する

genetic algorithm

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

decision problem

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

perfect hash function

完全ハッシュ関数; あらかじめ決まったデータに対し、激突が起こらないハッシュ関数

binary search

二分探索; 整列したデータで、範囲を再帰的に二分にして O(log n) の探索方法

memoization

履歴管理; (数学的) 関数の結果を保存することで再計算を防ぐ

linked list

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

random algorithm (4 点)

乱数アルゴリズム; 乱数を使ったアルゴリズム。例えばクイックソートで
分岐点を乱数で選ぶことによって、最悪の計算量を避けることが可能。

independent set (problem) (4 点)

独立集合 (問題); NP 問題の一つで、グラフでできるだけ多くの繋がってない
頂点の集合を返す問題。実用性が高く (例: パーティの主催)、判定問題は NP 完全問題

polynomial time (4 点)

多項式時間; 実行時間が項目数の多項式で表せる実行時間。問題「手に負える」という。
多項式の和や積が多項式、具体的な問題で指数が低いのは理由。

priority queue (4 点)

優先順位付き待ち行列; 優先順位の高いものが先頭に回る待ち行列。実装には
ヒープが最適。完全に分木で子より親の方が優先度が高いので、根は常に一番優先度が高い。

amortized analysis (4 点)

償却分析、データ構造をたまに時間をかけて大幅に作り直す場合の計算量の分析
応用例としては ハッシュ表の作成の計算量がある。

Ω と Ω (6 点)

O(g(n)) 以外に Ω(g(n)) と Θ(g(n)) が存在。 ∩/=/⊂ を使って、三つの文字が表現している関係を知っている限り書きなさい。

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))
Θ(g(n)) ⊂ O(g(n))
Θ(g(n)) ⊂ Ω(g(n))

マージソートの計算量 (36 点)

マージソートの計算量を漸化式で求める。問題を通して、n = 2^k に限定しなさい。

マージソートの仕組みを簡単に説明しなさい。(4 点)

マージソートはソートする配列を再帰的にできるだけ均等に半分にわける。分けたものを「併合」 (二つのソート済みの部分配列から順次に小さい方の要素を選んで、一つのソート済み配列にする) で再帰的に合流させ、 全体の配列を整列します。

計算量を求めるため、漸化式を立てなさい。

M(1) = 0 (1 点)

上記の理由 (2 点): 長さ 1 の配列は既に整列済み

M(n) = 1 + 2 M(n/2) + n (4 点)

上記の理由 (4 点): 配列を二つに分けることは一定時間かかる。二つの長さ n/2 の配列は再帰的にマージソートする。その後、マージ (併合) そのものには O(n) の時間がかかる。

漸化式を説明を添えながら授業と同じ方法で解いてください。 (15 点)

パターンを代入の繰り返しで発見します。
M(n) = [一回目の展開]
= 1 + 2 M(n/2) + n = [二回目の展開]
= 1 + 2 (1 + 2 M(n/2/2) + n/2) + n = [単純化]
= 1 + 2 + 4 M(n/4) + n + n = [三回目の展開]
= 1 + 2 + 4 (1 + 2 M(n/4/2) + n/4) + n + n = [単純化]
= 1 + 2 + 4 + 8 M(n/8) + n + n + n = [パターンが見えてきたので、まとめる (展開の数が k )]
= 2^k - 1 + 2^kM(n/2^k) + kn
M(1) = 0 の活用: n/2^k = 1 ⇔ k = log₂ n
2^k - 1 + 2^kM(n/2^k) + kn = n-1 + 2M(1) + n log n
結果、M(n) = n-1 + n log n  

マージソートの計算量を書きなさい。O(n log n) (1 点)

マージソートの利点について説明しなさい。(3 点)

クイックソートと違って、平均だけではなく、最悪でも O(n log n) で動く。膨大なデータで内部メモリに入りきらないときに有効。

マージソートの欠点について説明しなさい。(2 点)

併合の時にデータをコピーしないといけないので、メモリがデータの２倍必要です。

文字列照合の実装の選択 (18 点)

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

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

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

対象とする文書は膨大がだ、あらかじめ知られている。パターンは単語などに限定されるが、毎回変わる。素早い実装が必要。:

検索エンジン作成のための依頼と考えられます。
索引として辞書という抽象データ型の一つの実装、例えばハッシュ表、を選びます。
キーは検索される単語、データはその出現ヵ所 (複数ヵ所あり) になります。
ハッシュ表による実装では探索は O(1) になって、とても効率的です。
パターンは単語に限るによって、単語横断の検索はできないことに注意すべきです。
ハッシュ関数がばれると攻撃される恐れがあるので、乱数を使った万能ハッシュ法を使っと法がいいです。

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

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

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

@@@@
@@@@

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

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

疑似コードとバブルソートアルゴリズム (合計 18 点)

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

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

バブルソートの利点について細かく説明しなさい。（3 点）

仕組みが非常に分かりやすく、
実装が簡単で早くて間違いにくいです。

バブルソートの欠点について細かく説明しなさい。（3 点）

計算量が O(n²) だけではなく、腕力法で隣同士の比較・
入れ替えだけで、同等の計算量のアルゴリズムよりも最も遅いです。

O 記法の説明 (8 点)

プログラミングが得意な中学校の同級生と久ぶりに会う。プログラミングが得意だったせいか、高校を中退し、IT企業に務めている。次の会話の続きとして O 記法の仕組みと意義を詳細に説明しなさい。

同級生: 最近すごい早いプログラムを書きました。新アルゴリズムかも。

自分: 面白そう。計算量はどうですか。O(n) ですか。O(n²) ですか。

同級生: しらん。そんなの分からん。今のデータで十分早いなのでどうでもいいじゃん。

自分:
計算量はアルゴリズムの評価に大事です。
データがさらにどんどん増えたら、アルゴリズムがどの調子で遅くなるのかを示す。
O 記法はそれを非常にコンパクトで便利に表現します。
O 記法はハードウェアの性能にも依存しないが、
O(n) であれば例えば 10 倍のデータで 10倍遅くなるのに、
O(n²) の場合、データが 10倍の場合、100倍遅くなる。

アルゴリズムの設計方針 / 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.

課題: グラフの三角形分割問題では、n 個の頂点 (n は3の倍数) と m 個 (m≧n) の辺からなるグラフが与えられ、辺で三角形に繋がっているように頂点の三つ組への分割を求め、不可能であればその旨を出力する。

動的計画法 / dynamic programming

頂点を、辺を見ないで三つ組に分割し、一直線に並ぶ。できるだけ組の中の頂点を三角形に結ぶ。 そこから隣同士の組を合わせ、層毎に徐々に組を大きくする (頂点6個の層、9個の層、...)、その組内にまだ独立している頂点もできるだけ三角形にする。 計算量は O(n³) の可能性が高い。問題は、全ての頂点を三角形に結ぶことができないかも。

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

乱数を使って、(一部の頂点が独立している可能性も含む) 解の候補を沢山作る。そのかいから何回も乱数を使って頂点を組み替えて新しい解を作る。新しい解を作るときに変更の度合い (組み替える頂点の数) を徐々に減らしておく (=温度を下げる)。悪い解を中心に買いを捨てる。計算量は n x 回数 ｘ 解の数に比例。 問題点は温度の下げ方の調整と部分解の組み合わせができないこと。

分割統治法 / divide and conquer

頂点を再帰的に二つの集合に分け、数が5以下になったら、できるところを三角形に結ぶ。 残りの頂点を回の併合の時にできる限りに三角形に結ぶ。最善の計算量は O(n log n) だが、残る頂点が多い場合は計算量が悪化する。 利点は最善の時の計算量だが、分割によって局所的に三角形に結んだ所を後で組みなおせないので、解が見つからない可能性もある。

貪欲アルゴリズム / greedy algorithm

頂点をある基準、例えば頂点につながっている辺の数の昇順、に並び替え、 その順で三角形の分割を試みる。降順は最初がやりやすいが、後からやりにくくなるし、昇順では後の方に余裕が残る可能性もあり、不可能な場合、早く気が付くチャンスがある。 計算量は O(n log n) や O(n³) (三角形の二つ目と三つ目の頂点の選び方による)。問題は、いったん決まった組は後から変更できないこと。

社長に「大事な顧客の多数の大規模なグラフに対し、必ず明日まで解を出してくれ。」と言われたときの返事の概略を書きなさい。なお、三角形分割問題は調べたら、 NP完全問題であることが判明した。

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

2-3-4 分木、B 木、B+ 木 (46 点)

2-3-4 分木、B 木、B+ 木の共通の目的 (応用) を説明しなさい。(3 点)

三種類とも探索木で、抽象データ型の辞書 (鍵と値の対をたくさん保存できる) を実装する。

同様の目的を達成できる他のデータ構造を列挙しなさい。(3 点)

AVL 木、赤黒木、ハッシュ表

2-3-4 分木、B 木、B+ 木共通の普遍条件を書きなさい。(4 点)

木の高さが一定 (全ての葉がルートから同じ距離にある)
内部節の子の数が最低の場合、最高の半分以上 (またはmin_child_number>=max_child_number*α)

上記の木での三つの基本操作を授業と同じ順番で説明しなさい。(12 点)

探索: 根から探索を開始。節にキーがあれば、対応する値を返す。 節にキーが無ければ、節のキーと探しているキーを比較しながら次に探索する子を決める。 葉にキーが無い場合、「見つからない」と返す。

挿入: 探索と同じようにキーを探す。見つかったら実装異存 (ダブりを許すかどうか)。 見つからない場合、葉に挿入。葉に場所が残ってない場合は、一部のデータを隣の葉に移動、葉を分けて親にキーを追加などで対応。

削除: 探索と同様に、削除したいものを探す。内部節にある場合、キーが一番近い葉と交換。葉の項目を削除。 葉の最低項目数を下回ったら、隣の葉から借りる、隣の葉と合併し、親の項目を一つ減らすなどで対応。

次の表に該当する数値を記入しなさい。なお、必要なところではページの大きさ: 2048バイト、キーの大きさ: 10バイト、
値の大きさ: 240バイト、ページ番号の大きさ: 4バイト、最低占有率: 0.5 で計算しなさい。(20 点)

	2-3-4 木	B 木	B+ 木
内部説の最大のキーの数	3	8	146
内部説の最大の値の数	3	8	0
内部説の最大の子の数	4	9	147
内部説の最低のキーの数	1	4	73
内部説の最低の値の数	1	4	0
内部説の最低の子の数	2	5	74
葉の最大のキー・値の数	3	8	8
葉の最低のキー・値の数	1	4	4

B+ 木の利点を根拠を含め詳細に説明しなさい。(4 点)

B+ 木はページごとにアクセス可能な外部メモリに適している。B 木と違って、内部説にデータを入れないため、 内部説の子の数を最大化し、木の高さを出来るだけ浅くする。それにより、データへのアクセス (ページごと100ms 程度) が B 木に比べて早くなるのが最大の利点です。