基本情報技術者(科目A)過去問集 - 情報に関する理論

AIにおけるディープラーニングに最も関連が深いものはどれか。

次の方式によって求められるチェックデジットを付加した結果はどれか。ここで，データを 7394，重み付け定数を 1234，基数を 11 とする。

〔方式〕
（1）データと重み付け定数の，対応する桁ごとの積を求め，それらの和を求める。
（2）和を基数で割って，余りを求める。
（3）基数から余りを減じ，その結果の1の位をチェックデジットとしてデータの末尾に付加する。

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

	0	1
a	a	b
b	c	d
c	a	b
d	c	d

UNIXにおける正規表現 [A-Z]+[0-9]* が表現する文字列の集合の要素となるものはどれか。ここで，正規表現は次の規則に従う。

[A-Z] は，大文字の英字1文字を表す。
[0-9] は，数字1文字を表す。
+は，直前の正規表現の1回以上の繰返しであることを表す。
*は，直前の正規表現の0回以上の繰返しであることを表す。

次のBNFにおいて非終端記号〈A〉から生成される文字列はどれか。

〈R₀〉::= 0 | 3 | 6 | 9
〈R₁〉::= 1 | 4 | 7
〈R₂〉::= 2 | 5 | 8
〈A〉::=〈R₀〉|〈A〉〈R₀〉|〈B〉〈R₂〉|〈C〉〈R₁〉
〈B〉::=〈R₁〉|〈A〉〈R₁〉|〈B〉〈R₀〉|〈C〉〈R₂〉
〈C〉::=〈R₂〉|〈A〉〈R₂〉|〈B〉〈R₁〉|〈C〉〈R₀〉

次に示す計算式と逆ポーランド表記法の組合せのうち，適切なものはどれか。

	計算式	逆ポーランド表記法
ア	((a+b*c)-d	abc*+d-
イ	(a+(b*c))-d	ab+c*d-
ウ	(a+b)*(c-d)	abc*d-+
エ	a+(b*(c-d))	abcd-*+

逆ポーランド表記法（後置表記法）で，“EF-G÷CD-AB+÷+” と表現される式はどれか。

次の式を逆ポーランド表記法で表現したものはどれか。

$\frac{(A+B)\times (C+D)}{A-D}$

英字の大文字（A～Z）と数字（0～9）を同一のビット数で一意にコード化するには，少なくとも何ビットが必要か。

機械学習における教師あり学習の説明として，最も適切なものはどれか。

探索方法とその実行時間のオーダの適切な組合せはどれか。ここで，探索するデータの数をnとし，ハッシュ値が衝突する（同じ値になる）確率は無視できるほど小さいものとする。また，実行時間のオーダがn²であるとは，n個のデータを処理する時間がcn²（cは定数）で抑えられることをいう。

	2分探索	線形探索	ハッシュ探索
ア	log2n	n	1
イ	nlog2n	n	log2n
ウ	nlog2n	n2	1
エ	n2	1	n

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

	a	b	c	d
ア	0	1	00	11
イ	0	01	10	11
ウ	0	10	110	111
エ	00	01	10	11

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

コンパイラで構文解析した結果の表現方法の一つに四つ組形式がある。
（演算子，被演算子1，被演算子2，結果）
この形式は，被演算子1と被演算子2に演算子を作用させたものが結果であることを表す。次の一連の四つ組は，どの式を構文解析したものか。ここで，T₁，T₂，T₃ は一時変数を表す。

（＊，B，C，T₁）
（／，T₁，D，T₂）
（＋，A，T₂，T₃）

入力記号，出力記号の集合が {0，1} であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，入力記号は左から順に読み込まれるものとする。また，S₁は初期状態を表し，遷移の矢印のラベルは，入力/出力を表している。

〔状態遷移図〕

図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bの適切な組合せはどれか。

	a	b
ア	0	0
イ	0	1
ウ	1	0
エ	1	1

表は，文字 A〜E を符号化したときのビット表記と，それぞれの文字の出現確率を表したものである。1文字当たりの平均ビット数は幾らか。

文字	ビット表記	出現確率（%）
A	0	50
B	10	30
C	110	10
D	1110	5
E	1111	5

後置記法（逆ポーランド記法）では，例えば，式 Y=(A-B)×C を YAB-C×= と表現する。次の式を後置記法で表現したものはどれか。
　Y=(A+B)×(C-D÷E)

アナログ電圧をディジタル化した後に演算処理することの利点として，適切なものはどれか。

次のBNFで定義される＜変数名＞に合致するものはどれか。

＜数字＞::=0|1|2|3|4|5|6|7|8|9
＜英字＞::=A|B|C|D|E|F
＜英数字＞::=＜英字＞|＜数字＞|_
＜変数名＞::=＜英字＞|＜変数名＞＜英数字＞

表は，文字列を検査するための状態遷移表である。検査では，初期状態をaとし，文字列の検査中に状態がeになれば不合格とする。
解答群で示される文字列のうち，不合格となるものはどれか。ここで，文字列は左端から検査し，解答群中の△は空白を表す。

		文字
		空白	数字	符号	小数点	その他
現 在 の 状 態	a	a	b	c	d	e
	b	a	b	e	d	e
	c	e	b	e	d	e
	d	a	e	e	e	e

AIにおける機械学習の説明として，最も適切なものはどれか。

出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれか。

文字	出現頻度（%）	符号
A	26	00
B	25	01
C	24	10
D	13	[　a　]
E	12	111

AIにおけるディープラーニングの特徴はどれか。

送信側では，ビット列をある生成多項式で割った余りをそのビット列に付加して送信し，受信側では，受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する誤り検査方式はどれか。

次の状態遷移表をもつシステムの状態がS1であるときに，信号をt1，t2，t3，t4，t1，t2，t3，t4の順に入力すると，最後の状態はどれになるか。ここで，空欄は状態が変化しないことを表す。

		状態
		S1	S2	S3	S4
信 号	t1		S3
	t2	S3		S2
	t3			S4	S1
	t4		S1		S2

図で表される有限オートマトンで受理される文字列はどれか。ここで，⇨○ は初期状態を，◎ は受理状態を表す。

次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。

モジュラス11などの計算方法によって得られた結果を商品コードなどの末尾に付加し，入力の誤りを入力データだけから発見できるようにする方法がある。この末尾に付加されるものを何というか。

入力されたビットに対して出力されるビットが0か1のいずれかである確率を遷移確率という。遷移確率を表にしたとき，a，b，c，dの関係はどれか。

		出力
		0	1
入 力	0	a	b
	1	c	d

4桁の整数 N₁N₂N₃N₄ から，次の方法によって検査数字（チェックディジット）Cを計算したところ，C=4となった。N₂=7，N₃=6，N₄=2 のとき，N₁の値は幾らか。ここで，mod（x，y）は，xをyで割った余りとする。

検査数字：C = mod（（N₁×1+N₂×2+N₃×3+N₄×4），10）

チェックディジットを利用する目的として，適切なものはどれか。

図は，逆ポーランド表記法で書かれた式 abcd+++ をスタックで処理するときのスタックの変化の一部を表している。この場合，スタックの深さは最大で4となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。

図は70円切符の自動販売機に硬貨が投入されたときの状態遷移を表している。状態Q₄から状態Eへ遷移する事象はどれか。ここで，状態Q₀は硬貨が投入されていない状態であり，硬貨が1枚投入されるたびに状態は矢印の方向へ遷移するものとする。なお，状態Eは投入された硬貨の合計が70円以上になった状態であり，自動販売機は切符を発行し，釣銭が必要な場合には釣銭を返す。また，自動販売機は10円硬貨，50円硬貨，100円硬貨だけを受け付けるようになっている。

次の規則から生成することができる式はどれか。

〔規則〕
＜式＞ ::= ＜変数＞｜（＜式＞＋＜式＞）｜＜式＞＊＜式＞
<変数> ::= A｜B｜C｜D

四則演算の式の書き方には，演算子をオペランドの前に書く方法（前置記法），オペランドの間に書く方法（中置記法），オペランドの後に書く方法（後置記法）の3通りがある。図は，2分木で表現された式のたどり方と，各記法によって表される式を例示したものである。


各記法で式を書く手順の説明として，適切なものはどれか。

数値に関する構文が次のとおり定義されているとき，＜数値＞として扱われるものはどれか。

＜数値＞ ::= ＜数字列＞|＜数字列＞E＜数字列＞|＜数字列＞E＜符号＞＜数字列＞
＜数字列＞ ::= ＜数字＞|＜数字列＞＜数字＞
＜数字＞ ::= 0|1|2|3|4|5|6|7|8|9
＜符号＞ ::= +|-

A=1，B=3，C=5，D=4，E=2のとき，逆ポーランド表記法で表現された式 AB+CDE/-* の演算結果はどれか。

文字列中で同じ文字が繰り返される場合，繰返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法はどれか。