基礎理論(基数変換・論理演算・オートマトン・確率)

基本情報技術者試験(FE)は、情報処理の促進に関する法律に基づきIPA(独立行政法人情報処理推進機構)が実施する国家試験であり、2023年4月以降は通年実施のCBT方式に全面移行した。試験は科目A(四肢択一60問・90分)と科目B(20問・100分)の2科目で構成され、採点は項目応答理論(IRT)に基づく評価点方式で、両科目とも1,000点満点中600点以上が合格基準である。本章で扱う「基礎理論」は、IPAが公表する試験要綱・シラバスのテクノロジ系大分類1に位置づけられ、離散数学(基数、集合、論理演算)、応用数学(確率・統計)、情報に関する理論(オートマトン、形式言語)を含む。科目Aの中でも計算問題として安定して出題される領域であり、科目Bのアルゴリズム問題やハードウェア・ネットワーク分野の理解の土台にもなるため、最初に確実な得点源へ仕上げることが合格戦略上重要である。

基数変換は科目Aの最頻出論点の一つである。10進整数をn進数へ変換するには「基数で割って余りを下から読む」、10進小数は「基数を掛けて整数部を上から読む」のが原則である。例えば10進数13は、13÷2=6余り1、6÷2=3余り0、3÷2=1余り1、1÷2=0余り1から1101(2進)となり、10進数0.625は0.625×2=1.25、0.25×2=0.5、0.5×2=1.0の整数部を順に並べて0.101となる。また16進数1桁は2進数4桁、8進数1桁は2進数3桁に正確に対応するため、2進数を経由すれば相互変換が速い。注意すべきは、10進数では有限小数である0.1や0.2が2進数では循環小数となり有限桁で表現できない点で、これが浮動小数点演算の誤差の根本原因として出題される。基数変換は後述の補数表現やシフト演算(左1ビットシフトで2倍、右シフトで1/2倍)とも直結する基本技能である。

コンピュータ内部の負数は2の補数で表現するのが標準である。2の補数は「全ビットを反転して1を加える」ことで得られ、nビットで表現できる整数の範囲は-2^(n-1)から2^(n-1)-1までとなる。8ビットなら-128〜+127であり、正負の範囲が非対称である点、および符号絶対値表現や1の補数では0の表現が2通り生じる点がひっかけとして問われる。実数は浮動小数点数(符号部・指数部・仮数部から成り、IEEE 754が代表的規格)で表現するが、有限桁ゆえに誤差が避けられない。値がほぼ等しい数値同士の減算で有効桁数が減る「けた落ち」、絶対値の差が大きい数値の加減算で小さい値が結果に反映されない「情報落ち」、四捨五入や切捨てによる「丸め誤差」、無限級数の計算を有限項で打ち切ることによる「打切り誤差」という、誤差の名称と現象の対応は科目Aで繰り返し出題される定番論点である。

論理演算は真理値表で定義を正確に押さえることが出発点である。論理積(AND)は両入力が1のときだけ1、論理和(OR)は少なくとも一方が1なら1、否定(NOT)は反転、排他的論理和(XOR)は「二つの入力が異なるとき」に1となる。ANDとXORの混同は頻出のひっかけであり、同じ値同士のXORが必ず0になる性質は一致判定やビット反転の応用問題で使われる。恒等式ではド・モルガンの法則¬(A∧B)=¬A∨¬B、¬(A∨B)=¬A∧¬Bが最重要で、論理式の簡略化や等価な式を選ぶ問題の根拠となる。応用としてビット操作があり、特定ビットの取出しはANDによるマスク、特定ビットを1にセットするのはOR、反転はXORで行う。さらに論理回路では、XORが和・ANDが桁上げを出力する半加算器、下位からの桁上げも扱う全加算器の構成が、ハードウェア分野との境界領域として出題される。

有限オートマトンは、状態の有限集合、入力記号の集合、状態遷移関数、初期状態、受理状態の集合の5項組で定義される計算モデルであり、シラバス上は「情報に関する理論」に属する。科目Aでは状態遷移図または状態遷移表を与え、「受理される入力列はどれか」「入力列を与えたときの最終状態はどれか」を問う形式が定番である。解法は、初期状態から入力記号を1文字ずつ読んで遷移をたどり、入力終了時に受理状態にあるかを確認するだけであり、手順どおりに処理すれば確実に得点できる。理論面では、有限オートマトンが受理できる言語は正規表現で表される正規言語と一致すること、非決定性有限オートマトン(NFA)は部分集合構成法により等価な決定性有限オートマトン(DFA)へ変換でき、両者の受理能力が等しいことを押さえる。また、プログラム言語の構文定義に用いるBNF(バッカス・ナウア記法)も同分野の頻出項目で、生成規則から導出できる文字列を選ばせる問題が出る。

確率は応用数学分野の中心である。まず場合の数として、異なるn個からr個を取り出して並べる順列nPr=n!/(n-r)!と、順序を問わない組合せnCr=n!/(r!(n-r)!)を確実に計算できるようにする。確率計算では、二つの事象が「排反」(同時には起こらない)ならば加法定理P(A∪B)=P(A)+P(B)が、「独立」(一方の結果が他方に影響しない)ならば乗法定理P(A∩B)=P(A)×P(B)が成り立つ。排反と独立の混同は本章で最も多いひっかけである。玉の取出し問題では、取り出した玉を戻す復元抽出は独立試行として確率の積で、戻さない非復元抽出は組合せの比または条件付き確率P(B|A)=P(A∩B)/P(A)で処理する。期待値は「各値×その確率」の総和で求め、くじ引きや信頼性(稼働率)の問題に応用される。統計側では平均・分散・標準偏差の定義と正規分布の性質が問われる。

学習戦略としては、基礎理論は暗記量が少なく、手順の習熟がそのまま得点になる分野であることを意識したい。科目Aは60問90分で1問当たり平均90秒であり、基数変換や確率の計算は途中式を省かず素早く正確に処理する訓練が必要である。CBT会場ではメモ用紙と筆記用具が貸与されるため、2の補数や真理値表は迷わず書き出して確かめるのが安全である。教材はIPAが公式サイトで公開する試験要綱・シラバスと科目A・科目Bの公開問題(サンプル問題)が一次情報であり、旧制度の午前試験の過去問題も科目Aと出題水準が連続しているため演習素材として有効である。本章の論点は、2進数がハードウェアへ、論理演算が回路設計とセキュリティへ、オートマトンがコンパイラや正規表現へ、確率が稼働率計算へと後続章で再登場する。ここで解法を体に染み込ませておけば、試験全体を通じて計算問題の処理効率が上がる。