計算機科学概論 試験問題
1997 年度夏学期 1997 年 7 月 29 日 9 時〜10 時 30 分 担当 川合 慧
- 解答用紙は両面のもの 1 枚、草稿用紙 1 枚です。
- テキスト「コンピューティング科学」および自筆のノート
（書込み貼込み可）のみ参照可です。
- 4 問すべてについて解答しなさい。
- 問題についての質問は受け付けませんので、
必要なら前提を明記の上解答して下さい。
問題 1
64 ビットの 2 進数の全加算器を、
1 ビットの全加算器を部品として作ることを考える。
- 1 ビットの全加算器の機能を説明せよ。
- 64 個の全加算器を使って
64 ビットの加算器を構成する方法を示せ。
- b. の方法の演算所要時間に関する問題点を示せ。
- より多数の全加算器を用いて、
b. よりも高速な加算器を構成する方法を示せ。
高速化の原理（高速になる理由）を明記すること。
問題 2
再帰（recursion）とは何かを例を用いて説明し、
それがアルゴリズム構築に果たす役割について述べよ。
問題 3
以下に示すアルゴリズムが a1、a2、
...、an（n > 0）の最大値を
a1 に求めることを示せ。
ループ不変量の考え方を使うこと。ここでデータは整数値であるものとする。
i ← 1;
while i > n {
i ← i + 1;
if ai > a1
then {a1 と
ai を交換する}
}
問題 4
火星探査機「マーズパスファインダー」では、従来の「逆噴射による軟着陸」
の代わりにエアバッグによる「放り投げ着陸方式」を、最新鋭の処理装置
（CPU）の代わりに世代遅れだが消費電力の少ない処理装置を、
それぞれ用いた。探索計画全体を「問題」の、実現方法を「アルゴリズム」
の、それぞれ例と見倣すことによって、
アルゴリズムの多様性について解答用紙 20 行程度で論じよ。
Presented by KHK.