平成24年度秋季解答

問題1

全体集合S 内に部分集合A とB があるとき、A ∩ B に等しいものはどれか。
ここで、A ∪ B はA とB の和集合、A ∩ B はA とB の積集合、A はS におけるA の補集合、A -B はA からB を除いた差集合を表す。

ア	A -B
イ	(A ∪ B )-(A ∩ B )
ウ	(S -A ) ∪ (S -B )
エ	S -(A ∩ B )

解答：ア

＜解説＞

論理式A ∩ B をベン図で表現すると次のようになる。

ア～エの論理式をベン図で表すと次の様になる。

ア	○
イ	×
ウ	×
エ	×

したがって、アが正解である。

問題へ

問題2

4ビットから成る情報ビットx1x2x3x4に対して、
　(x ₁ + x ₂ + x ₃ + x ₅) mod 2 = 0
　(x ₁ + x ₂ + x ₄ + x ₆) mod 2 = 0
　(x ₂ + x ₃ + x ₄ + x ₇) mod 2 = 0
を満たす冗長ビットx ₅x ₆x ₇を付加した符号x ₁x ₂x ₃x ₄x ₅x ₆x ₇を送信する。
受信符号y ₁y ₂y ₃y ₄y ₅y ₆y ₇が、送信符号と高々1ビットしか異ならないとき、
　(y ₁ + y ₂ + y ₃ + y ₅) mod 2
　(y ₁ + y ₂ + y ₄ + y ₆) mod 2
　(y ₂ + y ₃ + y ₄ + y ₇) mod 2
がそれぞれ0になるかどうかによって、正しい情報ビットx ₁x ₂x ₃x ₄x を求めることが可能である。
y ₁y ₂y ₃y ₄y ₅y ₆y ₇ = 1100010であるとき、正しい情報ビットはどれか。
ここで、a mod b は、a を b で割った余りを表す。

ア	0100
イ	1000
ウ	1100
エ	1101

解答：エ

＜解説＞

受信ビット列y ₁y ₂y ₃y ₄y ₅y ₆y ₇＝ 1100010を式に代入し、その正誤を確認する。

値を代入した結果、式2と式3が誤りとなる。

したがって、式2と式3に共通に含まれるy ₄が誤って伝えられた情報ビットであると特定できる。

それに伴いy ₄=0→1となり正しい情報ビット列は1101となる。

よってエが正解である。

問題へ

問題3

配列を用いてスタックを実現する場合の構成要素として、最低限必要なものはどれか。

ア	スタックに最後に入った要素を示す添字の変数
イ	スタックに最初に入った要素と最後に入った要素を示す添字の変数
ウ	スタックに一つ前に入った要素を示す添字の変数を格納する配列
エ	スタックの途中に入っている要素を示す添字の変数

解答：ア

＜解説＞

スタックとは、ある場所に格納したデータを、新しく格納した順に取り出すようにする方式。一番古く格納されたデータが一番最後に取り出される、LIFO（Last In, First Out：後入れ先出し）型のバッファのことである。

1. スタックに新しい値を格納する場合は、最後に値が格納された領域の1つ上の領域に格納する。
2. 新しい値の格納により最後に値が格納された領域が一つ上に移動する。
3. スタックから値を取り出すときは、最後に値が格納された領域から取り出す。
4. 値を取り出すことにより最後に値が格納された領域の位置が１つ下に移動する。

したがって、スタックへの値の出し入れを表現するには、最低でも最後に値が格納された領域を示す添え字を用いればよい。したがってアが正解である。

問題へ

問題4

命令を並列実行するためのアーキテクチャであって、複数の命令を同時に実行するとき、命令を実行する演算器をハードウェアによって動的に割り当てる方式はどれか。

ア	SMP
イ	VLIW
ウ	スーパスカラ
エ	スーパパイプライン

解答：ウ

＜解説＞

ア	×	SMP(Symmetric Multiple Processor)は、複数のCPUが同等な立場で処理を分担するマルチプロセッサ手法。「対称型マルチプロセッサ」とも訳される。
イ	×	VLIW(Very Long Instruction Word：超長命令語)とは、CPUが命令を並列実行するためのアーキテクチャーの一種。
ウ	○	スーパスカラとは、プロセッサの中に複数の処理系統(パイプライン)を用意し、複数の命令を並列に処理することである。
エ	×	スーパーパイプラインとは、マイクロプロセッサ(MPU)の高速化手法の一つで、命令を細かい工程に分解して並列に実行するパイプライン処理を、より細分化・多段化したものである。

問題へ

問題5

キャッシュメモリへの書込み動作には、ライトスルー方式とライトバック方式がある。 それぞれの特徴のうち、適切なものはどれか。

ア	ライトスルー方式では、データをキャッシュメモリだけに書き込むので、高速に書込みができる。
イ	ライトスルー方式では、データをキャッシュメモリと主記憶の両方に同時に書き込むので、主記憶の内容は常に最新である。
ウ	ライトバック方式では、データをキャッシュメモリと主記憶の両方に同時に書き込むので、速度が遅い。
エ	ライトバック方式では、読出し時にキャッシュミスが発生してキャッシュメモリの内容が追い出されるときに、主記憶に書き戻す必要が生じることはない。

解答：イ

＜解説＞

書込み命令が実行された時に、キャッシュメモリと主記憶の両方を書き換える方式のことを、ライトスルー方式(write through) ，キャッシュメモリだけを書き換えておき、主記憶の書き換えはブロックの入れ替え時に行う方式のことを、ライトバック(write back) 方式という。

ライトスルー方式

• キャッシュへの書込みと同時に主記憶にも書き込む方式
• 書き込みの高速化はできない

ライトバック方式

• キャッシュから追い出された時点で主記憶へ書き込む方式
• 書込みも高速化できる。

したがって、イが正解である。

問題へ