用語の説明 (20 点)

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

data structure

データ構造; 複数のデータ項目とその関係を (主に) 計算機内で記録する仕組み

polynomial time

多項式時間; アルゴリズムの計算時間がデータ項目の数の多項式で表せられる時間

binary search

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

asymptotic growth

漸近的な増加; 関数の引数の増加によって関数の結果がおよそどの勢いで増えるか

priority queue

優先順位付き待ち行列; 優先順位の高いものが先頭に回る待ち行列

invariant

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

brute force algorithm

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

divide and conquer

分割統治法; 大きい問題を(2)分割して小さくする方法で、アルゴリズムの設計方法の一つ

memoization

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

decision problem

決定問題; 解とが「はい」か「いえ」だけの問題

速いアルゴリズムが見つからない問題 (15 点)

知り合いがある問題を解ける速いアルゴリズムを見つけようとしていたが、失敗した。 もしかすると NP-困難な問題かもしれないと言っている。事実の確認の方法と、 確認された場合の具体性のある対策について細かいアドバイスを書きなさい。

NP-困難な問題かどうかの確認として、判定問題に変換し、 数多くのNP完全な問題の一つに帰着してみることがいい。帰着というのは問題を多項式時間でもう一つの問題に 変換し、その問題を解き、解を逆変換するということ。具体的な対策としては実際に解けたいときのデータの分析、 これに合わせもうちょっと簡単な万代にならないか、そして完璧なものをあきらめ、問題に特化したもしくは一般的な (例えばシミュレーテッドアニーリングや遺伝的アルゴリズム) 近似法が考えられる。

アルゴリズムの表現方法 (15 点)

アルゴリズムの表現方法を三つ選んで、その利点と欠点を説明しなさい。

辞書の実装 (18 点)

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

ヒープの作成の計算量 (15 点)

配列によって実装すれば新しいヒープは O (n) の計算量で作れる。 下 (配列の後ろ) から順次 heapify_down を適応する。しかし、合計の要素の数が n で、 最大に heapify_down に掛かる計算量は O (log n) なので、合計で O (n log n) になるのも不思議ではない。n = 2^a-1 の場合に限って、 計算量が O (n) であることを式を使って示しなさい。

n = 2^a-1 というのは、ヒープを二分木で見ると 各深さ毎に完全に埋まっているということです。即ち層ごとに 1, 2, 4, 8,..., 2^a-2, 2^a-1 項目がある。深さが浅い項目ほど heapify_down は時間がかかり、 一項目あたりの計算量は深さと逆比例する。合計の計算量は 1*a + 2*(a-1) + 4*(a-2) + 8*(a-3) + ... + 2^a-2*2 + 2^a-1*1 で、これは 2^a + 2^a-1 + 2^a-2 + 2^a-3 + ... + 4 + 2 + 1 で、2^a+1 より小さいなので O(n) である。

文字列照合のアルゴリズム (15 点)

授業で説明した文字列照合のアルゴリズムの一つを選んで明記の上、その仕組みと特徴を例を使って細かく説明しなさい。

二分木の辿り方 (8 点)

右記の二分探索木の下記の辿り方のノードの順番を書きなさい。

幅優先 (左から)  

行きがけ順  

通り掛け順  

帰りがけ順  

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

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

扱うデータ項目の数が少ないが、急いで実装したいので、できるだけ早く作れるものが欲しい (8 点):

バブルソートを選ぶ。バブルソートは隣同士の項目を比較し、順番が逆でしたら入れ換える、 この作業を繰り返すだけの仕組みになっていますので、実装は非常に簡単で、注意点も殆どない。 しかし計算量は O(n²) なので、本当にデータ項目の数が少ないのか、 これから増える恐れがないのか確かめないといけない。
 
 

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

クイックソートを選ぶ。クイックソートはデータを量ではなくできるだけ乱数で選んだ分割要素を境界に再帰的二に分割する。 最悪の計算量は O(n²) だが、平均では O(n log n)。他にも同じ計算量のアルゴリズムはありますが、 クイックソートはその中で一番早いので、良くライブラリに使用される。注意すべき点は特に分割要素の選択 (三項目の中央値や乱数) だが、他に同値の項目の取り扱いや分割がある大きさ以下 (例: <=10) の時の挿入ソートの使用も実装の向上につながる。
 
 
 

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

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

ハッシュ表の実装公開の問題 (15 点)

公開されたハッシュ表の実装に対し、サービス拒否攻撃 (攻撃されたマシーンが膨大な計算を強いられるため、本来の役割ができない) が報告された。 具体例はユーザのデータがハッシュ表に登録され、 膨大の数の架空なユーザ登録でサービスへの登録やログインがどんどん遅くなったものである。 ハッシュ表の知識を生かし、その攻撃が可能である理由と対策方法を詳しく述べなさい。

ハッシュ表の実相の多くはチェイン法を使用している。 一つだけのチェインがどんどん長くなるともともとのハッシュ表の最大の利点の (挿入、削除など) の O(1) の時間がなくなり、そのチェインにおいて各種の操作が O(n) になる。 普通のデータではそうならないが、実装が公表されていると全てハッシュ値が同じになるユーザ名をわざわざたくさん登録して、効率を悪くすることが出来る。 対策としては万能ハッシュ法を使って、サーバのスタート時点で乱数で決めた値に依存するハッシュ関数を使うのがよい。