パイプライン制御

H19春試験の問16

すべての命令が5サイクルで完了するように設計された、パイプライン制御のコンピュータがある。20命令を実行するには何サイクル必要となるか。

ア：20　イ：21　ウ：24　エ：25

ええと、問題には20と5という数値しか無いんだし、たぶん ア か ウ でしょう。どっちかなぁ？

IT 用語辞典がやや分かりやすく書いてますが、各段階の処理機構を独立し、前の命令が終わる前に次の命令を処理し始めること だそうです。

小難しく考えず、スレッド開始キューみたいな感じと覚えておけば良いかも。って、分かり辛いかな。

これも文章よりは、図で覚えるのが良いと思います。

パイプライン制御

時間	1	2	3	4	5	6	7	8	9
処理A	■	■	■	■	■
処理B		■	■	■	■	■
処理C			■	■	■	■	■
処理D				■	■	■	■	■
処理E					■	■	■	■	■

データの並び替え ( ソート )

H19春試験の問11

n個のデータを整列するとき、比較回数が最悪の場合でO（n＾2）で、最良の場合でO（n）となるものはどれか。

ア：クイックソート　イ：単純選択法　ウ：単純挿入法　エ：ヒープソート

ええと、ソートアルゴリズムなんて忘れたよ。
C言語を始めたときに、課題としてやったぐらい。
たいていの場合、qsort(callback) で間に合ってたしなぁ。

さて、色々なソート方法がありますが、バブル、選択、挿入、クイック、マージ、ヒープ の 6種類について、考え方をざっくりと読んでおいた方が良さそうです。

このページ ( Akademeia ) が、解りやすくまとまってると思います。

まぁ、興味＋時間があれば、適当にプログラムしてみるのも良いかもしれません。

私としては、 1問しか出題されないだろうし、要点だけで十分かと思います。まぁ、今回の問題のように 平均計算量 と 最大計算量 を覚えておくのが有効でしょう。

ソート	平均計算量	最大計算量
バブルソート	O(ｎ^2)	O(ｎ^2)
選択ソート	O(ｎ^2)	O(ｎ^2)
挿入ソート	O(ｎ)	O(ｎ^2)
クイックソート	O(nlogn)	O(ｎ^2)
マージソート	O(nlogn)	O(ｎlogn)
ヒープソート	O(nlogn)	O(ｎlogn)

BNF ( BN記法・バッカス ナウア記法 )

H19春試験の問8

あるプログラム言語において...。これを BNF で定義したとき、aに入るものはどれか。

<digit>::=0|1|2|3...
...

BNFかぁ。聞いた事はあるある。

問題から言えば、<digit>::=0|1|2|3... ってところが、BNF なんだろうとは想像つくし、意味も想像できるなぁ。

一応、BNFの定義。

・記号 ::== が左辺と右辺の区切りを表す。
・記号 < と > で囲まれた範囲はメタ変数。
・右辺の中で、記号 | が「または」の意味で使われる。

最近は、EBNFが使われているらしいけど、亜種や変種が多くては、設問とするのは難しいのじゃないかなぁ。

無視しても良いかなぁ。

オートマトン

H19春試験の問7

図は、偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり...

オートマトン・・・？　自動の羊肉？

人の名前かと思ったら、れっきとした英語のようです。参考：Wikipedia

IT用語辞典 によれば、状態に応じて、入力値を処理し出力する装置らしい。

・・・状態遷移を実装したプログラムって思えば良いか。

ってか、状態遷移そのものだよね。

図はクセがありますが、オートマトンは無視してもよさそうです。

単純マルコフ過程

H19春試験の問３

表は...。天気の移り変わりが単純マルコフ過程であると考えたとき、雨の2日後が晴れである確率は何％か。

誰ですか？マルコフって。

しかも、単純って？

ぐぐると、経過には関係なく、現在の状態によって、次に起こる事象の確率が決まるということらしいです。

意味は分かりました。・・・で？

なにやら小難しいですが、情報処理試験で確率を計算させる問題としては、至極当たり前の前提条件です。そうでない場合の計算方法なんか思いつきませんし、たぶん試験時間が足りないでしょう。

この単語は無視。覚えなくて良さそうです。

さよなら、マルコフ。