カテゴリ: 3.コンピュータの基礎理論

 

1.CRC

CRCは、「送信側では、生成多項式を用いて検査対象のデータから検査用のデータを作り、これを検査対象のデータに付けて送信する(H16NW午前問31)」ものです。

2.CRCの過去問 

CRCに関して、ここ最近の応用情報技術者試験では、あまり問われていません。
(1)H21春AP午前問4

問4 誤り検出方式であるCRCに関する記述として,適切なものはどれか。
ア 検査用のデータは,検査対象のデータを生成多項式で処理して得られる1ピットの値である。
イ 受信側では,付加されてきた検査用のデータで検査対象のデータを割り,余りがなければ送信が正しかったと判断する。
ウ 送信側では,生成多項式を用いて検査対象のデータから検査用のデータを作り,これを検査対象のデータに付けて送信する。
エ 送信側と受信側では,異なる生成多項式が用いられる。




正解:ウ

(2)H22秋FE午後問3

問3 CRC(巡回冗長検査)に関する次の記述を読んで,設問1~3に答えよ。
 CRCは,誤り検出方式の一つである。送信側でデータに誤り検出符号(以下,符号という)を付加して送信し,受信側で検査することによって,転送の際の誤りの有無を判断する。

設問1 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。
 CRCを採用したパケット転送システムでは,送信側でパケットに符号が付加され,受信側で誤りの有無を検査する。受信側で誤りが検出されると,送信側に対して該当パケットの再送を要求する。100個のパケットに格納されたデータの転送において,受信側が実際に受信したパヶツトが,再送されたパケットも含めて[    ]個であったとすると,受信したパケットの20%から誤りが検出されたことになる。ここで,送信したパケットは必ず相手に届くものとする。また,パケットの再送要求は誤りなく届き,再送要求には必ず応じるものとする。

解答群
ア 100    イ 102    ウ 120    エ 125

正解は、エです。

設問2 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

 任意の長さのビット列の符号を求める計算手順を次に示す。ここで,符号の長さはnビットとする。

〔nビットの符号を求める計算手順〕
 (1)左端及び右端のビットが1である(n +1)ビットのビットパターン(以下,マスクという)を定める。
 (2)符号計算対象のビット列の右端にnビットの0を付加したビット列を作る。
 (3)(2)で作ったビット列に対して次の操作を行う。
  ① ビット列の左端から調べ,最初に値が1であるビットの位置pを見つける。
  ②pを左端としp+nを右端とする部分ビット列に対し,マスクで排他的論理和(XOR)を取る。
  ③ ビット列の右端nビット以外がすべて0になるまで,①及び②を繰り返す。
 (4)(3)の操作で得られたビット列の右端nビットが符号となる。

  図に,マスクが101のときの符号(2ビット)を計算する例を示す。

22-FE問3-1

  図 マスクが101のときの符号(2ビット)を計算する例

 マスク101で計算した,符号計算対象のビット列0010 0110の2ビットの符号は[    ]である。

解答群
ア 00    イ 01    ウ 10    エ 11

正解は、イです。

設問3 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

  誤りの有無の検査は,次の手順で行う。

 〔誤りの有無の検査手順〕
(1)受信したビット列に対して,送信側で符号の計算に利用したものと同じマスクを使い,〔nビットの符号を求める計算手順〕の(3)と同じ処理を行う。
(2)右端nビットの値によって,誤りの有無を判断する。

 受信したビット列(符号が付加されたビット列)を,誤りの有無の検査手順に従って検査すると,誤りがなければ最後に残った右端nビットの値は[    ]になる。このことは次の手順で説明できる。

〔手順〕
(1)符号計算対象のビット列を一つの数値Dと見ると,符号Cは次の式で表せる。
22-FE問3-2
(2)〔誤りの有無の検査手順〕で得られた結果の右端nビットの値Tは,次の式で表せる。
22-FE問3-3

(3)式②を変形すると次の式となる。
22-FE問3-4

(4)式①と式③によって,
    [  b  ]=T
となる。

 マスク101で計算した符号を右端に付加したビット列1001001101を受信した。このピット列には[  c  ]。

aに関する解答群
ア すべてのビットが0  
イ すべてのビットが1
ウ 符号と同じ
エ 符号の各ビットを反転させたものと同じ

bに関する解答群
22-FE問3-5

cに関する解答群
ア 誤りが含まれる
イ 誤りは含まれない
ウ 誤りが含まれるか否かは判断できない




正解は、

a ア
b エ
c ア です。

こちらも参考にしてください。
http://sm.seeeko.com/archives/15876986.html

小学校ではこんな問題があったと思います。
30人の生徒がいます。野球を好きな人が15人、サッカーが好きな人が10人、両方好きな人が4人いました。では、両方嫌いな人は何人でしょう。  
これをベン図で表すと、以下のようになります。
1
応用情報技術者試験を勉強する成子 

なぜベン図というのですか?
イギリスのベン(Venn)さんが考案したからです。レントゲンを発明したのがレントゲンさんであるのと同様です。
さて、論理和(OR)、論理積(AND)、排他的論理和(XOR)を覚えましょう。

これ以外には、否定も覚えておきましょう。ベン図では、補集合と言います。

論理和(OR)
上でいう、野球とサッカーのどちらかが好きな人です。
合計20人です
情報処理技術者試験では、A∪B、A∨B、A+B、などの表現が使われます。「AまたはB」と読みましょう。
ベン図と真理値表は、以下です。
ベン図 真理値表
OR2 OR

論理積(AND)
上でいう、野球とサッカーの両方が好きな人です。
4人います。
ベン図真理値表
AND2AND  

情報処理技術者試験では、A∩B、A∧B、A・B、などの表現が使われます。「AかつB」と読みましょう。
応用情報技術者試験を勉強する成子 

子供の頃に、AかつBだから、「つ」と「∩」を関連して覚えるといいと言われました。
試験では、問題文に表記の解説がなされますが、覚えておくのはいいと思います。

否定(NOT)
「じゃない」という意味です。
ベン図真理値表
後日記載NOT  

排他的論理和(XOR)
上でいう、どちらか一方だけが好きな人です。
16人います。
ベン図真理値表
haita2haita  

否定的論理積(NAND)
ANDの反対
以下も参照ください。
http://sm.seeeko.com/archives/15876986.html

では、ベン図に関して、過去問(H25年秋FE午前問1)を見てみましょう。
ベン図

正解はウです。
面倒ですが、一つ一つ丁寧に書いていくのが近道です。

論理演算において、いくつかの公式があります。それは、結合法則や分配法則、ド・モルガンの法則です。
応用情報技術者試験を勉強する成子 

結合法則と分配法則は、中学校の数学か何かで習った記憶があります。

はい、それとほぼ同じです。
実際に見てみましょう。

 

1.結合法則

これは、過去問(H29年春AP午前問1)でズバリ問われています。
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)

これは、数学における足し算や掛け算の以下の公式が成り立つのと同じです。
(A+B)+C=A+(B+C)
(A×B)×C=A×(B×C)

2.分配法則

A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C)

こちらも1つめは数学と同様です。
A×(B+C)=(A×B)+(A×C)

2つ目は、数学の公式とは違いますね。以下の式は成り立ちません。
A+(B×C)=(A×B)+(A∪C)

3.ド・モルガンの法則

aaa









分かりにくいですね。
ベン図を描いてみると、たしかに一致します。
aaaa
言葉で考えてみましょう。小学生にて、Aが野球が好き、Bがサッカーが好きと仮定します。
上の公式で考えます。
左辺:野球とサッカーの両方が好きではない人
右辺:野球が嫌い、または、サッカーが嫌いのどちらかの人
言葉で表現するとわかりにくいのですが、左辺も右辺も同じ人が対象になります。(以下の○の人が対象)
ben2

 

4.論理演算の公式の過去問を解いてみよう

(1)平成29年春期 午前問1

ben






順番にベン図を描くのが近道かも知れませんね。
すべて成立します。
【正解】エ

(2)H25春AP午前問2

問2
1-3H25h-2





【正解】ア

(3)H28春AP午前問1

問1 nビットの値L1,L2がある。次の操作によって得られる値L3は,L1とL2に対するどの論理演算の結果と同じか。
〔操作〕
(1)L1とL2のビットごとの論理和をとって,変数Xに記憶する。
(2)L1とL2のビットごとの論理積をとって更に否定をとり,変数Yに記憶する。
(3)XとYのビットごとの論理積をとって,結果をL3とする。
ア 排他的論理和   イ 排他的論理和の否定
ウ 論理積の否定   エ 論理和の否定






【正解】ア

(4)H27秋AP午前問1

問1 0以上255以下の整数nに対して,
1-3H27a-1
と定義する。 next (n)と等しい式はどれか。ここで,x AND y 及び x OR yは,それぞれxとyを2進数表現にして,桁ごとの論理積及び論理和をとったものとする。
ア (n +1)AND 255   イ (n +1)OR 256
ウ (n +1)OR 255    エ (n +1)AND 256






【正解】ア

(5)H27秋AP午前問2

問2 集合A,B,Cに対してA∪B∪Cでが空集合であるとき,包含関係として適切なものはどれか。ここで,∪は和集合を,∩は積集合を,XはXの補集合を,また, X⊆YはXがYの部分集合であることを表す。
ア (A∩B)⊆C   イ A∩B)⊆C   
ウ ((span style="text-decoration: overline;">A∩B)⊆C   エ ((span style="text-decoration: overline;">A∩B)⊆C






【正解】エ

(6)H26秋AP午前問2

問2 4nビットを用いて整数を表現するとき,符号なし固定小数点表示法で表現できる最大値をaとし, BCD (2進化10進符号)で表現できる最大値をbとする。nが大きくなるとa/bはどれに近づくか。
ア (15/9)×n
イ (15/9)n
ウ (16/10)×n
エ (16/10)n






【正解】エ

(7)H25秋AP午前問4

問4 論理式P,Qがいずれも真であるとき,論理式Rの真偽にかかわらず真になる式はどれか。ここで,“ ̄”は否定,“V”は論理和,“∧”は論理積,“→”は含意(“真→偽”となるときに限り偽となる演算)を表す。
1-3H25a-4






【正解】エ

(8)H28秋AP午前問1

問1 8ビットのデータX及びyの値をそれぞれ16進表現で0F,F0とするとき,  8ビットのデータAの下位4ビットを反転させ,上位4ビットを0にする論理式はどれか。
1






【正解】ウ
まず、XとYが2進数でどんな値なのでしょうか。慣れている人は、0FとF0を見て、00001111、11110000とすぐに分かったことでしょう。

念のため、一つずつ変換してみます。
X:0F(16進数)⇒15(10進数)⇒00001111(2進数(8ビット))
Y:F0(16進数)⇒240(10進数)⇒11110000(2進数)
たとえばAを11010111とすると、「8ビットのデータAの下位4ビットを反転させ,上位4ビットをOにする」と、
00001000 になります。
選択肢のなかでどれが正しいのかは、実際にやってみましょう。
たとえば、アです。わかりやすいように表にしましたが、このような図を書かなくても、A・Xを求めて、その否定を求めることはそう難しくないと思います。
2 
ウは以下のようになります。よって、正解選択肢です。
3

 

1.符号化とは

広義の「符号化」とは、アナログデータをデジタルデータにすることです。狭義の「符号化」に関しては、音声の符号化(A/D変換) における、「標本化,量子化,符号化の3段階で処理」で考えます。詳しくは以下に記載しています。

nw.seeeko.com

2.符号化に関する過去問

■H28春
問4 a,b,c,dの4文字から成るメッセージを符号化してビット列にする方法として表のア~エの4通りを考えた。この表はa,b,c,dの各1文字を符号化するときのビット列を表している。メッセージ中でのa,b,c,dの出現頻度は,それぞれ50%,30%,10%,10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって,ビット列の長さが最も短くなるものはどれか。
H28h-4



【正解】ウ

 

3.参考(ラングレス法)

可逆圧縮アルゴリズムの一つであるランレングス法について過去問(H21春FE午後問1)を紹介します。

問1 画像データの符号化に関する次の記述を読んで,設問1~3に答えよ。

 図1は,8×8画素の白と黒だけで色分けされた2値画像の例である。画素を1番上の行の左から右へ,次に2番目の行の左から右へと順に1画素を1ピットで,白を0,黒を1で表すと,図2のように64ビットのピット列で表現することができる。
H21春FE午後問1図1・図2
(1) 図2のビット列を,同じ値が連続している部分(以下,ランという)ごとに区切り,各ランをその連続する個数(以下,ランレングスという)で表すことによって,少ないビット数でのピット列表現に書き換えることができる。図2では,左上から数えて0が27個,1が27個,0が10個の順に連続しているので,27,27,10という情報を使った表現に書き換える。これを,ランレングス符号化という。

(2) 1番上の行の左端の画素は白で始まるものとする。ただし,その画素が黒の場合は,先頭に0個の白があるものとして符号化を行う。

(3) ランレングス符号化の方法は,次のとおりである。
 ① ランレングスをnとし,nを2進数で表現したときのけた数をmとする。ただし,常にm≧2となるように,n =0の2進数表現を00,n =1の2進数表現を01とする。
 ② nビットのランを図3のビット列に書き換える。
H21春FE午後問1図3
(4) 図2の例では,最初は0が27個連続しているので,n =27である。27を2進数で表現すると11011 (5けた)となり,m =5である。m-2=3なので,けた数情報は111である。したがって,この部分の符号化後のピット列表現は111011011となり,9ピットで表現できる。

(5) 表にn,m及び符号化後のピット列を示す。
H21春FE午後問1 表 ビット列
設問1 表中の[    ]に入れる正しい答えを,解答群の中から選べ。

 aに関する解答群
 ア 100
 イ 0100
 ウ 10100
 エ 110100

 bに関する解答群
 ア 14
 イ 15
 ウ 16
 エ 17

正解は、
a ウ
b イ
です。

設問2 図2の64ビットのビット列をランレングス符号化すると,何ビットで表現できるか。正しい答えを,解答群の中から選べ。

解答群
ア 22
イ 23
ウ 24
エ 25

正解は、エです。

設問3 ランレングス符号化後のビット列が,次のとおりであったとする。このビット列を復号した2値画像として正しい答えを,解答群の中から選べ。

 000111011111111011111010

解答群
H21春FE午後問1 設問3 解答群

正解は、エです。

 

 

1.信号処理に関して

 信号処理に関して、応用情報技術者試験シラバスでは、以下の記載があります。

(1)信号処理
アナログ波形を分析して,雑音を除去し,特徴を抽出する信号処理の考え方,仕組みを理解する。
用語例 DFT(Discrete Fourier Transform:離散フーリエ変換),FFT(Fast Fourier Transform:高速フーリエ変換),インパルス応答,フィルタ(ローパスフィルタ,ハイパスフィルタ,バンドパスフィルタ,ディジタルフィルタ),サンプリング定理,D/A 変換,A/D 変換

2.A/D変換

 会話や通話はアナログの波です。これを、TCP/IP上で通信をするには、0と1で表されるデジタル化をする必要があります。つまりアナログ(Analog)からデジタル(Digital)に変換する処理が必要です。
 A/D変換(アナログ/デジタル変換)に関しては、以下に記載しています。
http://nw.seeeko.com/archives/50493771.html

3.A/D変換に関する過去問

(1)平成28年秋期 午前

問22 音声を標本化周波数10 kHz,量子化ビット数16ビットで4秒間サンプリングして音声データを取得した。この音声データを,圧縮率1/4のADPCMを用いて圧縮した場合のデータ量は何kバイトか。ここで,1kバイトは1,000バイトとする。

ア 10  イ 20  ウ 80  エ 160 



標本化周波数10 kHzなので、1秒間に10k回のデータが存在します。量子化ビット数16ビットなので、1回のデータ量は16ビットです。
それを4秒間サンプリングし、1/4の圧縮をしたので、全部をかけ合わせます。
10k×16×4÷4=160kbit

これをバイトに直すために8で割ると、20kバイトです。

正解:イ

(2)H23秋FE午後問1

問1 A/D変換に関する次の記述を読んで,設問1~3に答えよ。

 A/D変換とは,アナログ信号をディジタル信号に変換することであり,標本化,量子化,符号化の3段階で処理する。直流の電圧を例にnビットのA/D変換を説明する。
(1)標本化
 標本化では,時間的に連続したアナログ信号である電圧を一定の時間間隔で測定する。図1では,時間軸をt0,t1,…と等間隔dで区切り,各時刻での電圧をv(t1),v(t1),…と表す。
2011h23a_fe_pm_qs_1

2011h23a_fe_pm_qs_2
2011h23a_fe_pm_qs_3
(3)符号化
 符号化では,(2)の量子化で用いた電圧v0,v1,…, vmaxに2進符号を対応付ける。この符号によって,各測定値を表す。

 

設問1 図2左の電圧v(t0),v(t1),…,v(t10)だけの符号化を考える。図2右の電圧v0,v1,…,v7を2進符号000,001,…,111に順に対応付けた場合を表1に示す。
2011h23a_fe_pm_qs_4

 図2左のv(t0),v(t1),…,v(t10))の各測定値を,表1に基づいて符号化すると表2のようになる。表2中の[    ]に入れる正しい答えを,解答群の中から選べ。
2011h23a_fe_pm_qs_5
  注記 網掛けの部分は表示していない。

解答群
ア 011  イ 100  ウ 101  エ 110  オ 111



正解は、
a エ
b ウです。

設問2 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。

 アナログ信号の電圧の範囲が0~9Vであるとき,FSRを9Vとし, 4ビットで量子化した場合,qは[  c  ]である。アナログ信号の電圧7.49…Vの測定値は[  d  ]Vとなり,表1の場合と同様に2進符号0000,0001,…,1111に順に対応付けて符号化すると[  e  ]となる。

c, dに関する解答群
ア 0.5625    イ 0.6  ウ 1.2  エ 2.25  オ 5.5
カ 7.0   キ 7.2  ク 7.5  ケ 7.8   コ 8.0

eに関する解答群
ア 1010  イ 1011  ウ 1100  エ 1101  オ 1110



正解は、
c イ
d キ
e ウです。

設問3 次の記述中の[    ]に入れる正しい答えを,解答群の中から選べ。
 FSRが1,022ミリVであるアナログ信号の電圧を,50ミリ秒間隔で5秒間標本化した。このとき, A/D変換後の総データ量を1,000ビット以内に納めることができる刻み幅qの最小値は[  f  ]ミリVである。

解答群
ア 0.1  イ 0.5   ウ 1.0   エ 1.5  オ 2.0  カ 2.5  キ 3.0



正解は、オです。

ハミング符号とは
過去問(H25春AP午前問4)ではハミング符号に関して、「ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できるようにしたものである」とあります。ポイントは、どのビットが間違っているかまで検出できるので、データ誤りを訂正できることです。

以下の過去問で言うと、データが「0110」で、それに対するハミング符号が「011」です。これを付与することで、1ビット誤りを検出し、どこが間違っているかもわかります。

CRCとの違い
CRCとハミング符号の違いについて
CRCは、「生成多項式」を使うのが特徴。x3乗+○x2乗+・・・みたいな、xの何次式かの計算式である。
これにより、パリティと違い、複数のビット誤りを検出できる。
ただし、誤りの訂正まではできないので、受信側が送信側にデータの再送を依頼する。
これは、HDLC手順で利用されています。

一方、ハミング符号は、こちらも計算式を用いることはCRCと同じ。
特徴は、受信側で誤りの訂正までできる優れもの。再送しなくていいのは便利。
だが、CRCと違って、1ビット誤りしか分からない。一部のRAIDで使われている。

ハミング符号の過去問
(1)過去問(H25春AP午前問4)
問4 ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できる
haming
ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア 0110011  イ 1010011  ウ 1100011  エ 1110111
今回は1ビット誤りなので、X1~X4のどれかに誤りがあります。
問題文と照らし合わせ、X1X2X3P3X4P2P1=1110011 として、3つの式に入れてみましょう。

1※1※0※1=1
1※1※0※1=1
1※1※1※0=1  ※は排他的論理和(表記の関係で)

ということで、本来は0になるべき値が、全て1に変わっています。
全ての式にX1が入っているので、X1が誤りということが分かります。
よって、X1を0に置き換えた0110011(選択肢ア)が正解です。
ネットワークスペシャリストを目指す女性SEあれ?

それ以外のビットは変更無しですか?
はい。1ビットの誤りですし、実際、X1を0にすることで、付加ビットの3つの式も全て満たします。

(2)H19秋SW午前問7
問7 コンピュータの主記憶の誤り制御などに採用されている方式のうち、1 ビット誤りを訂正し,2ビットの誤りを検出することができる方式はどれか。
ア 奇数パリティ方式 
イ 水平パリティ方式 
ウ チェックディジット方式
エ ハミング符号方式
奇数パリティ方式や水平パリティ方式では、誤り訂正はできません。1ビットの誤り検知までです。↓


正解は、エのハミング符号です。

(3)H17NW午前問32

haming2

1.誤り制御とは

データを通信相手の送信する際に、通信中のノイズなどにより、データが誤って送られる場合があります。受信側では、その誤りを検知したり、場合によっては訂正するなどの誤り制御をすることで、データの正確性を保ちます。
誤り制御方式には、①パリティビット、②CRC、③ハミング符号、などがあります。 
CRCに関しては、以下
http://sm.seeeko.com/archives/15876760.html

ハミング符号に関しては以下に記載
http://sm.seeeko.com/archives/15877011.html

2.パリティビット

パリティとは、データの誤りを検知するために付与する冗長ビットのことです。
具体例は、次で説明します。

(1)奇数パリティと偶数パリティ
偶数パリティは、1の数が偶数、奇数パリティは奇数になるようにします。
たとえば、
1000という4ビットデータがあった場合、
①偶数パリティ
1000 ⇒ 10001 最後に1のパリティを付与
②奇数パリティ
1000 ⇒ 10000 最後に0のパリティを付与します。

もし、途中で1ビットのデータ誤りが発生した場合、上記の偶数パリティが10101になっていれば、1の数が奇数個ですから、データ誤りが発生したことが分かります。しかし、10111というように、2ビットのデータ誤りの場合、1の数が偶数個(つまり正しい)なので、データ誤りを検知できません。
1

(2)垂直パリティと水平パリティ
この下の過去問にありますように、垂直方向か水平方向にチェックするかによって、垂直パリティと水平パリティがあります。
垂直パリティだけですと、1ビットの誤りは検知できますが、どのビットで誤りが発生したかは分かりません。水平パリティと組み合わせることで、どこに誤りが発生したかが分かります。そのビットを反転(0⇒1、1⇒0)させることでデータ誤りの検知だけでなく、訂正まで行うことができます。

3.パリティビットに関する過去問

(1)H27秋AP午前問4
問4 図のように16ビットのデータを4×4の正方形状に並べ,行と列にパリティビットを付加することによって何ビットまでの誤りを訂正できるか。ここで,図の網掛け部分はパリティビットを表す。
パリティ
ア 1  イ 2  ウ 3  エ 4



正解:ア

(2)H25春FE午前問4
問4 通信回線の伝送誤りに対処するパリティチェック方式(垂直パリティ)の記述として,適切なものはどれか。
ア 1ビットの誤りを検出できる。
イ 1ビットの誤りを訂正でき,2ビットの誤りを検出できる。
ウ 奇数パリティならば1ビットの誤りを検出できるが,偶数パリティでは1ビットの誤りも検出できない。
エ 奇数パリティならば奇数個のビット誤りを,偶数パリティならば偶数個のビット誤りを検出できる。
1ビットの誤りまでは検知できますが、それ以上の検知や、誤りの訂正はできません。



正解:ア

人間の言葉をそのまま理解できないコンピュータには、コンピュータが理解できる言語を使う必要があります。このように、コンピュータにはコンピュータならではの理論があり、ここではそんな情報(コンピュータ)に関する理論をいくつか紹介します。

 

1.オートマトン

オートマトンとは、状態遷移図のモデルです。
たとえばタスク管理において、「実行状態」「実行可能状態」「待ち状態」の3つの状態を遷移します。
過去問(H20FE秋午前問29)では、コンピュータのタスクの状態遷移として、次の図が記載されています。
状態遷移
また、実行状態のタスクが、「自分より優先度の高いタスクが実行可能状態になった」ことで、実行可能状態に遷移するともあります。

このように、ある「状態」と「遷移」の様子を表したモデルがオートマトンです。かつ、状態や遷移が有限なものが有限オートマントンです。

実際の過去問(H21春AP午前問3)の有限オートマトンを見てみましょう。問題文には、「S1は初期状態を,S3は受理状態を表している。」とも記載があります。
automaton
ここで、初期状態のS1に1が与えられるとS2に遷移し、0が与えられるとS3に遷移します。
S2においては、0が与えられるとS2のままで、1が与えられるとS1に遷移します。
S3においては、0が与えられるとS2に遷移し、1が与えられるとS3のままです。

2.オートマトンの過去問

(1)H28秋AP午前問4

問4 表は,入力記号の集合が{0,   1},状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
manton
ア a   イ b   ウ c   エ d

さて、よくわからない問題だと感じた人も多かったことでしょう。状態集合が{a, b, c, d}であり、それに対して入力記号の集合が{0,   1}です。問題文の状態遷移表をオートマトンの図にすると、以下になります。
auto 
ここで、最後が110で終わっているものを受理すると、樹里状態はa~dのどれになるのでしょうか。というのが問題です。最後が110というのがよく分かりませんが、とにかく、a~dの4つの中のいずれかからスタートしますので、順番に入れてみます。

・aからスタート
 a→1→b→1→d→0→c
・bからスタート
 b→1→d→1→d→0→c
・cからスタート
 c→1→b→1→d→0→c
・dからスタート
 d→1→d→1→d→0→c

このように、どこからスタートしても110を受理すると、cで受理状態になります。
正解は、cですからウです。

(2)H26春AP問4
問4 表は,入力記号の集合が{0,1},状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
H26h-4
ア a   イ b   ウ c   エ d
【正解】ウ

(3)H25春AP問3
問3 図は,偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり,二重丸が受理状態を表す。 a,bの適切な組合せはどれか。
H25h-3_1図H25h-3_2選択肢表


【正解】ウ

 

1.逆ポーランド表記法

逆ポーランド表記法とは,演算子を二つの演算対象の後ろに配置することによって,数式を表現する表記法です。例えば,一般的な表記法の数式1+2×3を,逆ポーランド表記法では123×+と表記します。逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い表記方法です。

まずは過去問(H24秋AP午前問4)を見てみましょう。

問4 式 E=(A+B)×(C-D)と対応する逆ポーランド表記法はどれか。
ア =EX+AB-CD ウ EAB-CD+×=
イ EAB+CD-×= 工 EABCX+D-=


逆ポーランド表記法は、パッと見は難しいのですが、方式を覚えて慣れてしまえば難しくはありません。後述する過去問(H25春AP午後問2)をベースに解説します。
まず、表記の方法は、 2×3 を 23× とします。演算子を演算対象のすぐ後ろに配置するのです。このルールだけ覚えてください。
では、 1+2×3 はどうなるでしょうか。
この演算は、1+2を先にするのではなく、2×3を先に計算しますよね。つまり、2×3が一つの塊です。よって、(2×3)をZと考えると、1+Zですから、1Z+になります。Zに23×を入れると、123×+となります。
2
よって、この問題の正解はイです。
応用情報技術者試験を勉強する成子 

なぜこんな面倒なことをするのですか?
先ほどの過去問には、「逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。」とあります。

上記の過去問ですが、このルールに従うと、 A+B は AB+ 、 C-D は CD- 
(A+B)と(C-D)をそれぞれの塊とみた上で掛け算をするので、 (A+B)×(C-D) は AB+CD-× になります。この塊とEを「=」という演算をすると考えればいいので、 EAB+CD-×= が正解です。

2.逆ポーランド表記法の過去問

(1)H25春AP午後問2
 過去問(H25春AP午後問2)に、逆ポーランド表記法に関する出題があるので以下に掲載します。

問2 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムに関する次の記述を読んで,設問1~3に答えよ。
 逆ポーランド表記法とは,演算子を二つの演算対象の後ろに配置することによって,数式を表現する表記法である。例えば,一般的な表記法の数式1+2×3を,逆ポーランド表記法では123×+と表記する。
 逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。
 一般的な表記法の数式から逆ポーランド表記法への変換は,スタックを用いることで容易に実現できる。

〔逆ポーランド表記法への変換アルゴリズム〕
 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムでは,まず変換前の数式を,数値,演算子及び括弧の要素(以下,演算要素という)に分解する。
演算子には二項演算子十,-,×,÷を用い,括弧には"("と")"を用いる。
数値は0~9の1桁の数とする。それぞれの演算要素には,優先度を定義する。
 変換の処理には,変換前配列,スタック及び変換後配列を用いる。初期状態では,変換前配列には変換前の数式の演算要素が順に入っており,スタックと変換後配列は空の状態である。変換後には,変換後配列に逆ポーランド表記法に変換した結果が入る。例えば,変換前の数式が1+2×3の場合,初期状態は表1のようになる。
a

 逆ポーランド表記法への変換は,次の(1)~(4)の手順で行う。
(1)変換前配列の先頭から順に,演算要素を1個参照する。
  参照する演算要素がない場合は(4)に進む。
(2)スタック上に演算要素がある場合は,スタックの先頭にある演算要素の優先度を参照し, (1)の演算要素の優先度以上なら,スタックの先頭の演算要素をホップし,変換後配列の末尾に追加する。これを,スタックの先頭の演算要素の優先度が, (1)の演算要素の優先度未満になるまで繰り返す。ただし,スタックの先頭の演算要素が“(”の場合は,そこで繰返しを終了する。
(3)(1)で参照した演算要素が“)”なら,それを破棄し,その際スタックの先頭にあるはずの“(”もホップして破棄した後(1)に戻る。(1)で参照した演算要素が“)”以外なら,その演算要素をスタックにプッシュし. (1)に戻る。
(4)スタック上にある全ての演算要素を順番にホップし,変換後配列の末尾に追加する。

演算要素の優先度を表2に,数式1+2×3を変換するときの処理過程を図1に示す。
なお,図1中の丸で囲った演算要素は, (1)の手順で参照した演算要素である。
b
(後半略)

設問1 逆ポーランド表記法への変換について, (1), (2)に答えよ。
(1)数式(2+3)×4を逆ポーランド表記法に変換した結果を答えよ。
(2)表2及び表4中の[ ア ]~[ エ ]に入れる適切な二項演算子を、+,-,×,÷の中から一つずつ選んで,表を完成させよ。

(後半略)


(2)H28秋AP午前問3

問3 逆ポーランド表記法で表された式を評価する場合,途中の結果を格納するためのスタックを用意し,式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき,入力が演算子となった。このときに行われる演算はどれか。ここで,演算は中置表記法で記述するものとする。
enzan
ア A 演算子 B   ウ C 演算子 D
イ B 演算子 A   エ D 演算子 C

中置表記法なので、3+4のように、演算子(×や+)が文字と文字の中に入ります。
ちなみに、逆ポーランド記法は、34+などと表記するので、後置記法と言われます。

 (詳しくは別途解説)
スタックは後入れ先出し法(LIFO)ですので、上から順に処理をします。
ただこのとき、リンクの図を見てもらうとわかるように、最初に演算する数値が下に来ます。よって、正解は、ウの C 演算子 D  です。

有限小数などの数値に関する出題があります。ここでは、特に有限小数に関して解説します。過去問は、数値に関することを集めました。

1.有限小数と無限小数

有限小数とは、言葉の通り、小数部分が有限の数です。たとえば、1.23とか0.3156など。一方、無限小数は、小数部分が無限の数です。分かりやすいのが、1÷3の結果です。0.333333・・・と3が無限に続きます。

過去問(H24春IP問66)を例に考えましょう。
問66 2進数に変換したとき,有限小数で表現できる10進数はどれか。
ア 0.1
イ 0.2
ウ 0.4
エ 0.5
2進数から10進数への基数変換の方法は以下を参考にしてください。
http://sm.seeeko.com/archives/15877053.html

10進数を2進数にしていきますから、2倍していきます。
それが、きれいに整数になればいいのです。
ア 0.1 ⇒0.2 ⇒0.4 ⇒0.8 ⇒ 1.6  ×(いつまでも続く)
イ 0.2 上と同様
ウ 0.4 上と同様 
エ 0.5 ⇒1 よって、2進数で表すと、0.1

正解はエです。

2.数値に関する過去問

(1)H26春AP午前問1

問1 2進数で表現すると無限小数になる10進小数はどれか。
ア 0.375
イ 0.45
ウ 0.625
エ 0.75
同じく2をかけていきます。
ア 0.375 ⇒0.75 ⇒1.5 2桁目が1
           0.5 ⇒ 1 3桁目が1 2進数表記で0.011
イ 0.45 ⇒0.9 ⇒1.8 永遠に続く
ウ 0.625 ⇒1.25 1桁目が1
       ⇒0.25 ⇒0.5 ⇒1 1桁目が1 2進数表記で0.101
エ 0.75 ⇒1.5 1桁目が1
       ⇒0.5 ⇒1 2桁目が1 2進数表記で0.11

よって、正解はイです。

(2)H29春AP問2
問2 (1+α)nの計算を,1+n×αで近似計算ができる条件として,適切なものはどれか。
ア |α|が1に比べて非常に小さい。
イ |α|がnに比べて非常に大きい。
ウ |α÷n|が1よりも大きい。
エ |n×α|が1よりも大きい。



計算してみましょう。
公式を覚えている人は少ないと思われるので、nに数値をあてはめていきます
n=2 (1+α)^2=1+2α+α^2
n=3 (1+α)^3=1+3α+3α^2+α^3
n=4 (1+α)^4=1+4α+6α^2+4α^3+α^4
・・・
すると、|α|が1に比べて非常に小さい場合には、^2、^3・・・の部分がとても小さくなり、無視してもいいレベルになります。それ以外の選択肢で、上記の公式に数字を当てはめてみると、^2、^3・・・の部分がほぼ0になりません。よって、1+n×αの近似値にはなりません。
【正解】ア

(3)H25春AP問3
問3 負の整数を表現する代表的な方法として,次の3種類がある。
     a 1の補数による表現
     b 2の補数による表現
     c 絶対値に符号を付けた表現(左端ビットが0の場合は正,1の場合は負)
   4ビットのパターン1101をa~cの方法で表現したものと解釈したとき,値が小さい順になるように三つの方法を並べたものはどれか。
ア a,c,b    イ b,a,c
ウ b,c,a    エ c,b,a



1の補数や2の補数に関しては、以下に説明をしてあります。
http://sm.seeeko.com/archives/15877053.html

[a]
1101を元のデータにしましょう。1の補数はビットを逆にしているだけなので、0010です。よって-2
[b]
1101を元にするには、ちょっと難しいのですが、もう一度同じ処理をします。1の補数が0010、2の補数は1を足しては0011です。 よって、-3
[c]
先頭の1はマイナスを意味します。101は5 よって-5
【正解】エ

過去問にカルノー図の例がありますが、ちょっとだけ複雑です。

カルノー図
【正解】エ

1.誤差とは

円周率のように、3.141592・・・と続く数字があります。
コンピュータでは、ある程度のとこで桁数を有限にする必要があります。
すると、実際の値とは誤差ができます。

応用情報技術者試験のシラバスでは、このあたりに関して以下の記載があります。
(3)算術演算と精度
加減乗除,表現可能な数値の範囲,シフト演算,演算精度(誤差とその対策)など,コンピュータでの算術演算を理解する。

用語例 論理シフト,算術シフト,桁落ち,情報落ち,丸め,打切り,オーバフロー(あふれ),アンダフロー,単精度,倍精度

2.誤差の種類

過去問(H20秋SW午前問2)をもとに、誤差に関して整理します。
(1)丸め誤差
「指定された有効けた数で演算結果を表すために,切捨て,切上げ,四捨五入などで下位のけたを削除することによって発生する誤差(過去問(H20秋SW午前問2)より)」です。

「3.14159・・・」を小数点第2位で四捨五入すると「3.1」です。実際の3.14159・・・とは誤差があります。これによって、円の面積が正しく計算できず、誤差が生じてしまいます。

(2)けた落ち(桁落ち)
「値がほぼ等しい二つの数値の差を求めたとき,有効けた数が減ることによって発生する誤差(過去問(H20秋SW午前問2)より)」です。
123.45 - 123.42 = 0.03
応用情報技術者試験を勉強する成子
これは何が問題なのですか?
しかも、「誤差」なのですか?
少数は、以下にあるように、α×2のβ乗で表される。
http://sm.seeeko.com/archives/15877104.html
α(仮数部)の桁数は決まっているが、有効桁数が少なくなると、残り部分をゼロ埋めしてします。それって、本当は0じゃないよね?0.1000みたいな、意味のないゼロがつく。これを誤差と言っているのだろう。

また、ITEC社のコンピュータシステムの基礎のp342にわかりやすい事例があった。※こちらは明らかな誤差。
ルート150=12.247449 (有効桁数8桁)
ルート151=12.288206 (有効桁数8桁)
ルート151-ルート150をすると、0.040757になり、有効桁数が減ってしまう。
有効桁数を先に区切るのではなく、有理化して、計算すれば、0.040757013となる。
プログラムの組み方によっては、桁が落ちてしまい、こちらの場合は誤差である。

(3)情報落ち
「絶対値の非常に大きな数値と小さな数値の足し算や引き算を行ったとき,小さい数値が計算結果に反映されないことによって発生する誤差(過去問(H20秋SW午前問2)問より)」、「浮動小数点数の加算において,一方の数値の下位の桁が結果に反映されないことである。(H27春FE問2)」です。

12345+0.6789=

(4)桁あふれ(オーバフロー)
「演算結果が,扱える数値の最大値を超えることによって生じるエラーのことである。(H27春FE問2)」

(5)打切り誤差
「無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差(過去問(H20秋SW午前問2)より)」です。

3.誤差に関する過去問

(1)H25秋AP問2
問2 桁落ちによる誤差の説明として,適切なものはどれか。
ア 値がほぼ等しい二つの数値の差を求めたとき,有効桁数が減ることによって発生する誤差
イ 指定された有効桁数で演算結果を表すために,切捨て,切上げ,四捨五入などで下位の桁を削除することによって発生する誤差
ウ 絶対値の非常に大きな数値と小さな数値の加算や減算を行ったとき,小さい数値が計算結果に反映されないことによって発生する誤差
エ 無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差



【正解】ア


(2)H27春FE問2)
問2 桁落ちの説明として,適切なものはどれか。
ア 値がほぼ等しい浮動小数点数同士の減算において,有効桁数が大幅に減ってしまうことである。
イ 演算結果が,扱える数値の最大値を超えることによって生じるエラーのことである。
ウ 浮動小数点数の演算結果について,最小の桁よりも小さい部分の四捨五入,切上げ又は切捨てを行うことによって生じる誤差のことである。
エ 浮動小数点数の加算において,一方の数値の下位の桁が結果に反映されないことである。



ア:桁落ち
イ 桁あふれ(オーバフロー)
ウ:丸目誤差
エ:情報落ち

f:id:mamori_yuto:20181027120143j:plain


ここでは、2進数などの基数について解説します。

1.2進数とは

我々が日常的に使っている数字は、10進数を使っています。一方、コンピュータでは、0と1の2つの数字だけを使います。これを2進数と言います。
※参考ですが、2進数以外に、コンピュータでの処理を表現するときには、たとえばネットワークでは16進数も使います。
進数の意味としては、0と1の2つの数字で表すものが2進数、0~9の10個の数字で表すものが10進数、0~9、A~Eの16個の数字(と文字)で表すのが16進数です。

Q.2進数、10進数で表してみよう。
10進数 ---- 2進数 ---- 16進数 
0        0         0
1        1         1
2        10        2
3        11        3
4        100      4
5        101      5
6        110      6
7        111      7
8        1000      8
9        1001      9
10       1010        A
11       1011       B
12       1100       C
13       1101       D
14       1110       E
15       1111       F
16       10000    10
17       10001    11
18       10010    12
19       10011    13
20       10100    14

Q.では問題です。我々は、10進数を当たり前に使っています。234という数字をよくみてください。4は4個を意味す。でも3は3個を意味しませんよね。30個を意味します。2も同じで、200を意味します。この観点で、234という数字を、10と2,3,4などの数字の計算式で表してください。

A.簡単ですね。
234=2×10の2乗 + 3×10の1乗 + 4×10の0乗  ※10の0乗=1

こうなります。まずはこの事実を改めて認識してください。

2.基数とは

基数とは、桁が上がる基準となる数のことです。この言葉だけ聞くとよくわからないでしょうが、我々が日頃の買い物などで使っているのは10進数で、この基数は10です。また、2進数の基数は2で、16進数の基数は16です。

たとえば、2という数字を例に考えます。
10進数では「2」と表現され、桁が変化しません(つまり1桁)。ですが、2進数で2を表現すると10になり(桁が上がります)。
同様に、15は10進数では15となって2桁ですが、16進数ではFです。16に満たないので桁が上がらず1桁です。
f:id:mamori_yuto:20181027120212j:plain


16進数の場合は、16になってはじめて桁が上がるということですね。

 

その通りです。ですから、15までの数を1桁で表現できなければいけません。
そこで、10→A、11→B、12→C、13→D、14→E、15→Fと表現されます。
逆に、2進数は2という数字で桁が上がってしまいます。なので、2以上の数字は要りません。だから、0と1だけで表現されます。

考え方の基本として、基数という考えをしっかりと押さえましょう。
2進数の2は、「2で桁が上がる」のです。10進数の場合は10で桁が上がります。
その結果として、以下が言えます。
・10進数の場合は0~9までの数字があればよい
・数字は 以下のように、10の階乗を使って表現できる。
234=2×10の2乗 + 3×10の1乗 + 4×10の0乗 

ただ、基数という言葉の意味は少しわかりにくい面があります。
基数という言葉は、あまり深く考えず、「何進数なのか?」と置き換えて考えればいいでしょう。
また、0と1の2つの数字で表すものが2進数、0~9の10個の数字で表すものが10進数、0~Eの16個の数字(と文字)で表すのが16進数と考えておくと、実際のその通りですし、分かりやすいと思います。

Q.10進数で30という数字を2進数と16進数で表しましょう。

A.2進数では11110、16進数では1Eです。

3.基数変換の方法(10進数に変換)

(1)基数変換の方法
2進数を10進数にする場合や、16進数を2進数にする方法を解説します。(このように、基数を変えることを基数変換と言います。ただ、言葉は覚えなくてもいいでしょう)

方法は、すでに述べた以下の方法を活用します。
234=2×10の2乗 + 3×10の1乗 + 4×10の0乗 
2進数の場合でも同じです。
101=1×2の2乗 + 0×2の1乗 + 1×2の0乗 = 4 + 0 + 1 =5

(2)小数の場合
小数点が入った場合はどうなるでしょうか。実は計算方法は同じです。
小数点以下は、マイナス乗を加えていきます。
言葉で解説するよりも、実際の変換を見てもらった方が分かりやすいと思います。

基数変換
★2進数の処理結果は9.5ではなく、5.5の間違い
10進数で解説します。このように、各位の値(1の位が8、10の位が2)に、基数の累乗(1の位は10の0乗、10の位は10の1乗)をかけて、足したものが10進数の値になります。

4.基数変換(10進数を変換)

では、次に10進数を2進数や16進数に変える方法を説明します。
考え方は上の図と同じです。たとえば、上の変換の小数点を無くしたものですが、5という数字や298という数字は、以下の式で表されます。なので、2進数では5、16進数では12Aとなります。
kisuu
応用情報技術者試験を勉強する成子
 
でも、その計算をどうやるのですか?
多くの方がやっている方法ですが、以下のように、基数で値を割っていきます。これ以上割れなくなったらおしまいで、その余りを逆から見て行くと、進数変換ができます。
このテクニックはとても有用なので、覚えておきましょう。
下図のように、10進数の5は2進数で101、298は12Aになることが分かります。
2

5.基数変換(10進数を変換:小数)

10進数の0.375を2進数にするにはどうしたらいいのでしょうか。
2進数の小数を復習しましょう。
2
このように、2進数で表された小数は、2倍していくと1になります。また、上記の小数点第3位のところをみてもらうとわかるように、小数点第三位のところが1であれば、2を3倍すると1になります。
以下をみてください。これをみると、なんとなく、両方を2倍していくと計算方法が見えてこないでしょうか。
2sinsuu
では、2倍していきましょう。
0.375 2倍 ⇒0.75  1にならないので、小数点第1位は0
     さらに2倍 ⇒1.5 1になったので、小数点第2位は1
     残りの0.5を2倍 ⇒1 1になったので、小数点第3位は1

2進数表記で0.011となります。 
位は10の1乗)をかけて、足したものが10進数の値になります。

6.シフト演算

では、シフト(shift)とは「移す」という意味で、ビットを右や左にずらします。
たとえば2進数の場合
001100(=12) を左に1ビットずらすと2倍、2ビットずらすと4倍になります。
→左に1ビット 011000(=24)
→左に2ビット 110000(=48)
001100(=12) を右に1ビットずらすと1/2倍、2ビットずらすと1/4倍になります。
→左に1ビット 000110(=6)
→左に2ビット 000011(=3)

6.基数に関する過去問

(1)H20秋SW午前問1
問1 基数変換に関する記述のうち,適切なものはどれか。
ア 2進数の有限小数は,10進数にしても必ず有限小数になる。
イ 8進数の有限小数は,2進数にすると有限小数にならないこともある。
ウ 8進数の有限小数は,10進数にすると有限小数にならないこともある。
エ 10進数の有限小数は,8進数にしても必ず有限小数になる。



有限小数と無限小数に関しては、別途記事を確認ください。

正解はアです。

(2)H28春AP問2
問2 10進数123を,英字A~Zを用いた26進数で表したものはどれか。ここでA=0,B=1,…,Z=25とする。
ア BCD
イ DCB
ウ ET
エ TE



基数である26で割り算をします。
すると4(=E)と19(=T)であることが分かります。
1
【正解】ウ


(3)H27春AP問2
問2 2桁の2進数x1x2が表す整数をxとする。2進数x2x1が表す整数を,xの式で表したものはどれか。ここで,int(r)は非負の実数rの小数点以下を切り捨てた整数を表す。
1-1H27-1




【正解】ウ
(4)H25春AP問1
問1 αを正の整数とし,b=a2 とする。αを2進数で表現するとnビットであるとき,bを2進数で表現すると高々何ビットになるか。
ア n+1   イ 2n   ウ n2   エ 2n




難しい問題ですね。
分からない場合は、数字を当てはめるといいでしょう。a=10、b=100
a(=10)を2進数にすると、1010で4ビット、n=4
b(=100)を2進数にすると、1100100で、7ビット
ア n+1=5
イ 2n=8
ウ n2 =16
エ 2n=16  であり、最も近いイがなんとなく答えではないかとあたりをつけることができる。
【正解】イ

 

1.制御に関する理論

「制御に関する理論」に関して、応用情報のシラバスを引用します。

② センサ・アクチュエータの種類と動作特性
コンピュータ制御では,制御対象の光,温度,圧力などの状態をセンサで検出し,コンピュータが判断して,アクチュエータを通じて電動,油圧,水圧,空気圧などの機械的な動作に変換し,制御対象を一定の状態に保つなどの制御を行うことを理解する。

用語例 光学センサ,イメージセンサ,レーザセンサ,赤外線センサ,X 線センサ,磁気センサ,加速度センサ,ジャイロセンサ,超音波センサ

③ 計測システムの種類と動作特性
測位システムなど,コンピュータを利用した高度な計測システムの考え方,仕組みを理解する。

用語例 GPS基地局測位,無線LAN アクセスポイント測位

コンピュータや電子機器、家電などには、これらのセンサーや計測システムが導入されて、うまく動作するようになっているのです。

2.ジャイロセンサ

ジャイロセンサとは、角速度を計測するセンサーです。角速度とは、角(角度)の速度なので、回転するスピードと考えてください。たとえば、デジカメの手ぶれ防止機能は、このジャイロセンサで手ぶれを検知します。

過去問(H29秋AP午前問71)では、ジャイロセンサに関して、「ドローン,マルチコプタなどの無人航空機に搭載されるセンサのうち,機体を常に水平に保つ姿勢制御のために使われる」と述べられています。

3.センサーに関する過去問

(1)H29秋AP午前問71
問71 ドローン,マルチコプタなどの無人航空機に搭載されるセンサのうち,機体を常に水平に保つ姿勢制御のために使われるセンサはどれか。
ア 気圧センサ      ウ 地磁気センサ
イ ジャイロセンサ    エ 超音波センサ




【正解】イ

 

(2)H27春AP午前問4
問4 携帯端末に搭載されているジャイロセンサが検出できるものはどれか。
ア 端末に加わる加速度   イ 端末の角速度
ウ 地球上における高度   エ 地球の磁北




【正解】イ

 

 

1.BNF(Backus-Naur Form)

バッカスナウアーフォームと読みます。
我々が日常で話す言葉が自然言語ですが、そのコンピュータに理解しろというのは無理があります。そこで、ルール(形式)に基づいた言語を形式言語と言います。その代表がBNFです。

BNFでは、2つのルールだけ覚えましょう。

➀ ::= ⇒ 定義する
② |   ⇒ または

では、例を見ましょう。
bnf
上記のルールに従うと、<digit>には数字の0か1か2か3が入ります。

2.BNF(Backus-Naur Form)の過去問

(1)H29秋AP問2
問2 次のBNFにおいて非終端記号〈A〉から生成される文字列はどれか。
〈R0〉::=0|3|6|9
〈R1〉::=1|4|7
〈R2〉::=2|5|8
〈A〉 ::=〈R0〉|〈A〉〈R)〉|〈B〉〈R2〉|〈C〉〈R1〉
〈B〉 ::=〈R1〉|〈A〉〈R1〉|〈B〉〈R0〉|〈C〉〈R2〉
〈C〉 ::=〈R2〉|〈A〉〈R2〉|〈B〉〈R1〉|〈C〉〈R0〉
ア 123   イ 124   ウ 127   エ 128




【正解】ア

(2)平成29年春期 午前

問4 あるプログラム言語において,識別子(identifier)は,先頭が英字で始まり,それ以降に任意個の英数字が続く文字列である。これをBNFで定義したとき,aに入るものはどれか。

bnf

1行目から順に解説します。
・<digit>の右に::=がありますので、<digit>という言葉を定義しています。具体的な定義内容は右側にあり、|で区切られているので、0または1または2または・・・9のいずれかの値を取ります。つまり、<digit>は任意の1桁の数字が入ることがわかります。
 ・同様に、<letter>には大文字小文字を含めた任意のアルファベット1文字が入ります。

さて、ここで、設問文に「識別子(identifier)は,先頭が英字で始まり,」とあります。よって、数字だけの<digit>は対象外になります。残るはウかエです。
設問文に「任意個の英数字が続く文字列」とありますから、、<digit>の数字だけでなく、<letter>の文字も入ります。よって、正解はエです。

以下は、検証です。(メモ程度にお考えください)
・<identifier>は、<letter>または <identifier><digit>または<identifier><letter>です。順に説明します。
①<letter>の場合
任意のアルファベット1文字が入ります。
② <identifier><digit>の場合
<identifier>が取りうる値+任意の数字1文字が入ります。
③ <identifier><letter>の場合
<identifier>が取りうる値+任意のアルファベット1文字が入ります。

①の法則にしたがうと、<identifier>は例えばA、②の法則にしたがうと、<identifier>は例えばA1、③の法則にしたがうと、<identifier>は例えばA1Bです。さらに、この値をもって②や③の法則に当てはめると、たとえばA1B2、A1BC、となります。ここに挙げた5個のいずれの場合でも、<identifier>は先頭が英字で始まり,それ以降に任意個の英数字が続く文字列となります。

■負の数の計算
2進数の計算において、マイナスの演算をする際は、2の補数を使います。
たとえば、1001(=9)という値において
・ビットを反転させる 0110 ←1の補数
・それに1を加える  0111 ←2の補数
では、1100(=12)から1001(=9)を引いてみましょう。
1100+0111=0011(=3)※先頭であふれた1は、捨てられます。

■固定小数点数
・固定小数点数とは、小数点の位置を固定した数。(たとえば、16ビットにおいて、一番右端とか、8ビット目か)
ただ、これが以外に桁数の効率が悪い。
たとえば、16ビットにおいて小数点を8ビットの終わりに固定すると、整数部は2の8乗しか設定できない
 ⇔浮動小数点数

■浮動小数点
・コンピュータでは、浮動小数点を使う。
たとえば、1.2×10の30乗とか。
ここで、1.2が仮数、10が基数、30を指数と言います。
上記は、固定小数点数では表現できない大きな数を表現できますね。(ただ、誤差がでますが)
 参考ですが、C言語の場合、以下です。
  ・単精度浮動小数点数(32ビット)はfloat
  ・倍精度浮動小数点数(64ビット)はdouble

・正規化
1.2×10の30乗は、12.0×10の29乗や120×10の28乗、0.12×10の31乗と表現することも可能です。統一した方がいいので、仮数の整数部は常に0以外の1桁にします(実際には、1にします)。このように、桁合わせをすることを正規化と言います。
※また、指数部は2進数、基数は2です。

過去問(H29春FE)
問2 0以外の数値を浮動小数点表示で表現する場合,仮数部の最上位桁が0 以外になるように,桁合わせする操作はどれか。ここで,仮数部の表現方法は,絶対値表現とする。
ア 切上げ  イ 切捨て  ウ 桁上げ エ 正規化
→正解はエ

■IEEE754による浮動小数点の標準規格
H27秋FE午前問2に詳しい解説があります。

浮動小数点
32ビット単精度浮動小数点形式の表現(単精度表現)では、符号部1ビット、指数部8ビット、仮数部23ビット
です。また、仮数の整数部は常に1なので、表現する必要が無い。数ビット得する。←ケチ表現
※単精度は32ビット、倍精度は倍の64ビットで表現されます。倍精度の方が正確ですが、もちろん処理には時間がかかります。

・指数部はゲタバキ表現を使う。127(=1000000)を加える。こうすることで、マイナスの指数も表現できる。
たとえば、0.625を単数度表現してみましょう。
0.625=α×2のβ乗で表現されます。
まず、0.625は2進数で0.101です。
0.101×2の0乗 = 1.01×2の-1乗(2倍すると、桁が一つ繰り上がる)
指数部は1ですが、ゲタバキなので、127を足すと、126になります。2進数では、1111110(=01111110)です。これを16進数にするには、4ビットずつ区切ればいいので、0111(=7)、1110(=E)で、7Eです。

試験センターが発表する「午後の出題範囲」に、「4 情報セキュリティの管理・運用に関すること」というのがある。

午後1や午後2では、重要な位置づけになるテーマだ。
現に、H17~H20において、午後1では各1問が「セキュリティ管理」に関する出題である。
午後1に関しては、セキュリティ管理に特化した問題は稀であるが、セキュリティ管理をテーマとして書くことは可能である。
例えば、システム障害の題材をセキュリティインシデントにしたり、運用管理においてセキュリティの監視をする、などである。

H18午後1問2は、色々な意味で勉強になる。
例えば、[セキュリティ侵害時のW社の対応手順]を読んでいると、セキュリティ対応の基本的なやり方が書いてあり、勉強になる。
また、このまま午後2の問題になってもおかしくない。

例えば、[セキュリティ侵害時のW社の対応手順]が記載され、

設問ア あなたが携わったITサービスの概要と、発生したセキュリティインシデントの概要を800字で述べよ。

設問イ 設問アで述べたセキュリティインシデントの検知から終了までのプロセスを、どのような視点で原因究明をしたか及び工夫した点を含め、800字以上1600字以内で、具体的に述べよ。

設問ウ SLAで取り交わした合意内容の達成を目指した、セキュリティインシデント管理プロセスの定期的な評価と改善について、600字以上1200字以内で、具体的に述べよ。

その解答例は、H18午後1問2の[状況調査と処置]で書かれている内容そのものである。

ITサービスマネージャの立場として、「(自ら)ログを調査した」「(自ら)内容を確認した」などではなく、「指示した」という表現になっており、論文で使える表現である。

セキュリティインシデントの論文ネタとしておくのもよい。
・インシデント:不正アクセスの発生。Webサーバに不審なファイルの存在
・直接原因:OSのセキュリティホールを利用したもの
・原因:開発環境にはパッチを適用しているが、本環境には適用していなかった。
・工夫した点:・原因分析を確実に行えるように、ハードディスク内容の保存、ログイン状況、プロセス稼働状況を記録した。(こういう記述ができると、経験をさりげなくアピールできる)
不正アクセスの再発を防止するために、インターネット接続を遮断した。

■床下空調方式
データセンターでは、皆このタイプですね。
床下から冷たい空気が流れる。暖かい空気は上昇するため、その流れに従って天井から排出する。

H20SM午前27では「空調設備の送風方式の一つである床下空調方式の特徴として、送風の流れと暖気の上昇の流れが同じであり、効率よく冷却ができる。」とある。


■天井吹出方式
通常のエアコンによる空調と考えればよいでしょう。
フリーアクセス+床下空調を実現するためのコストがない場合には、こちらになるでしょう。

 

1.待ち行列とは

 銀行の窓口やスーパーのレジなど、処理の順番を待つための行列ができることがあります。このときの、平均待ち時間を計算するのが待ち行列の理論です。待ち行列の計算は、窓口の要員数を決定することなどに活用されます。
 以下の図を見て下さい。銀行に一つの窓口があり、窓口でサービスを受けている人と、順番を待っている人がいます。窓口で口座開設などの手続きを受けたりするなどのサービスを受けます。この時間をサービス時間と言います。また、待っている時間を待ち時間、サービス時間と待ち時間を合わせて応答時間と言います。

f:id:mamori_yuto:20181028044125j:plain

2.待ち行列で覚えるべき公式

M/M/1の問題は難しいと思う人、簡単と思う人の両方がいるでしょう。ポアソン分布であったり、指数分布であったり難しい言葉が並びます。難しいと感じる人も多いと思います。
しかし、以下の公式を1つ覚えるだけで解けます。

【公式】
平均待ち時間=ρ÷(1-ρ)X T
・ρは窓口の利用率(必ず1以下)
・Tはサービス時間

今回、平均待ち時間=Tであるため
T=ρ÷(1-ρ)X T

これを解くと
ρ=0.5が導き出せます。
問題文を読み解くとという重要な力は必要ですが、内容そのものは単純な問題です。

3.【参考】M/M/1の説明

・M:単位時間に到着する客の数はポアソン分布に従う(つまりランダム)。別の言い方をすると、一様分布でどの値も確率は同じ。たとえば、(0,1)の一様分布といえば、0.001 0.002 などの点が同じ確率で存在する。
・M(Markov):サービス時間は指数分布に従う(長いサービス時間になるほど量は減る)

・1:窓口は一つである。
※平成16年 問8参照
ちなみに、M/D/1の場合、サービス時間のD(Deterministic)は一定時間

4.待ち行列の過去問

(1)H28春AP問3
問3 多数のクライアントが,LANに接続された1台のプリンタを共同利用するときの印刷要求から印刷完了までの所要時間を,待ち行列理論を適用して見積もる場合について考える。プリンタの運用方法や利用状況に関する記述のうち,M/M/1の待ち行列モデルの条件に反しないものはどれか。
ア 一部のクライアントは,プリンタの空き具合を見ながら印刷要求をする。
イ 印刷の緊急性や印刷量の多少にかかわらず,先着順に印刷する。
ウ 印刷待ち文書の総量がプリンタのバッファサイズを超えるときは,一時的に受付を中断する。
エ 一つの印刷要求から印刷完了までの所要時間は,印刷の準備に要する一定時間と,印刷量に比例する時間の合計である。




【正解】イ

(2)H27春
問1 ATM(現金自動預払機)が1台ずつ設置してある二つの支店を統合し,統合後の支店にはATMを1台設置する。統合後のATMの平均待ち時間を求める式はどれか。ここで,待ち時間はM/M/1の待ち行列モデルに従い,平均待ち時間にはサービス時間を含まず,ATMを1台に統合しても十分に処理できるものとする。
〔条件〕
(1)統合後の平均サービス時間:Ts
(2)統合前のATMの利用率:両支店ともρ
(3)統合後の利用者数:統合前の両支店の利用者数の合計
H27h-1


【正解】エ

(3)H26秋AP問3
問3 コンピュータによる伝票処理システムがある。このシステムは,伝票データをためる待ち行列をもち, M/M/1の待ち行列モデルが適用できるものとする。平均待ち時間がT秒以上となるのは,処理装置の利用率が少なくとも何%以上となったときか。ここで,伝票データをためる待ち行列の特徴は次のとおりである。
  ・伝票データは,ポアソン分布に従って発生する。
  ・伝票データのたまる数に制限はない。
  ・1件の伝票データの処理時間は,平均T秒の指数分布に従う。
ア 33   イ 50   ウ 67   エ 80


【正解】イ

(4)H25秋AP問5
問5 通信回線を使用したデータ伝送システムにM/M/1の待ち行列モデルを適用すると,平均回線待ち時間,平均伝送時間,回線利用率の関係は,次の式で表すことができる。
h25a-5
 回線利用率が0%から徐々に上がっていく場合,平均回線待ち時間が平均伝送時間よりも最初に長くなるのは,回線利用率が何%を超えたときか。
ア 40   イ 50   ウ 60   エ 70




【正解】イ

(5)H20問秋AD午前問13
問13 待ち行列モデルの適用事例として,適切なものはどれか。
ア 1回当たりの発注コスト, 1個当たりの在庫維持コストなどを基に,在庫商品の発注量を決定する。
イ 過去何年か分の売上データを時系列に並べ,推移状況を比較することによって,次年度の売上を予測する。
ウ 画像情報の密度,大きさ,平均圧縮率,通信速度などを基に,必要な通信時間を計算する。
エ 電話の平均受付回数,平均対応時間などを基に,問合せに対応するサービスデスクの要員数を決定する。



正解は、エです。

殿扇子で指示試験センターが発表する試験範囲の1つに、「情報セキュリティの運用・管理に関すること」があります。

ITILの中には「セキュリティ管理」というテーマはありません。ですが、セキュリティ管理は運用管理部門における大切な業務であり、過去の出題も多かったため、注意深く学習する必要があります。

一例ですが、H20SU午後Ⅱの問題に、パスワードの運用ルールに関する例があります。覚える必要はありませんし、それほど重要とは思いませんが、一読の価値はあるでしょう。

・パスワードを保存する場合には、その内容を暗号化すること
・パスワードを送信する場合には、その内容を暗号化すること
・利用者に対し、定期的にパスワードを変更するように促すこと
・利用者が自らパスワードを変更できること
・利用者が定期的にパスワードを変更していることを、管理者が確認できること
・利用者が定期的にパスワードを変更しないと、その利用者はシステムを利用できなくなること
・破られやすいパスワードは設定できないこと
・それまでに利用していたパスワードは再設定できないこと。
図2 パスワード管理に関するセキュリティ要件(H20SU午後Ⅱ問1より引用)

 

↑このページのトップヘ