このページでは，基本情報技術者試験を中心に，基礎理論（情報に関する理論）分野の過去問題・サンプル問題・公開問題を掲載しています。アナログ／ディジタル変換，符号化（ハフマン符号化，ランレングス符号化），オートマトン（状態遷移表・状態遷移図），正規表現，形式言語（BNF，逆ポーランド表記法），AI（機械学習，ディープラーニング）など，試験で頻出のテーマについて，解答だけでなく図や表を使って解説しています。解けなかった問題は，各問題下の【参考】リンクから対応する解説ページを読み，理解した上でもう一度解いてみてください。
平成27年度 基本情報技術者試験 秋期 午前 問4
問 アナログ電圧をディジタル化した後に演算処理することの利点として，適切なものはどれか。
ア アナログからディジタルへの変換では誤差が発生しない。
イ 演算結果が部品精度，温度変化及び外来雑音の影響を受けにくい。
ウ 数値演算において丸め誤差が発生することはない。
エ 電圧が変化してから演算結果を得るまでの遅延時間が発生しない。
【解答】イ
【解説】
アナログ値（連続的な値）からディジタル値（離散値）へ変換する場合，一定間隔ごとにサンプリングするので誤差が生じる（サンプリングの間隔が広かったり，少ないビットでサンプリングすると誤差が大きくなる）。
アナログ値は波として表されるので，ノイズが発生すると，その影響を受ける。一方，ディジタル値は一定範囲内の値であれば同じディジタル値に変換されるので，多少のノイズであれば影響を受けない。
ウ 演算過程で，丸め誤差が発生することがある。
エ ディジタル化する際に，遅延が発生することがある。
| 【参考】 |
平成30年度 基本情報技術者試験 秋期 午前 問4
問 出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれか。
| ア 001 | イ 010 | ウ 101 | エ 110 |
【解答】エ
【解説】
2分木構造を利用すると，
となる。
平成23年度 基本情報技術者試験 特別 午前 問3
問 表は，文字A～Eを符号化したときのビット表記と，それぞれの文字の出現確率を表したものである。1文字当たりの平均ビット数は幾らになるか。
| ア 1.6 | イ 1.8 | ウ 2.5 | エ 2.8 |
【解答】イ
【解説】
1文字当たりの平均ビット数は，各文字のビット数と出現確率を掛けた値を足すことにより求めることができる。
A：1ビット × 0.5（50%）＝ 0.5
B：2ビット × 0.3（30%）＝ 0.6
C：3ビット × 0.1（10%）＝ 0.3
D：4ビット × 0.05（5%）＝ 0.2
E：4ビット × 0.05（5%）＝ 0.2
よって，
平均ビット数 ＝ 0.5 ＋ 0.6 ＋ 0.3 ＋ 0.2 ＋ 0.2 ＝ 1.8
となる。
平成21年度 基本情報技術者試験 春期 午前 問4
問 文字列中で同じ文字が繰り返される場合，繰返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法はどれか。
| ア EBCDIC符号 | イ 巡回符号 |
| ウ ハフマン符号 | エ ランレングス符号化 |
【解答】エ
【解説】
ランレングス符号化
文字列（や記号列）を符号化する際，同じ文字が繰り返し出現する部分を「反復回数と文字」という形に置き換えて，全体のデータ量を少なくする圧縮方法。
平成27年度 基本情報技術者試験 春期 午前 問4
問 入力されたビット列に対して出力されるビットが0か1のいずれかである確率を遷移確率という。遷移確率を表にしたとき，a，b，c，dの関係はどれか。
| ア a ＋ b ＋ c ＋ d ＝ 1 | イ a ＋ b ＝ 1，c ＋ d ＝ 1 |
| ウ a ＋ c ＝ 1，b ＋ d ＝ 1 | エ a ＋ d ＝ 1，b ＋ c ＝ 1 |
【解答】イ
【解説】
状態遷移表は，次のようにみる。
平成26年度 基本情報技術者試験 春期 午前 問5
平成23年度 基本情報技術者試験 特別 午前 問4
問 表は，文字列を検査するための状態遷移表である。検査では，初期状態をaとし，文字列の検査中に状態がeになれば不合格とする。
解答群で示される文字列のうち，不合格となるものはどれか。ここで，文字列は左端から検査し，解答群中の△は空白を表す。
| ア ＋0010 | イ －1 | ウ 12.2 | エ 9.△ |
【解答】ウ
【解説】
状態遷移表で，各選択肢を調べると，
| ア |  |
| イ |  |
| ウ |  |
| エ |  |
となる。
（令和4年度） 基本情報技術者試験 サンプル問題 科目A 問4
平成30年度 基本情報技術者試験 春期 午前 問4
問 入力記号，出力記号の集合が {0, 1} であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，入力記号は左から順に読み込まれるものとする。また，S1 は初期状態を表し，遷移の矢印のラベルは，入力／出力を表している。
〔状態遷移図〕
| ア 0001000110 | イ 0001001110 |
| ウ 0010001000 | エ 0011111110 |
【解答】ア
【解説】
状態遷移図に 0011001110 を順に入力すると，
となる。
平成28年度 基本情報技術者試験 春期 午前 問2
問 次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。
| ア 0000 | イ 0111 | ウ 1010 | エ 1111 |
【解答】ウ
【解説】
状態遷移図の各状態を，下図のように左から順にS0，S1，S2としてみると，
| ア |  |
| イ |  |
| ウ |  |
| エ |  |
となる。
平成28年度 基本情報技術者試験 秋期 午前 問3
問 300円の商品を販売する自動販売機の状態遷移図はどれか。ここで，入力と出力の関係を “入力／出力” で表し，入力の “a” は “100円硬貨” を，“b” は “100円硬貨以外” を示し，S0 ～ S2 は状態を表す。入力が “b” の場合はすぐにその硬貨を返却する。また，終了状態に遷移する際，出力の “1” は商品の販売を，“0” は何もしないことを示す。
ア  | イ  |
ウ  | エ  |
【解答】ア
【解説】
300円の商品を販売する状態遷移図を，問題に従い作成すると，
となる。
平成24年度 基本情報技術者試験 春期 午前 問5
問 図は70円切符の自動販売機に硬貨が投入されたときの状態遷移を表している。状態 Q4 から状態 E へ遷移する事象はどれか。ここで，状態 Q0 は硬貨が投入されていない状態であり，硬貨が1枚投入されるたびに状態は矢印の方向へ遷移するものとする。
なお，状態 E は投入された硬貨の合計が70円以上になった状態であり，自動販売機は切符を発行し，釣銭が必要な場合には釣銭を返す。また，自動販売機は10円硬貨，50円硬貨，100円硬貨だけを受け付けるようになっている。
ア 10円硬貨が投入された。
イ 10円硬貨又は50円硬貨が投入された。
ウ 10円硬貨又は100円硬貨が投入された。
エ 50円硬貨又は100円硬貨が投入された。
【解答】エ
【解説】
状態遷移図に，遷移のようすを書き込むと次のようになる。
平成28年度 基本情報技術者試験 春期 午前 問3
問 UNIXにおける正規表現 [A－Z] ＋ [0－9] ＊ が表現する文字列の集合の要素となるものはどれか。ここで，正規表現は次の規則に従う。
[A－Z] は，大文字の英字1文字を表す。
[0－9] は，数字1文字を表す。
＋は，直前の正規表現の1回以上の繰返しであることを表す。
＊は，直前の正規表現の0回以上の繰返しであることを表す。
| ア 456789 | イ ABC＋99 | ウ ABC99＊ | エ ABCDEF |
【解答】エ
【解説】
正規表現 [A－Z] ＋ [0－9] ＊ は，
大文字の英字1文字以上の繰り返しと，数字0文字以上の繰り返し
という意味なので，
ア 数字から始まっている ⇒ ×
イ ＋記号が含まれている ⇒ ×
ウ ＊記号が含まれている ⇒ ×
エ 6文字の英字と，0文字の数字 ⇒ ○
となる。
平成23年度 基本情報技術者試験 秋期 午前 問4
問 次の規則から生成することができる式はどれか。
〔規則〕
＜式＞ ::＝ ＜変数＞ | (＜式＞＋＜式＞) | ＜式＞＊＜式＞
＜変数＞ ::＝ A | B | C | D
| ア A＋ (B＋C) ＊D | イ (A＋B) ＋ (C＋D) |
| ウ (A＋B) ＊ (C＋D) | エ (A＊B) ＋ (C＊D) |
【解答】ウ
【解説】
各選択肢を，順に調べると，
ア ＜変数＞＋ (＜変数＞＋＜変数＞) ＊＜変数＞
⇒ ＜式＞＋ (＜式＞＋＜式＞) ＊＜式＞
⇒ ＜式＞＋＜式＞＊＜式＞
⇒ ＜式＞＋＜式＞
＜式＞の形にはならない。
イ (＜変数＞＋＜変数＞) ＋ (＜変数＞＋＜変数＞)
⇒ (＜式＞＋＜式＞) ＋ (＜式＞＋＜式＞)
⇒ ＜式＞＋＜式＞
＜式＞の形にはならない。
ウ (＜変数＞＋＜変数＞) ＊ (＜変数＞＋＜変数＞)
⇒ (＜式＞＋＜式＞) ＊ (＜式＞＋＜式＞)
⇒ ＜式＞＊＜式＞
⇒ ＜式＞
エ (＜変数＞＊＜変数＞) ＋ (＜変数＞＊＜変数＞)
⇒ (＜式＞＊＜式＞) ＋ (＜式＞＊＜式＞)
⇒ (＜式＞) ＋ (＜式＞)
＜式＞の形にはならない。
令和元年度 基本情報技術者試験 秋期 午前 問7
問 次のBNFで定義される＜変数名＞に合致するものはどれか。
＜数字＞ ::＝ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
＜英字＞ ::＝ A | B | C | D | E | F
＜英数字＞ ::＝ ＜英字＞ | ＜数字＞ | _
＜変数名＞ ::＝ ＜英字＞ | ＜変数名＞＜英数字＞
| ア _B39 | イ 246 | ウ 3E5 | エ F5_1 |
【解答】エ
【解説】
各選択肢を，順に調べると，
ア ＜英数字＞＜英字＞＜数字＞＜数字＞
⇒ 先頭が＜英数字＞となるので＜変数名＞の形にはならない。
イ ＜数字＞＜数字＞＜数字＞
⇒ ＜英数字＞＜英数字＞＜英数字＞
⇒ 先頭が＜英数字＞となるので＜変数名＞の形にはならない。
ウ ＜数字＞＜英字＞＜数字＞
⇒ ＜英数字＞＜変数名＞＜英数字＞
⇒ ＜英数字＞＜変数名＞
⇒ 先頭が＜英数字＞となるので＜変数名＞の形にはならない。
エ ＜英字＞＜数字＞＜英数字＞＜数字＞
⇒ ＜変数名＞＜英数字＞＜英数字＞＜英数字＞
⇒ ＜変数名＞＜英数字＞＜英数字＞
⇒ ＜変数名＞＜英数字＞
⇒ ＜変数名＞
となる。
平成24年度 基本情報技術者試験 春期 午前 問4
問 後置記法（逆ポーランド記法）では，例えば，式 Y＝ (A－B) ×C を YAB－C×＝ と表現する。次の式を後置記法で表現したものはどれか。
Y＝ (A＋B) × (C－D÷E)
| ア YAB＋C－DE÷×＝ | イ YAB＋CDE÷－×＝ |
| ウ YAB＋EDC÷－×＝ | エ YBA＋CD－E÷×＝ |
【解答】イ
【解説】
計算式を逆ポーランド表記法で記述するには，通常の計算式の計算と同じ順に，演算子を被演算子の後ろに記述していけばよい。
Y＝ (A＋B) × (C－D÷E)
⇒ Y＝AB＋× (C－DE÷)
⇒ Y＝AB＋×CDE÷－
⇒ Y＝AB＋CDE÷－×
⇒ YAB＋CDE÷－×＝
となる。
平成26年度 基本情報技術者試験 秋期 午前 問4
問 次に示す計算式と逆ポーランド表記法の組合せのうち，適切なものはどれか。
計算式 | 逆ポーランド表記法 | |
| ア | ((a＋b) ＊c) －d | abc＊＋d－ |
| イ | (a＋ (b＊c)) －d | ab＋c＊d－ |
| ウ | (a＋b) ＊ (c－d) | abc＊d－＋ |
| エ | a＋ (b＊ (c－d)) | abcdー＊＋ |
【解答】エ
【解説】
計算式を逆ポーランド表記法で記述するには，通常の計算式の計算と同じ順に，演算子を被演算子の後ろに記述していけばよい。
ア ((a＋b) ＊c) －d
⇒ (ab＋＊c) －d
⇒ ab＋c＊－ d
⇒ ab＋c＊d－
イ (a＋ (b＊c)) －d
⇒ (a＋bc＊) －d
⇒ abc＊＋－d
⇒ abc＊＋d－
ウ (a＋b) ＊ (c－d)
⇒ ab＋＊cd－
⇒ ab＋cd－＊
エ a＋ (b＊ (c－d))
⇒ a＋ (b＊cd－)
⇒ a＋bcd－＊
⇒ abcd－＊＋
平成25年度 基本情報技術者試験 春期 午前 問6
問 図は，逆ポーランド表記法で書かれた式 abcd+++ をスタックで処理するときのスタックの変化の一部を表している。この場合，スタックの深さは最大で4となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。
| ア ab+c+d+ | イ ab+cd++ |
| ウ abc++d+ | エ abc+d++ |
【解答】ア
【解説】
ア スタックの深さは最大で，2
イ スタックの深さは最大で，3
ウ スタックの深さは最大で，3
エ スタックの深さは最大で，3
平成21年度 基本情報技術者試験 秋期 午前 問3
問 逆ポーランド表記法（後置表記法）で，“ EF－G÷CD－AB＋÷＋ ” と表現される式はどれか。
ア ((A＋B) ＋ (C－D)) ÷G－ (E÷F)
イ ((A＋B) ÷ (C－D)) ＋G÷ (E－F)
ウ ((E－F) ÷G) ＋ ((C－D) ÷ (A＋B))
エ ((E－F) ÷G) ÷ ((C－D) ＋ (A＋B))
【解答】ウ
【解説】
逆ポーランド表記法で記述された演算式は，スタックを用いて計算することができる。
平成22年度 基本情報技術者試験 春期 午前 問3
問 A＝1，B＝3，C＝5，D＝4，E＝2 のとき，逆ポーランド表記法で表現された式 AB＋CDE／－＊ の演算結果はどれか。
| ア －12 | イ 2 | ウ 12 | エ 14 |
【解答】ウ
【解説】
逆ポーランド表記法で記述された演算式は，スタックを用いて計算することができる。
(A＋B) ＊ (C－D／E)
＝ (1＋3) ＊ (5－4／2)
＝ 4 ＊ (5－2)
＝ 4 ＊ 3
＝ 12
となる。
平成30年度 基本情報技術者試験 秋期 午前 問3
問 AIにおける機械学習の説明として，最も適切なものはどれか。
ア 記憶したデータから特定のパターンを見つけ出すなどの，人が自然に行っている学習能力をコンピュータにもたせるための技術
イ コンピュータ，機械などを使って，生命現象や進化のプロセスを再現するための技術
ウ 特定の分野の専門知識をコンピュータに入力し，入力された知識を用いてコンピュータが推論する技術
エ 人が双方向学習を行うために，Webシステムなどの情報技術を用いて，教材や学習管理能力をコンピュータにもたせるための技術
【解答】ア
【解説】
機械学習とは，（データから特定のパターンを見つけ出すような）人間が行っている学習能力をコンピューターに持たせるための技術のことをいう。
学習能力をプログラムして大量のデータを与えることにより，コンピューター自身が自律的に最適な制御を行えるようになる。
令和元年度 基本情報技術者試験 秋期 午前 問73
問 生産現場における機械学習の活用事例として，適切なものはどれか。
ア 工場における不良品の発生原因をツリー状に分解して整理し，アナリストが統計的にその原因や解決策を探る。
イ 工場の生産設備を高速通信で接続し，ホストコンピュータがリアルタイムで制御できるようにする。
ウ 工場の生産ロボットに対して作業方法をプログラミングするのではなく，ロボット自らが学んで作業の効率を高める。
エ 累積生産量が倍増するたびに工場従業員の生産性が向上し，一定の比率で単位コストが減少する。
【解答】ウ
【解説】
機械学習とは，（データから特定のパターンを見つけ出すような）人間が行っている学習能力をコンピューターに持たせるための技術のことをいう。
学習能力をプログラムして大量のデータを与えることにより，コンピューター自身が自律的に最適な制御を行えるようになる。
平成31年度 基本情報技術者試験 春期 午前 問4
問 機械学習における教師あり学習の説明として，最も適切なものはどれか。
ア 個々の行動に対しての良しあしを得点として与えることによって，得点が最も多く得られるような方策を学習する。
イ コンピュータ利用者の挙動データを蓄積し，挙動データの出現頻度に従って次の挙動を推論する。
ウ 正解のデータを提示したり，データが誤りであることを指摘したりすることによって，未知のデータに対して正誤を得ることを助ける。
エ 正解のデータを提示せずに，統計的性質や，ある種の条件によって入力パターンを判定したり，クラスタリングしたりする。
【解答】ウ
【解説】
機械学習とは，（データから特定のパターンを見つけ出すような）人間が行っている学習能力をコンピューターに持たせるための技術のことをいう。
| 教師あり学習 | データと，その正解を与えて規則性などを学習させ，未知のデータに対して正誤を判断できるようにする方式 例）需要予測など |
| 教師なし学習 | データのみを与えて（正解は与えない），規則性や特徴などを見つけ，グループ化する方式 例）クラスタリング |
| 強化学習 | それぞれの行動に対して得点（評価，報酬）を与え，最善の（最も多く点が取れる）行動を学習する方式 例）ロボットの制御，将棋や碁のゲーム |
平成30年度 基本情報技術者試験 春期 午前 問3
問 AIにおけるディープラーニングの特徴はどれか。
ア “AならばBである” というルールを人間があらかじめ設定して，新しい知識を論理式で表現したルールに基づく推論の結果として，解を求めるものである。
イ 厳密な解でなくてもなるべく正解に近い解を得るようにする方法であり，特定分野に特化せずに，広範囲で汎用的な問題解決ができるようにするものである。
ウ 人間の脳神経回路を模倣して，認識などの知能を実現する方法であり，ニューラルネットワークを用いて，人間と同じような認識ができるようにするものである。
エ 判断ルールを作成できる医療診断などの分野に限定されるが，症状から特定の病気に絞り込むといった，確率的に高い判断ができる。
【解答】ウ
【解説】
ディープラーニング（深層学習）とは，ニューラルネットワークの隠れ層が複数あるものを使用して，より複雑な学習をできるようにしたものをいう。
■ニューラルネットワーク
ニューラルネットワークとは，人間の神経網を模倣したモデルのことをいう。
※ パーセプトロン…ニューロン（人間の脳にある神経細胞）をモデル化したもの
| 【参考】 | 「情報に関する理論－AI －情報処理シンプルまとめ」 |
平成29年度 基本情報技術者試験 秋期 午前 問74
問 車載機器の性能の向上に関する記述のうち，ディープラーニングを用いているものはどれか。
ア 車の壁への衝突を加速度センサが検知し，エアバッグを膨らませて搭乗者をけがから守った。
イ システムが大量の画像を取得し処理することによって，歩行者と車をより確実に見分けることができるようになった。
ウ 自動でアイドリングストップする装置を搭載することによって，運転経験が豊富な運転者が運転する場合よりも燃費を向上させた。
エ ナビゲーションシステムが，携帯電話回線を通してソフトウェアのアップデートを行い，地図を更新した。
【解答】イ
【解説】
ディープラーニング（深層学習）とは，ニューラルネットワークの隠れ層が複数あるものを使用して，より複雑な学習をできるようにしたものをいう。
■ニューラルネットワーク
ニューラルネットワークとは，人間の神経網を模倣したモデルのことをいう。
※ パーセプトロン…ニューロン（人間の脳にある神経細胞）をモデル化したもの
| 【参考】 | 「情報に関する理論－AI －情報処理シンプルまとめ」 |
まとめ
今回は，基本情報技術者試験の過去問題・サンプル問題・公開問題のうち，基礎理論（情報に関する理論）分野に関するものを集め，シンプルにまとめてみました。みなさんは，どのくらい解けましたか？はじめは難しく感じるかもしれませんが，繰り返し問題を解くことで，少しずつ理解できるようになると思います。8割以上（できれば9割以上）解けるようになることを目標に，ぜひ取り組んでみてください。また，一度解けるようになっても，時間が経つと忘れてしまうことがあります。1週間後や1か月後など，期間をあけてもう一度解き直すことで，理解の定着につながると思います。
