後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
| 授業 科目 |
データ構造とアルゴリズム | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
下記左側にある計算量を持つプログラム断片を右側に書きなさい。記述は使い慣れたプログラム言語でも疑似コードでもよい。
文法の間違いではなく、計算量があっているかどうかで採点される。変数の宣言は不要。なお、n*n、n*log(n) などの式は使用禁止。
| 例： O(n) |
for (i=0; i<n; i++)
sum += i*i;
|
| O(n2) | for (i=0; i<n; i++)
for (j=0; j<n; i++) {
sum += i*i;
} |
| O(4n) | fun(n) {
if (n<=1) sum += 1;
else for (i=0; i<4; i++) fun(n-1);
} |
| O(n3) | for (i=0; i<n; i++)
for (j=0; j<n; j++)
for (k=0; k<n; k++)
sum += i*j+k;
|
| O(n log n) | for (i=n; i>0; i/=2)
for (k=0; k<n; k++) {
sum += k*i;
}
|
| O(n!) | fun(n) {
if (n<=1) sum += n;
else for (i=0; i<n; i++) fun(n-1);
} |
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
下記の「ハミルトン閉路問題」の課題のため、下記の最初の四つの部分問題のアルゴリズムの設計方針や原理を使った際の、
それぞれのアルゴリズムの概略を提案しなさい。また、それぞれに対し、予想される計算量とその根拠、設計方針を使った場合の問題点について述べなさい。
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 個の辺からなるグラフが与えられ、全ての頂点を1回ずつ通る閉路 を求め、不可能であればその旨を出力する。
遺伝的アルゴリズム / genetic algorithm
@@@
貪欲アルゴリズム / greedy algorithm
@@@
分割統治法 / divide and conquer
@@@
動的計画法 / dynamic programming
@@@
社長に「大事な顧客の多数の大規模なグラフに対し、必ず明日まで解を出してくれ。」と言われたときの返事の概略を書きなさい。なお、ハミルトン閉路問題は調べたら、 NP完全問題であることが判明しました。
大変申し訳ございませんが、この問題は 3-SAT 問題、独立集合問題や巡回セールスマン問題をはじめ多くの問題と同様に NP 困難であり、 いまだに必ず早い時間 (数年以上のではなく、明日まで) で完璧に解けるアルゴリズム (方法) が見つかっていません。 万が一見つかったら世紀の大発見になり、一億円以上の賞金も貰える。 多くの専門家はそれが無理だと思っているが、その証明もいまだできていません。
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
| 授業 科目 |
データ構造とアルゴリズム | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
二分探索木を作成しなさい。入力項目を一つ挿入するごとにその途中経過を書きなさい。 入力項目とその順番: A, O, Y, S, G, M. (6 点)
A A A A A A
\ \ \ \ \
O O O O O
\ \ / \ / \
Y Y G Y G Y
/ / \ /
S S M S
二分探索木の探索の場合の平均計算量 (1 点): O(log n) 二分探索木の探索の場合の最悪の計算量 (1 点): O(n)
最悪の計算量になる条件を説明しなさい。(2 点)
入力される順番がソートされている順番に近い場合、木の高さが O(n) になる場合。
最悪の計算量にならないようにするための対策を説明しなさい。(3 点)
項目の入力や削除の順番は変えられませんので、二分探索木をやめて、何かの平行木 (2-3-4 分木、赤黒木など) やハッシュ表を使うしかありません。
クイックソートの平均計算量 (1 点): O(n log n) クイックソートの最悪の計算量 (1 点): O(n2)
最悪の計算量になる条件説明しなさい。(2 点)
ピボットの選択が何回も範囲の一番小さいや一番大きい項目 (やそれに近い項目) になった場合。
最悪の計算量にならないようにするための対策を説明しなさい。(2 点)
ピボットを乱数で選ぶか、三つの要素の中央値で選ぶ。
計算量とは関係のない、クイックソートの実装にできる工夫を三つ列挙しなさい。(3 点)
二分探索木もクイックソートも平均計算量と最悪の計算量の関係が似ている。しかし、最悪の計算量への対策が違う。
計算量の共通点と対策の違いの根本的な理由を説明しなさい。(3 点)
計算量が違うのはどちらも、分割のところでデータの真ん中あたりの項目を使えるかどうかにかかっています。 しかし、クイックソートの場合、すべてのデータ項目がそろっているので、分割点はアルゴリズム内で選べるのにたいし、二分探索木の場合、挿入の順番は外部に依存しているので、別のデータ構造を使うしかない。
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
下記の三つの事情に合わせて、探索用のデータ構造を実装するように頼まれた。 データ構造を選んで、そのデータ構造の名前、仕組み、探索の計算量、選んだ理由と実装の場合特に注意すべき点を記述しなさい。
この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。)
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)
@@@@
@@@@
一回目の授業では参考書の購入 (又は貸出) と熟読が強く薦められました。熟読した参考書の詳細を書きなさい。参考書を読まなかった場合、その理由を書きなさい。
石畑清著、アルゴリズムとデータ構造、
岩波講座ソフトウェア化学、岩波書店
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
| 授業 科目 |
データ構造とアルゴリズム | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
疑似コードの特徴を五つ列挙しなさい。(5 点)
ラビン-カープアルゴリズムの疑似コードを書きなさい。(20 点)
algorithm: Rabin-Karp
input: pattern p, of length m; text t, of length n; base b; divisor d;
output: position, or nil when not found
pattern_hash ← (∑i=0m-1p[i]*b(m-i-1)) mod d
running_hash ← (∑i=0m-1t[i]*b(m-i-1)) mod d
for i from 0 to (n-m-1)
if pattern_hash = running_hash and pattern = text[i..(i+m-1)]
return i
end_if
running_hash -= text[i] * (b(m-i) mod d)
running_hash *= b
running_hash += text[i+m]
running_hash = running_hash mod d
end_for
end_algorithm
次の 3-SAT 問題を独立集合問題に帰着しなさい。
(￢a ∨ b ∨ ￢c) ∧ (a ∨ ￢b ∨ ￢c) ∧ (￢a ∨ b ∨ c)
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
挿入ソートと選択ソートのアルゴリズムは両方とも二重ループを使用する。外側のループが何回か完了した時点の配列の状態をそれぞれ書きなさい。(6点)
| 完了した回数 | 挿入ソート | 選択ソート | |
|---|---|---|---|
| 開始前 | 4 2 9 7 0 3 8 5 6 1 | 4 2 9 7 0 3 8 5 6 1 | |
| 1 | 2 4 9 7 0 3 8 5 6 1 | 0 2 9 7 4 3 8 5 6 1 | |
| 2 | 2 4 9 7 0 3 8 5 6 1 | 0 1 9 7 4 3 8 5 6 2 | |
| 3 | 2 4 7 9 0 3 8 5 6 1 | 0 1 2 7 4 3 8 5 6 9 | |
| 5 | 0 2 3 4 7 9 8 5 6 1 | 0 1 2 3 4 7 8 5 6 9 |
ソートする配列の長さが n で、外側のループ回数が k 回目のとき、それぞれのアルゴリズムは平均で何回、配列の要素の比較を行っているかと、その理由を書きなさい。(6点)
挿入ソート: (1+k)/2回。なぜかというと、最低1回で最大で k回比較が必要で、すべての回数が同じ割合です。
選択ソート: n-k回。なぜかというと、k回目の外側のループでは n-k+1 この項目の中の最小の項目を見つける必要がある。
ソートする配列の長さが n で、外側のループ回数が k
回目のとき、平均で何回配列の要素を移動しているかとその理由を書きなさい。
なお、項目の交換の場合、一時的に避難する必要があるので、一つの交換のためには三つの移動が必要。(6点)
挿入ソート: k/2+2回。なぜかというと、新しく挿入する項目をよけると戻すには2回、その間の項目をずらすのは最低0回で最大k回の平均となる。
選択ソート: 3回。なぜかというと、見つかった最小の項目と
最初の項目を交換するためです。
アルゴリズムの特徴がよく見えるように授業で使ったアニメーションと同様に、外側のループの回数のちょうど半分が完了した時点での状態を描きなさい。(6点)。
| 挿入ソート | 選択ソート |
|---|---|
[図省略]
|
両方のアルゴリズムが同時にスタートし、終了までに同じ時間を要するという前提で、上記の図のどちらがなぜ先なのか説明しなさい。(4点)
挿入ソートの方の図が先です。なぜかというと挿入ソートの外側のループが回数ごとに重くなるが、選択ソートの方は回数ごとに軽くなる。
アルゴリズムを選ぶにあたって、それぞれの一番大事な特徴を書きなさい。(4点)
挿入ソート: すでに殆ど整列されている場合、早い (「仕上げ磨き」に最適)
選択ソート: 項目の移動は O(n) で少なくて、実行時間の揺れも少ない
後期試験 ・ 2022 年 1 月 27 日 1 時限実施 ・ ページ
| 授業 科目 |
データ構造とアルゴリズム | 学生番号 | 学科 | 学年 | 組 | 番 | フリ ガナ |
評点 | ||||||||
| 氏名 | ||||||||||||||||
| 担当者 | DÜRST, Martin J. | |||||||||||||||
次の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。部分問題 X.11 以降は説明を長くしなさい。