計算量 (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.

x = q * p;
t = x - 70;
x = q + t;

足し算二つ、掛算ひとつ、代入三つしかしないので、一定時間に終わるので、O(1)

---

for (a=0; a<k; a++)
    for (b=0; b<a; b++)
        sum += detail[b] * detail[a];

二重ループで、b は最初狭い範囲でしか動かないが、合計の割り算と足し算は n*n/2 回ぐらいあるので、O(n²)

---

int fun(n) {
    if (n<2)  total++;
    else for (i=0; i<n; i++) fun(n-2);
}

n が2以上の時にn 回繰り返して、さらに n-1 で自分を呼ぶので、n*(n-1)*... で O(n!)

---

for (k=n; k>0; k/=2)
    for (i=0; i<n; i++)
        total += 1;

for ループを一回回ると k が半分に減って、さらにループごとの計算量が一定なので、O(n log k)

---

for (a=0; a<=n; a++)
    for (b=0; b<n; b++)
        for (c=0; c<b; c++)
            total += items[c];

三つのループで、b が小さい時に一番内部のループが早く終わるが、全体で O(n³)。

図によるアルゴリズムの表現 (10 点)

アルゴリズムの表現方法の一つとして図があります。その利点と問題点を他の表現方法と比べながら詳細に説明しなさい。
Diagrams are used as a method to express algorithms. Explain in detail the advantages and problems of this method, in comparison to other methods.

利点 / advantages： 視覚的で全体像と全体の流れがつかみやすい。
プログラム言語などに比べて、一般人にも分かりやすい可能性がある。
ホワイトボードなどで簡単に書ける。

問題点 / problems： フローチャートなどの場合、構造化プログラミングと相性が悪い。
正式な形 (例えば UML) で綺麗な図を書くのは手間がかかる (ただし、ツール使用可)。
保存、編集、交換 (例えば電子メールなど) が難しい。

O(n log n) の整列アルゴリズムの比較 / Comparison of O(n log n) Sorting Algorithms (15 点)

O(n log n) の整列アルゴリズムは複数あるが、それぞれの実際の速さが違う。 その速さに影響するものの一つとして項目の移動または交換があります。下記のそれぞれのアルゴリズムにおいて、 移動や交換の数を n の関数で表し、その理由を書きなさい。(具体例： 選択ソートは交換の数が、最後の項目以外すべての項目を正しい場所に一回移動する必要があるため、n-1。)
The various O(n log n) sorting algorithms differ in actual speed. One of the reasons for this difference is the number of moves or exchanges of data items. For each of the algorithms below, describe the number of moves or exchanges necessary as a function of n, and give the reason(s) for your result. (Example: Selection sort needs n-1 exchanges, because all data items except for the last one have to be moved to their correct place once.)
(ヒント: 正確な関数が見つからない場合、近似してもいいですが、その場合使った前提を説明しなさい。
Hint: If you cannot find a precise function, give an approximation, but describe the assumptions you have made.)

マージソート / merge sort マージソートは各マージの段階に全ての項目を一回移動します。
マージの段階の数が ⌈log₂ n⌉ (log₂ n の天井関数) となる
よって、マージソート全体の移動の回数が n ⌈log₂ n⌉ である

クイックソート / quick sort クイックソートは最悪で O(n²) ですが、全ての項目の順番の確率が同じという前提で
平均的な計算量を分析すると、比較の数がおよそ 1.39 n log₂ n と分かる
入れ替えの数を比較の数から推測するには、一つの入れ替えができる為には
左側から分割要素より大きいものも、右側から分割要素より小さいものも見つける必要があるが、
大きい・小さいは更に確率 0.5 でなるので、入れ替えの数がおよそ 0.35 n log₂ n になる
一つの入れ替えを二つの移動と同等と扱っても、マージソートより早いのが分かる

ヒープソート / heap sort ヒープソート全体は二段階からなる: ヒープの作成とヒープからの項目の削除
ヒープの (一発での) 作成は O(n) ですが、heapify_down のループ回数 (=入替回数)
は最大でおよそ 5 n で、平均でおよそ 2.5 n です。
要素を取り除くときも heapify_down が使われるが、一番後ろ (下) から根のところ
に持ってきた要素に heapify_down を適用するので、殆どの場合、一番下まで heapify_down が必要
よって、n/2 log₂ n + n/4 (log₂ n - 1) + ... でほぼ n log₂ n
の入れ替えが必要になる。合計でおよそ 2.5 n + n log₂ n の入れ替えで、
マージソートよりも遅いのがよくわかる

ハッシュ表の開番地法 / Open Addressing for Hash Tables (10 点)

ハッシュ表の開番地法の用途と仕組みを詳細に説明しなさい。
In detail explain the purpose and workings of open addressing for hash tables.

ハッシュ関数によってデータ項目のハッシュ表内の場所が決まるが、 完全なハッシュ関数を作るのは多くの場合不可能なので、 激突 (複数のデータ項目が同じ場所に割り振られる) が起こります。 解番地法はそのための一つの対策である。データ項目はハッシュ表に直接 格納するが、既に格納されているの場所 (ビンとも言う) に新たに項目を 格納する場合、決まった方法で次々と別のビンを検討する。その場合、 占有率を1より十分低い値 (例えば <0.5) に抑えておかないと、 平均で一定時間内に (すなわち O(1) で) 挿入、探索、削除が保証できない。

探索用のデータ構造の選択 / Selection of Data Structures for Seaching (合計 24 点)

下記の三つの事情に合わせて、探索用のデータ構造を実装するように頼まれた。 データ構造を選んで、そのデータ構造などの名前、仕組み、探索の計算量、選んだ理由と実装の場合特に注意すべき点を記述しなさい。
You have been asked to implement data structures for searching for the three different circumstances described below. Select a data structure for each case, give the names of the data structures,... and describe their workings, the computational complexity, your reason for selection, and any special considerations.

扱うデータの量が膨大で、現代の計算機のメインメモリに入りきらない / the amount of data to be handled is huge and doesn't fit in today's computers' main memory:

B+ 木が最適を使います。データを最下層だけにおいて、それより上の層にキーのみを配置し、ノードの大きさ を外部メモリのページの大きさに合わせることで、外部メモリへのアクセスの数を抑えて、高速化につながる。 計算量は挿入、削除、探索とも O(log n) だが、一つ一つのページの取り寄せにかかる時間が長い。 実装の場合には特に削除がめんどくさい。
 
 
 

扱うデータ項目の全てのキーが前もって知られているし、項目ごとに必要なメモリが一定である。データの量がかなりあるが、早い探索アルゴリズムが欲しい / The keys for all data items are known in advance, and each data item needs the same amount of memory. The number of data items is fairly large, and a fast search algorithm is preferred:

項目を整列し、配列に入れるのが最適かと思われる。探索は二分探索で O(log n)。 実装が簡単で、余分のメモリもいりません。
 
 
 
 

データ項目が挿入される順番が予想不可能な場合でも対応可能な、ライブラリに組み込むための本格的な実装が必要 / A serious implementation for a library is needed, where the order of insertion of the data items cannot be predicted:

ハッシュ表を使います。キーからハッシュ関数でビンの番号を決め、そこからチェーン法でデータ項目を連結リストでつなぐ。 質のいいハッシュ関数を使って、占有率をある一定の値 (例: 5.0) より小さく保つと連結リストの平均の長さが限定されて、操作 (挿入、削除、探索) が一定時間 (O(1)) で可能。
 
 

アルゴリズムの設計方針 (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 個の変数と m 個の項の 3SAT 問題で解ける設計問題を依頼されている。 m も n もかなり大きな数である (例えば百万程度)。
Problem: The CEO of a certain company asks you to solve a design problem by solving a 3SAT problem with n variables and m terms. Both m and n are quite big (for example around one million).

貪欲アルゴリズム / greedy algorithm

変数を出現頻度順にソートし、その順に一番よさそうな値を決める。 整列が必要なので、計算量は O(n log n)。 最適解を出す保証がないが、 頻度の少ない返送が後回しされるので、それの値を決める時に何とかなる可能性もある。

動的計画法 / dynamic programming

変数を入力順にならべ、隣同士の変数二つ、三つ、… と 値の設定をお試みる。 計算量は行列の掛け算の順番と同様に O(n³) になりそう。最適性の保証がないので、最適解に届くのが難しいです。

分割統治法 / divide and conquer

変数を再帰的にに分割する。できるだけお互いに係わりのない (同じ項に出現しない) 変数で分ける。計算量が O(n log n) やそれ以上。 問題は、分割によって最適解より悪い結果が得られることである。

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

最初は乱数で変数の値を決める。複数の回の候補からスタートする。 さらに、乱数を使って、次々と候補を新たに作り出す。乱数で逆転する変数の数 (温度) を徐々に下げる。 計算量は O(n∙候補の合計の数)。 問題点: 温度の変化の調整、最適解が得られる保証がない。

社長に「大事なお客さんなので絶対に明日まで解を出してくれ。」と言われたときの返事の概略を書いてください。 Please write your answer when the CEO tells you "This is for a very important customer, so you have to find a solution by tomorrow early morning at all costs.".

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

二分探索木の探索の疑似コード / Pseudocode for Search in a Binary Search Tree (16 点)

根 root で与えられた、各ノードに key, data, left, right というメンバを持つ二分探索木でキー k のデータ項目を探すアルゴリズムを疑似コードで書きなさい。
In pseudocode, write the algorithm to search a data item with key k in a binary search tree given by root root, where each node has members key, data, left, and right.

algorithm binary_tree_search
  inputs: root (of binary tree),
          key
  output: data (for key) or nil (when not found)
  
  current_node ← root (start search at root)
  while true do       (loop can also be replaced by recursion)
    if current_node = nil_node (special node when children missing)
      return nil_node
    else if key < root.key
      current_node ← current_node.left
    else if key > current_node.key
      current_node ← current_node.right
    else if key = current_node.key
      return current_node.data
    else
      warn "Error: Inconsistent Binary Search Tree"
    end
end

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

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)
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 (32 点)

次の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。
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.

preorder

行きがけ順、(二分) 木の辿り方で、親を全ての子の前に処理する

amortized analysis

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

sentinel

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

brute force algorithm

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

traveling salesman problem

巡回セールスマン問題; 完全問題で、グラフの頂点を全て辿る最短経路を見つける問題

genetic algorithm

遺伝的アルゴリズム; 解を生物と進化論の現象と似た方法で最適化してみる方法

abstract data type

抽象データ型; データとそのための操作の組み合わせ

polynomial time

多項式時間; 実行時間が項目数の多項式で表せる実行時間

perfect hash function

完全ハッシュ関数; 激突の無いハッシュ関数、データに合わせて作る必要がある

decision problem

決定問題; 結果が真偽で表せる問題、理論的に扱いやすい

invariant

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

radix sort

基数整列; 最下位の桁から桁ごとにソートする方法 (安定なソートが必要)

memoization

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

cryptographic hash function

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

precomputation

事前計算; アルゴリズムの本体に入る前の準備のための計算

priority queue

優先順位キュー; 順位の優先度が一番高い項目を常に先に出す抽象データ型

計算量の比較 / Comparing Computational Complexities (10 点)

次の計算量を小さい順に並びなおしなさい。「⊂」または「=」で小さい場合と同等な場合を区別しなさい。
Arrange the following complexities in ascending order. Use "⊂" and "=" to distinguish smaller and equivalent complexities.
(例: O(1)=O(2)⊂O(nⁿ))

O(1.0001ⁿ), O(log₇ n), O(7000 log log n), O(n log n), O(n^1.004), O(2016n), O(30³⁰⁰⁰), O(log_n n),
O(log nⁿ), O(nⁿ), O(1.002ⁿ), O(n !), O(n^1.6), O(log (n^1.8))

O(30³⁰⁰⁰) = O(log_n n) ⊂ O(7000 log log n) ⊂ O(log₇ n) = O(log (n^1.8)) ⊂ O(2016n) ⊂ O(n log n) = O(log nⁿ) ⊂ O(n^1.004) ⊂ O(n^1.6) ⊂ O(1.0001ⁿ) ⊂ O(1.002ⁿ) ⊂ O(n !) ⊂ O(nⁿ)