[問01-10]H28秋期基本情報技術者試験解説

ここでは例として「00101110」という8ビット列を用います。
「00001111」との演算で、この下4桁「1110」が変化しないものを選びます。

両ラインで同じ製品を製造しているため、できたものを見ても、それがどちらで製造されたか特定することはできません。そのため、AとBそれぞれの不良品率から予想します。

以上の不良品率を比べて見ると、
0.012 : 0.004 = 3 : 1

つまり、不良品がラインAで製造された確率は、「3 / 4 = 0.75(75%)」となります。

POINT

300円の商品を販売する自動販売機の状態遷移図はどれか。ここで、入力と出力の関係を“入力/出力”で表し、入力の“a”は“100円硬貨”を、“b” は“100円硬貨以外”を示し、S0〜S2 は状態を表す。入力が“b”の場合はすぐにその硬貨を返却する。また、終了状態に遷移する際、出力の“1”は商品の販売を、“0”は何もしないことを示す。

[ア]

[イ]

[ウ]

[エ]

状態遷移図は頻繁に出題される問題のひとつです。整理して考えましょう。
まず図中の「a/0」「b/0」は、(入力)/(出力)を表しています。
aとbが入力、0と1が出力です。それぞれの意味を確認します。

つまり、「a/1」は「100円硬貨を入れて(入力) / 商品を販売(出力)」。
「b/0」は「100円以外の硬貨を入れて(入力) / 何もしない(出力)」。
となるわけです。

問題には、「300円の商品を販売する」とあります。
すなわち、「a」(100円投入)が3回(300円)呼び出されて、商品が販売(1)されるわけです。
投入金額が300円未満のときは、追加の硬貨を待つわけですから、何もしない(0)ことになります。

以上より、300円で商品を販売する状態遷移図は、初期状態(S0)から、「a/0」(100円投入/何もしない)が2回続いた(200円投入)あと、「a/1」(100円投入/商品販売)に遷移する(300円で商品販売し、初期状態に戻る)ものとわかります。この要件を満たすのは、選択肢アです。

100円未満の硬貨が投入された場合は、何もしません。おそらく払い戻されるのでしょう。この状態遷移図は、まさしくガチャポン(ガチャガチャ)ですね。

1ビットで表現できるのは、「1」か「0」の2通りでした。2ビットは4(2²)通り、3ビットは8(2³)通り、4ビットは16(2⁴)通り。
つまり、nビットで表現できるビットパターン数は、 2ⁿ 個になります。

32ビットのパターン数は、2³²、24ビットのパターン数は2²⁴。
倍数計算では、この乗数部分に注目します。

2³²÷2²⁴=2^32-24=2⁸=256。

よって「256倍」が正解です。

1. まずその信号(振幅、周波数など)の強度を連続的に測定し、(標本化)
2. それをコンピュータが理解できる形(整数などの離散値)にし、(量子化)
3. 2進数にして、あとで元の(類似の)信号に戻せるよう変換します。(符号化)

自然界の音は、空気の振動です。
これをそのまま機械に記録することはできないので、コンピュータの得意な「数字」に置き換えます。空気の振動はやがては消えてしまいますが、数字はデータとして記録・送信することができます。

A/D(アナログ→デジタル)に用いられる機器には、マイクがあります。
D/A(デジタル→アナログ)に用いられる機器には、スピーカーがあります。

CHECK POINT

2分探索木になっている2分木はどれか。

[ア]

[イ]

[ウ]

[エ]

2分探索木の構造に関する問題です。

基礎的な制約 「左の子孫の値≦親の値≦右の子孫の値」 が解答のポイント。

[ア]	「15」の右の子孫の値が親より小さいため間違い。
[イ]	条件を満たすため、2分探索木である。
[ウ]	「16」の右の子孫の値が親より小さいため間違い。
[エ]	「18」の右の子孫および「19」の右の子孫の値が親より小さいため間違い。

Binary_search_tree(public domain)-wikipedia

整数x,y(x>y≧0)に対して、次のように定義された関数 F(x,y)がある。F(231,15)の値は幾らか。ここで、x mod yはxをyで割った余りである。

[ア]2
[イ]3
[ウ]5
[エ]7

「再帰的」とある通り、xが確定するまで上記の式に代入を繰り返します。
右辺にある(y=0のとき)(y>0のとき)という条件に注目しましょう。

 F(231, 15)
=F(15, 231 mod 15)
=F(15, 6)

=F(6, 15 mod 6)
=F(6, 3)

=F(3, 6 mod 3)
=F(3,0)
=3

y>0
F(y, x mod y)
x = 15, y= 6

y>0 -> F(y, x mod y)
x = 6, y = 3

y>0 -> F(y, x mod y)
x = 3, y = 0
y=0 -> x

対して「動的ページ」は、アクション(ボタンクリックなど)や利用者情報、接続時間などによって、表示するコンテンツを動的に生成し表示させます。

例えば、Amazonなどのショッピングサイトを利用する際、画面の端にはアカウント名が表示されているはずです。私のために開発者があらかじめ記述してくれたのでしょうか？もちろん違います。そのページは、あなたのユーザ情報およびその購買履歴など様々な情報から動的に生成されたWebページなのです。

問題は、この「動的処理」がどこで行われるかという点です。
これを「サーバ側」で動作させる手法には、サーブレットやJSPなどがあります。

対して「クライアント側(ブラウザ)」で動作させる手法には、Javaアプレットなどがあります。
ブラウザで動的処理を行う、というのはイメージが難しいかもしれませんが、例えば「Radish Network Speed Testing」など、回線速度測定ページなどではJavaアプレットが用いられ、実行の承諾が表示されます。
Radish Network Speed Testing

CHECK POINT

主記憶のデータを図のように参照するアドレス指定方式はどれか。
[ア]間接アドレス指定
[イ]指標アドレス指定
[ウ]相対アドレス指定
[エ]直接アドレス指定

間接アドレス指定方式のアドレス部では、「処理対象データが格納されている記憶場所のアドレスが格納されている記憶場所のアドレス」(H28秋季応用技術者09)が指定されます。

問題の図は、対象データを間接的に指定しているので、用語を知らなくても直感で正解できる問題でしょう。

CHECK POINT

「投機」という言葉に馴染みがなければ、”speculative”の別の意味である「思索的な、推論的な、不確かな」の意味で考えると理解しやすいでしょう。

「投機実行」は、CPU処理高速化のため「予測した分岐先命令をあらかじめ実行しておく」手法です。

CPUは、複数の命令を並行実行するなどして処理の高速化を図ります。しかし、プログラムの途中に「条件分岐」があると、当然その「条件」を得るまでは、[処理A]か[処理B]どちらを実行するべきか判断できません。せっかく並行実行したのに、分岐点で処理が足止めされてしまうわけです。

投機(speculative)に「推論的な、不確かな」という意味があるとおり、投機実行では「条件」が確立していない段階で、見切り発車的に予測分岐先の処理を実行します。これにより、 並行処理を分岐点より先に進めることができる のです。もし予測が当たっていたら、その処理が適用され、外れた場合は、見切り発車した分の処理を破棄して正しい分岐先の命令を実行します。

例えば、「ごはん派 or パン派」という条件分岐があります。
過去の実行履歴から85%の確率で「ごはん派」が選ばれることがわかっています。
投機実行では、分岐点に到達する前に、あらかじめ「ごはん派」の先の処理を進めます。やはり「ごはん派」に分岐しました。予測が的中したことで、命令処理全体の実行時間を短縮することができました。

仮に誤って実行確率の小さい「パン派」を実行してしまうと、結局処理が巻き戻ってしまいます。そのため投機実行では、過去の実行履歴など、分岐予測の精度が重要なポイントになってきます。

CHECK POINT

2016/11/17 問2、問3の解説を追加