クイックソートの注意点 (12 点)

クイックソートは早いと知られているが、実用的な実装の場合には注意点がいくつかあります。その注意点から三つ選んで、細かく説明しなさい (できるだけ細かく説明できる注意点を選択しなさい)。

ピボットの選択： 最小や最大の値がピボットに選ばれると、クイックソートの効率が非常に
悪くなる。簡単なため、最初の項目や最後の項目をピボットに選ぶと、既に整列や逆整列
されているデータの場合、計算量が n の二乗になってしまう。できるだけ真ん中に来る
ピボットの選び方として、乱数で選ぶと、三項目の中央値を選ぶなどがある。

スタックの深さ： クイックソートは再帰的なアルゴリズムなので、再帰の深さによって
stack overflow もありうる。それを防ぐため、二分割の小さい部分だけを
再帰的にし、大きい部分を末尾再帰または繰り返しで実装するのは
大事です。

キーの重複： 同じキーが多く重複するときに、単純なクイックソートは最悪の計算量
(n の二乗) になりやすい。対策としてはピボットより大きい、小さいの二分割のでは
なく、三分割にした方がいい。ピボットに比べて < と >= への分割と、
<= と > への分割を交代することで疑似的に実装が可能のではないか。

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

アルゴリズムの表現に適した実際に実行可能なプログラム言語を一つ選んで、明記の上にその選択の理由、利点と欠点を細かく説明しなさい。

Ruby を選びます。[他の言語でもよい!]
Ruby は「動く疑似コード」と言われるので、アルゴリズムの表現に非常に向いている。
利点: 動的型付けなので、方の詳細に気をとられないでアルゴリズムの本質に注目可能。
型の宣言が不要、同時代入が可能などで疑似コードの多くに使われるものがそろっている。
行末のセミコロンなどが省略可能なので、記述が簡潔。
irb による対話的な実行、プロファイラなど環境が充実。
欠点: 配列など組み込みクラスを使うと、隠されたところで計算量が上がる恐れがある。
本当の疑似コードではごまかしも聞くが、実行したい場合にはごまかしはできない。
番兵などではオブジェクト指向 (OO) が有効に使えるが、初心者に分かりにくいかも。

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

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

@@@@

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

@@@@

マージソートの併合の疑似コード (16 点)

二つの配列 array1 と array2 を三つ目の配列 array (それぞれの長さが length1, length2, length(=length1+length2)) に併合するマージソートの併合のアルゴリズムを疑似コードで書きなさい。

algorithm merge
  inputs: two array (array1, array2),
          two array lengths (length1, length2),
  output: merged array
  
  i1 ←  0; i2 ←  0; i ← 0
  loop
    if i1 < length1
      if i2 < length2 and array1[i1] > array2[i2]
        array[i] ←  array2[i2]
        i2 ← i2+1
      else
        array[i] ←  array1[i1]
        i1 ← i1+1
      end
    elsif i2 < length2
      array[i] ←  array2[i2]
      i2 ← i2+1
    else
      return
    end
    i ← i+1
  end
end

Ω と Θ (8 点)

O() 記法以外に Ω() と Θ() があります。それぞれの意味と定義について説明しなさい。

Ω(): Ω(g(n)) は g(n) の増加以上の関数の集合と定義されている。
Ω (ギリシャ文字の大文字のオメガ) は O と同じようにある増加の関数の集合を表す。
∃c>0: ∃n₀≥0: ∀n≥n₀: c·g(n)≤f(n) ⇒ f(n)∈Ω(g(n))
Ω 記法はアルゴリズムや問題の最低計算量などで使われる。

Θ(): Θ(g(n)) は g(n) の増加と同等の関数の集合と定義されている。
Θ (ギリシャ文字の大文字のシータ) も O と Ω と同じようにある増加の関数の集合を表す。
∃c₁>0: ∃c₂>0: ∃n₀≥0: ∀n≥n₀: c₁·g(n)≤f(n)≤c₂·g(n) ⇒ f(n)∈Θ(g(n))
Θ は O と Ω の組み合わせ、すなわち Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

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

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

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

平衡木の選択肢もあるが、キーに順番がない場合でも使えるハッシュ表を選びます。
ハッシュ表は探索、挿入、削除ともに O(1) となっているが、特に挿入の場合、
これは償却分析によるもので、非常にまれに挿入が O(n) になる。
ハッシュ表の設計において、激突への対策が大事ですが、これをチェイン法で実装する。
ハッシュ関数の選択は、納めるデータ型によってライブラリの使用者が決めるようにする。
ハッシュ表の課題は、データを順番に出したい場合、ソートが別に必要ということです。

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

B+ 木を選びます。B+ 木は 2-3-4 木の拡張で、ひとつのノードのデータがちょうど
ハードディスクなどの外部メモリの一つのページに入るようになっています。
キー以外のデータは全て葉のノードに入ることでアクセスするページの数を抑えている。
計算量は 探索・挿入・削除ともに O(n log n) です。探索と挿入の実装は
割と簡単ですが、削除は他の木構造と同様に相当複雑。各ノードの容量は
半分以上しか使用されない場合もあるので、ハードディスクは十分用意する必要がある。

データはすべて最初から提供され、その後変わらない (10 点):

「その後変わらない」というのは、挿入・削除が必要なくて、
探索だけが必要ということです。そのため、データを配列に入れ、
あらかじめソートします。探索には二分探索をつかいます。
木構造な場合に必要な参照などが必要なくて、非常に
コンパクトに実装できます。作成は O(n log n) で、
探索は O(log n) の時間がかかります。

文字列照合の最悪の計算量 (12 点)

文字列照合の素朴な実装とその場合の最悪の計算量を実例を使って説明しなさい。

実例は文書が a...ab (a が n-1 個) で、パターンは a..ab (a が m-1 個, n >> m)。
外側のループはパターンをシフトして、中川のループはパターンを一文字ずつ文書と比較する。
計算量は、上記の例でパターンを毎回最後の文字まで比較するので、O(nm)。

次の二つのアルゴリズムの場合、上記の最悪の実例を使ってその時のアルゴリズムの動きと計算量を説明しなさい。

Knuth-Morris-Pratt のアルゴリズム: パターン内の構造を分析したうえで、文書内の比較対処を絶
対後戻りしない。パターンの最後に来たところで a と b が合わない時、パターンをずらす、
文書内の位置をずらす、の繰り返しで動くので、比較階数がおよそ 2n で計算量は O(n)。

Boyer-Moore のアルゴリズム: パターンの最後の文字から比較開始なので、その場で合わない
のはすぐ分かるが、パターンの最後の b の前の文字が全部同じなので、パターンを文字一つ
しかずらせない。結果的に上記の例では計算量が O(n) で、最善の時の O(n/m) を下回る。

用語の説明 (16 点)

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

amortized analysis

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

radix sort

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

inorder

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

secondary storage

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

memoization

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

invariant

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

chaining

連鎖法; ハッシュ表で激突が生じるときに連続リストを使う方法

genetic algorithm

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

O() 記法の特徴 (20 点)

次の表に同じ行に書いてある二つの O() 記法を、その間の欄を使って「⊂」、「=」、又は「⊃」で小さい場合、同等な場合、大きい場合を区別し、一番右側の欄にその理由を、数式を含め書きなさい。

番号		⊂/=/⊃		理由
	O(200n)	⊂	O(nn)	n > 200 で nn > 200n である。
	O(log log n)	⊃	O(lognn)	lognn が常に 1 に 対して、log log n は非常にゆっくりが伸びる。
	O(200n2.3+5000n2.8)	⊂	O(134n3.2)	多項式の場合、一番大きい項以外 の項も定数の因子も無視できるので、 n3.2 は n2.8 より大きい。
	O(log1.1 n)	=	O(log100 n)	log1.1 n = log1.1 100 · log100 n であって、log1.1 100 は定数 のため無視できる。
	O(1.1n)	⊃	O(n100)	右側の n のところの伸び率は (n/(n-1))100 で、左側の伸び率は 1.1。1.1-100= n/(n-1) 以降で左側の 伸び率が大きくなる。

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

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

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

課題: 某会社の社長から盛大なパーティーを開きたいため、知り合い n 人 (例えば 400人) のリストをもとに、実際に招待される k 人のリストを作ることを依頼されている。条件が二つ: (1) できるだけ多くの人を招くこと、そして (2) あらかじめリストに載っている情報により、お互いの仲が悪い人同士を招かないこと。

分割統治法

招待可能な人のリストを再帰的に二分割し、 そこから逆順に併合する。併合するときには両方のグループから交代で可能な限り人を追加する。 既に追加された人と仲が悪い人は除去する。計算量が O(n² log n)。 問題は、分割によって最適解より悪い結果が得られることである。

貪欲アルゴリズム

人を仲が悪い友達の小さい順に整列し、 順番に解に追加する。既に仲が悪い人がいれば、追加しない。 整列より仲の悪い人のチェックが計算量が多いので、計算量は O(n²)。 仲の悪い人が少ない穏やかな人を先に選ぶため、ある程度の結果が得られる可能性があるが、 「効率」の順でやっているので結構いいところまで行くと期待されるが、最適解を出すのは難しい。

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

最初は乱数を使って一定数の解を作る。 繰り返し各解から人を招く有無を変更し、複数の新解を作成。仲の悪い人が存在する解は常に除外する。 最初は有無の変更数を多く (例： 20人) し、徐々に一人まで削減。 全体を通じて一番いい解を結果に。計算量は O(n∙繰り返しの数∙繰り返し毎の解数)。 問題点: アルゴリズムの調整 (冷まし具合)、最適解が得られる保証がない。

動的計画法

入力順に、重なるように二人組、三人組 の順に、その組で可能な一番多い人の組み合わせを「行列の掛算の順番を決める」と同じ様に選ぶ。 組み合わせを仲が悪い人がいる時、使わない。計算量は仲が悪い人のチェックも必要なので、 O(n⁴)。仲の悪い人が多い人が結構早めに除外されるのがこのアルゴリズムのいいところだが、 部分構造の最適性の保証がないので、最適解に届くのが難しいです。

社長に「必ず一番人が多くなる様に、お客さんのリストを作れ」と言われたときの返事の概略を書いてください。

この問題はいわゆる「独立集合問題」の応用です。 独立集合問題は例えば巡回セールスマン問題をはじめ他の多くの問題と同様に NP 困難であり、 いまだに必ず早い時間 (数年以上のではなく、パーティーに間に合う間) で解けるアルゴリズム (方法) が見つかっていません。万が一見つかったら世紀の大発見になり、一億円の賞も貰える。 多くの専門家はそれが無理だと思っているが、その証明もいまだできていません。