計算機科学概論　試験問題

1998 年度夏学期　　1998 年 7 月 28 日　9 時～10 時 10 分（試験時間 70 分）　　担当　川合　慧

試験時間は 70 分です。解答用紙（両面）1 枚、草稿用紙 1 枚です。
テキスト「コンピューティング科学」（書込み貼込み可）および自筆のノートのみ参照可です。
3 問すべてについて解答しなさい。解答は問題番号順でなくても構いません。
問題についての質問は受け付けません。必要なら前提を明記の上解答して下さい。

問題 1.

10 進表記された自然数を位の大きい方から 1 桁ずつ読み込んで、その値が 3 の倍数かどうかを判定するための状態遷移図を構成することを考える。方針は次の通り。

「それまでに読み込んだ数字で表される値」を 3 で割った余りだけを考え、「次の 1 桁」を読んだときにその余りがどう変化するかを見る。

たとえば、整数値 280527 については、中間的な値と（括弧内）は以下のようになる。

2(2)→25(1)→280(1)→2805(0)→28052(2)→280527(0)

以下の問に答えよ。

「状態」および「状態遷移」の概念を簡潔に説明せよ。
上記の方針に沿うものとして、「余り」を表す 3 個の状態 S₀, S₁, S₂ を考え、その間の遷移を図で示せ。遷移の「矢印」には、その遷移を起こした数字（0～9）を添え書きすること。
この図を使って「各桁の数字の和が 3 の倍数ならもとの数も 3 の倍数である」ことを示せ。たとえば 280527 は 2+8+0+5+2+7 = 24 = 8×3 なので 3 の倍数となる。
同じ考え方で「位の小さい方から 1 桁ずつ読み込んで判定する」状態遷移図を作れ。整数値 280527 による遷移を例として示す。
7(1)→27(0)→527(2)→0527(2)→80527(1)→280527(0)

問題 2.

逆問題とは何かを説明し、解くことが易しい例と難しい例とを一つずつあげ、難易に差が出る理由を述べよ。できるだけ身近な例を用いること。

問題 3.

以下のいずれか一項目について 20 行程度で論ぜよ。

計算量: 探索・整列・倍長乗算などを例とした「計算量とそのオーダ」についての説明、及びその研究の情報処理システムにとっての重要性。
信頼性: 情報処理システムを実社会の問題に適用する場合に生じうる問題点と、システムの信頼性及びその向上手法。
以　　上

Presented by KHK.