計算機科学概論 試験問題
1997年度冬学期 1998年2月12日 10時50分〜12時00分 担当 川合 慧
- 試験時間は 70 分です。
解答用紙（両面）1 枚、草稿用紙 1 枚です。
- テキスト「コンピューティング科学」（書込み貼込み可）
および自筆のノートのみ参照可です。
- 3 問すべてについて解答しなさい。
解答は問題番号順でなくても構いません。
- 問題についての質問は受け付けません。
必要なら前提を明記の上解答してください。
問題 1
二つのデータ集合 A と B とが、データ列
a1, a2, ..., an
および
b1, b2, ..., bm
として与えられている。
この両者の「どちらにも含まれている要素」をすべて求めるための、
以下の 2 種のアルゴリズムについて設問に答えよ。
ただし、大きさ p のデータの整列の計算量は
O (p log p) であるものとする。
(1)何ら前処理をせずに、A の個々の要素が
B の中にあるかどうかを探す。
(2)B を整列してから、A の個々の要素が
B の中にあるかどうかを探す。
- それぞれのアルゴリズムの計算量を求めよ。
オーダの概念による概算でよい。
- この二つのアルゴリズムの利害得失を、データの大きさ
（n と m）を考慮に入れて論ぜよ。
問題 2
3 個のランプ付きボタンが一列に並んだ装置があり、
次のように振舞うという。
あるボタンを押すと、そのボタンのランプの状態（点灯・消灯）
が反転するとともに、そのボタンの隣のランプの状態も変化する。
真中のボタンには「隣」が 2 個あることに注意すること。
最初はランプがすべて消えているものとする。
状態遷移の考え方を使って以下の設問に答えよ。
- 真中のランプだけを点灯させるための、
ボタンを押す必要最小回数を求めよ。
- 真中のランプだけを点灯させるためには、真中のボタンを最低
1 回は押さなければならないことを示せ。
- a、b の解答方法を例として、
状態の考え方の問題解決における役割について論ぜよ。
問題 3
以下に示す項目のいずれか一つについて 10 行以内で説明せよ。
資料の丸写しではなく、講義を聴講して得た知見をもとにして、
できるだけ身近な題材を使用して論ずること。
- 計算モデル
- 2 進法と計算機構
- ソフトウェアの信頼性
- 逆問題とその解法
Presented by KHK.