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

 

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



正解は、オです。

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

 

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 はどうなるかというと、(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+などと表記するので、後置記法と言われます。
スタックの流れは以下です。

sm.seeeko.com


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

 

1.制御に関する理論

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

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

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

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

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

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

2.ジャイロセンサ

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

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

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

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




【正解】イ

 

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




【正解】イ

 

↑このページのトップヘ