基礎理論 ― 離散数学・応用数学・情報理論・通信理論

基数と数値の表現・演算精度

コンピュータは 2 進数で数を扱いますが、人間が読み書きするのは 10 進数、メモリダンプやアドレスは 16 進数です。基数（何種類の数字を使うか）を切り替える計算は、本章のほぼ全ての計算問題の土台になります。位ごとに「基数の何乗」という重みが付いている（位取り記数法）と捉えれば、どの基数でも同じ手順で変換できます。

桁数と対数 ― 「何ビット必要か」の型

n ビットで表せるパターンは 2ⁿ 通り、符号なし整数なら 0〜2ⁿ−1 です。逆に N 通りを区別するには log₂N を切り上げたビット数が要ります。10 進 1 桁は約 3.32 ビット（log₂10 ≒ 3.32）に相当し、10 進 k 桁の整数は 2 進で約 3.32k 桁になります。また d 桁の 2 進数を 2 乗すると桁数は 2d または 2d−1 になる（最上位が 1 なので 2^d−1 以上、2 乗で 2^2d−2 以上）という性質も、桁数問題の定番です。文字を使った符号にも同じ考え方が使えます。0〜7 の 8 種類の数字だけを使う 3 桁の番号を小さい順に並べると、番号「345」は 8 進数として 3×64＋4×8＋5＝229 なので、「000」を 1 番目と数えれば 230 番目です。

負数の表現と固定小数点数

負数は 補数で表します。1 の補数は全ビットを反転したもの、2 の補数は 1 の補数に 1 を加えたもので、現在のコンピュータはほぼ 2 の補数を使います。理由は、減算を加算回路だけで実現でき（A − B ＝ A ＋（B の 2 の補数）、桁あふれは捨てる）、0 の表現が 1 通りだからです。最上位ビットが符号（1 なら負）になります。

例として 8 ビットで −5 を表すと、5 ＝ 00000101 → 反転 11111010（1 の補数）→ ＋1 で 11111011（2 の補数）です。固定小数点数は小数点の位置を決め打ちした整数表現で、業務計算の金額（誤差が許されない）や組込み機器で使われます。範囲が狭い代わりに演算が速く誤差が出にくいのが特徴です。

浮動小数点数 ― IEEE 754 の構造

浮動小数点数は数を「符号 × 仮数 × 基数^指数」の形で表し、指数で小数点の位置を動かします。正規化は仮数の先頭を 0 以外にそろえる操作で、IEEE 754 では 1.xxx の形にして先頭の 1 を省略し（隠れビット）、有効桁を 1 ビット稼ぎます。指数は負の値も表せるようにバイアス（下駄）を足して格納します。

仮数のビット数が有限なので、浮動小数点演算には必ず誤差が伴います。試験で問われるのは誤差の名前と発生条件の対応です。特に「桁落ち」と「情報落ち」は 10 年で 3 問出ており、定義の入替えが定番の誤答肢です（図 2-2）。

シフト演算とビット演算 ― 乗除・剰余を置き換える

論理シフトは空いたビットに 0 を詰める操作で、符号なし整数向きです。算術シフトは符号ビットを動かさず、右シフトでは空きに符号ビットと同じ値を詰めるので、2 の補数の負数でも符号が保たれます。左に n ビットシフトすると 2ⁿ 倍、右に n ビットシフトすると 2ⁿ で割った商になります（正数では切捨て。負数の算術右シフトは負の無限大方向に丸められます）。x × 10 は x を 3 ビット左シフト（8 倍）と 1 ビット左シフト（2 倍）の和で計算でき、乗算器のない小さな CPU ではこの手法が使われます。

集合と論理演算 ― ド・モルガン・真理値表・カルノー図

集合と論理は同じ構造を別の記号で書いたものです。集合の和・積・補は論理の OR・AND・NOT に、ベン図の塗り分けは真理値表の行に対応します。論理演算は 10 年で 10 問（AI と並ぶ本章最多）で、問われ方は「等価な式を選ぶ」「真理値表から演算を特定する」「カルノー図で簡単化する」の 3 つです。

集合の演算とド・モルガンの法則

ド・モルガンの法則は「和の補集合は補集合の積、積の補集合は補集合の和」です。A ∪ B の補集合 ＝ Ā ∩ B̄、A ∩ B の補集合 ＝ Ā ∪ B̄ となり、論理式では ¬(A ∨ B) ＝ ¬A ∧ ¬B、¬(A ∧ B) ＝ ¬A ∨ ¬B です。試験ではこれと差集合の定義を組み合わせます。Ā ∩ B̄ は「A にも B にも属さない」なので、差集合で書けば Ā − B（A の外にあって B にも入らない）と同じ集合です。誤答肢には Ā ∪ B̄（A ∩ B の補集合）、A − B̄（＝ A ∩ B）のように 1 か所だけ記号を変えた式が並ぶので、要素の帰属を「A に入るか・B に入るか」の 4 領域で確かめるのが確実です。

命題論理と含意

命題は真（1）か偽（0）かが定まる文です。「A ならば B」（含意 A → B）は、A が真なのに B が偽のときだけ偽になり、前件 A が偽なら B に関係なく全体が真です。A → B は ¬A ∨ B と等価です。含意を扱う出題としては直近 10 年で令和 7 年春期・問 1 相当が唯一です（この等価則はトートロジー識別に使えます）。対偶 ¬B → ¬A は元の命題と真偽が一致しますが、逆 B → A や裏 ¬A → ¬B は一致しません。

論理演算と真理値表

ある演算の相補演算とは、出力をすべて否定した演算です。表を縦に見ると、AND の相補は NAND、OR の相補は NOR、そして XOR の相補は XNOR（等価演算）です。「XOR の相補演算はどれか」に NAND や NOR を選ばせる肢が 2 回出ています。名前で判断せず、4 行すべてが反転しているかを確認してください。NAND だけ（あるいは NOR だけ）を組み合わせれば NOT・AND・OR がすべて作れるため、NAND は万能ゲートと呼ばれます。

排他的論理和 XOR は「2 入力が異なるとき 1」で、次の性質が計算問題の根拠になります。A ⊕ A ＝ 0、A ⊕ 0 ＝ A、A ⊕ 1 ＝ ¬A、交換則・結合則が成り立ち、(A ⊕ B) ⊕ B ＝ A なので同じ値を 2 回 XOR すると元に戻ります。パリティビットの計算、ストリーム暗号、RAID 5 のパリティ復元がこの性質で動いています。

結合則は AND・OR・XOR には成り立ちますが、NAND や NOR、含意には成り立ちません。「結合法則が成り立つ演算はどれか」という出題（平成 29 年春期）がこの点を突いています。

カルノー図で論理式を最小化する

カルノー図は真理値表を 2 次元に並べ替えたもので、隣り合うマス目は 1 変数だけが異なるように（00, 01, 11, 10 の順、グレイコード順）配置します。1 のマス目を 2ⁿ 個の長方形で囲むと、囲みの中で値が変わる変数を消去できます。左端と右端、上端と下端は隣接扱い（折返し）です。4 変数のカルノー図から等価な簡略化式を選ぶ問題が 2 回（令和 4 年秋・令和 7 年秋相当、同一問題）出ています。

論理回路 ― 加算器・多数決回路・フリップフロップ

論理回路の問題は真理値表を自分で書けば必ず解けます。3 入力なら 8 行、入力の組合せを 000 から 111 まで並べて 1 行ずつ確認するのが最速です。

確率と統計

確率・統計は 10 年で 7 問、計算と「考え方を選ぶ」問題が半々です。順列・組合せで場合の数を数え、加法・乗法定理で確率を組み立て、期待値で平均的な結果を見積もる、という流れを型にしておきます。直近 3 年はベイズの定理を「事後確率を求める場面はどれか」と問うなど、公式を使う場面の判断へ寄っています。

「袋から取り出した玉の色から、どの袋を選んだかを推定する」「検査が陽性だったとき本当に病気である確率」のように、観測された結果から原因側の確率を更新する場面がベイズの定理の出番です。逆に「袋 A を選んだとき赤玉が出る確率」は単なる条件付き確率で、ベイズは不要です。

確率分布 ― 名前と場面を対応させる

連続型分布では特定の値をとる確率は 0 で、確率密度関数の面積が区間の確率になります。抜取検査で「不良率 10% のロットから 3 個抜き取り、全部良品なら合格」とすれば、合格確率は独立試行として 0.9³ ＝ 0.729 です。

統計の基本用語

推定と仮説検定

標本から母集団の値を 1 点で見積もるのが点推定、範囲で見積もるのが区間推定（95% 信頼区間など）です。観測データが得られる確からしさ（尤度）を最大にするパラメータを選ぶ方法が最尤推定です。

仮説検定では、否定したい主張を帰無仮説（例: 新旧システムの平均応答時間に差はない）、示したい主張を対立仮説に置き、帰無仮説が正しいとしたときに観測結果以上に極端なことが起きる確率（p 値）が有意水準（5% や 1%）より小さければ帰無仮説を棄却します。

有意水準 α は第 1 種の誤りを許容する確率そのものです。α を小さくすると β は大きくなる（トレードオフ）ので、両方を下げるには標本数を増やします。検定の種類は、平均の差なら t 検定（母分散未知）・z 検定（母分散既知または大標本）、分類データの分布や独立性ならカイ二乗検定、3 群以上の平均差なら分散分析と対応させておけば十分です。

数値計算・数値解析・グラフ理論

この節の小分類（数値計算・数値解析・グラフ理論・最適化）は 10 年で計 7 問と薄めですが、二分法の反復回数（令和 7 年春期）やニュートン法（令和 3 年秋期）のように、考え方を知っていれば 1 分で解ける問題が混ざります。用語の対応表を押さえ、二分法だけは計算の型にしておきます。

線形代数と数列

スカラは 1 つの数、ベクトルは数の並び、行列は数の 2 次元配置、テンソルはそれを多次元に一般化したもの（ディープラーニングの入出力データ）です。行列の積は「左の行 × 右の列」の内積で、一般に AB ≠ BA です。連立一次方程式 Ax ＝ b は、係数行列に行の基本変形を繰り返して単位行列にする掃出し法（ガウスの消去法）で解けます。

数値解析 ― 近似解の求め方と誤差

方程式を式変形で解けないとき、コンピュータは反復計算で近似解に近づけます。近似解と真の値の差が絶対誤差、それを真の値で割ったものが相対誤差です。反復を有限回で止めることによる誤差が打切り誤差、各ステップの丸めが積み重なるのが丸め誤差で、両者は反復回数を増やすと逆方向に動きます。

グラフ理論と最適化問題

グラフは頂点（ノード）と辺（エッジ）の集まりで、ネットワーク構成・工程・状態遷移など「つながり」を表す共通言語です。辺に向きがあれば有向グラフ、なければ無向グラフで、頂点 i と j が辺で結ばれていれば 1 を置く隣接行列で表現できます（無向なら対称行列）。木は閉路を持たない連結グラフで、n 頂点なら辺は必ず n−1 本です。「辺の数が頂点の数より 1 少なく、かつ連結」なら木、閉路が 1 つでもあれば木ではありません。

最適化問題は制約条件の下で目的関数を最大・最小にする問題です。変数が連続なら連続最適化（線形計画法: 目的関数と制約がすべて 1 次式で、最適解は実行可能領域の頂点にある）、選択肢が離散なら組合せ最適化（ナップサック問題、巡回セールスマン問題）に分かれます。部分問題の解を表に記録して再利用する動的計画法は組合せ最適化の基本技法で、PERT（Program Evaluation and Review Technique）のクリティカルパス計算（前進計算・後退計算）や最短経路のアルゴリズムも動的計画法の一種です。巡回セールスマン問題は都市数が増えると解の候補が爆発的に増え、多項式時間の解法が知られていません（後述の NP 困難）。

待ち行列理論 ― M/M/1 モデル

待ち行列理論は、窓口に客がランダムに到着してサービスを受けるシステムの待ち時間を確率的に見積もる理論です。ATM・コールセンター・Web サーバの応答時間・通信回線の伝送待ちに共通して使え、M/M/1 モデルは 10 年で 8 問と本章の最頻出テーマです。公式は 1 本、出題の数値パターンは 3 つしかありません。

モデルの記法と用語

M/M/1 はケンドール記法で「到着分布／サービス時間分布／窓口数」を表し、M はマルコフ性（厳密には無記憶性）を意味します。到着がポアソン分布（到着間隔は指数分布）、サービス時間も指数分布、窓口が 1 つ、待ち行列の長さに制限がなく先着順（FIFO：First In First Out）でサービスする、が前提です。「先着順」という前提を変える運用（優先順位付け）はモデルの前提に反する、という読解問題（平成 28 年春期）も出ています。

応答時間 Tq ＝ Ts/(1−ρ) と待ち時間 Tw ＝ ρ × Ts/(1−ρ) は ρ 倍の違いです。問題文が「待ち時間」なのか「応答時間（処理を含む）」なのかを最初に確認してください。待ち行列モデルで扱いにくい複雑なシステムは、乱数で到着とサービスを再現するシミュレーション（モンテカルロ法）で評価します。

情報理論と符号理論 ― 情報量・ハフマン符号・標本化

情報理論は「情報の量」を確率で測る理論です。めったに起きない事象ほど、それが起きたと知らされたときの驚きは大きい ― この直感を式にしたのが情報量で、生起確率 p の事象が起きたと知ったときの情報量は log₂(1/p) ビットです。p ＝ 1/2 なら 1 ビット、p ＝ 1/8 なら 3 ビットになります。情報源全体の平均情報量がエントロピー H ＝ Σ p_i log₂(1/p_i) で、これがその情報源を符号化するのに必要な平均ビット数の下限（＝一意復号可能な符号、代表的には接頭語符号を前提として、これ以上は圧縮できない限界）を与えます。

情報源符号化はデータを短くし、通信路符号化は逆に冗長なビットを足します。目的が正反対なので、「圧縮したのに誤り訂正もできる」といった肢は疑ってかかります。

ハフマン符号 ― 出現確率で符号長を変える

ハフマン符号は、出現確率の高い文字に短い符号、低い文字に長い符号を割り当てる可変長符号です。作り方は「確率が最小の 2 つを選んで 1 つにまとめる」を繰り返すだけで、できあがった木の枝に 0 と 1 を振れば符号表になります（図 2-6）。

連続する同じ値をまとめるランレングス符号（AAAAABBB を A5B3 とする）は、白と黒が続く FAX 画像のように同じ値が連続するデータで効きます。逆にランダムなデータでは符号が伸びることもあります。可逆圧縮（ZIP、PNG、ハフマン、ランレングス）と非可逆圧縮（JPEG、MP3）の区別も押さえます。

アナログとデジタル ― 標本化・量子化・符号化

音声や温度のような連続量（アナログ）をコンピュータで扱うには、標本化（時間を一定間隔で区切って値を読む）→量子化（読んだ値を決められた段階に丸める）→符号化（段階の番号を 2 進数で表す）の 3 段階で数値化します。

この一連の処理が A/D 変換であり、パルスの符号として送る方式が PCM（Pulse Code Modulation：パルス符号変調）です（図 2-7）。

文字コード

UTF-8 は先頭バイトのビットパターンで「この文字が何バイトか」が分かる自己同期的な設計になっており、ASCII 文字はそのまま 1 バイトで表せます。この互換性が Web での事実上の標準になった理由です。

形式言語・オートマトン・計算量

この節のテーマは、中分類「基礎理論」としては直近 10 年で BNF が 1 回（平成 29 年春期）出たのみの薄い領域です。ただし逆ポーランド記法・計算量はアルゴリズム分野（第 3 章）、構文解析はソフトウェア分野（第 6 章）で問われるので、用語と読み方だけは確実にしておきます。

述語論理と推論

命題論理が「真か偽かが決まった文」を扱うのに対し、述語論理は「x は社員である」のように変数を含む文（述語）と、「すべての」「ある」といった量化子を扱います。関係データベースの問合せは、述語を満たす行を集める操作として述語論理で説明できます。

推論には、一般的な規則から個別の結論を導く演繹推論（規則が正しければ結論も必ず正しい）と、個別の観察から一般規則を導く帰納推論（結論は確からしいだけで、反例で覆る）があります。機械学習はデータから規則を導くので帰納推論に当たります。

形式言語と BNF

形式言語は、記号の並び（文字列）のうちどれが「正しい文」かを文法で厳密に定義した言語です。プログラム言語の構文定義には BNF（Backus-Naur Form）がよく使われ、非終端記号を ::= の左辺に、選択肢を | で区切って書きます。再帰的な定義で「任意の長さ」を表せるのが要点です。

<数字>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<整数>   ::= <数字> | <整数><数字>
<符号付> ::= <整数> | + <整数> | - <整数>

この定義では、<整数> が自分自身を左に含むので 1 桁でも 100 桁でも表せます。BNF の問題は「この文法で生成できない文字列はどれか」という形が定番で、定義を 1 文字ずつ当てはめて確かめれば解けます。同じ内容を図で表したものが構文図式です。文法の種類では、規則の左辺が非終端記号 1 個だけの文脈自由文法がプログラム言語の構文に使われます。文字列のパターンを簡潔に表す正規表現は、文脈自由文法より表現力が低い代わりに有限オートマトンで判定できます。

逆ポーランド記法と構文木

演算子を被演算子の後ろに置く記法が逆ポーランド記法（後置記法）で、括弧なしで演算順序を一意に表せます。式 (A ＋ B) × (C − D) は AB+CD-* となり、左から読んでスタックに積む・演算子が来たら 2 つ取り出して計算する、という単純な手順で評価できます。構文木でいえば、通常の中置記法は木を左・根・右の順（中間順）に、逆ポーランドは左・右・根の順（後行順）にたどった結果です。

オートマトンと計算のモデル

有限オートマトンは、有限個の状態と、入力記号ごとの遷移だけを持つ最も単純な計算モデルです。入力を最後まで読んだときの状態が受理状態なら、その文字列を受理します。試験では状態遷移表を与えて「受理される文字列はどれか」を問う形で出るので、初期状態から 1 文字ずつ指でたどるのが確実です。同じ内容を、状態を丸・遷移を矢印で描いた図が状態遷移図です。

この表は「末尾が 01 である 2 進文字列」を受理します。1101 なら S0 →（1）S0 →（1）S0 →（0）S1 →（1）S2 で受理、010 なら S0 → S1 → S2 → S1 で終わるので受理されません。プッシュダウンオートマトンは有限オートマトンにスタックを足したもので、括弧の対応のような「数を覚える」処理ができ、文脈自由文法に対応します。さらに無限のテープを持つチューリング機械は、現在のコンピュータで計算できるものすべてを表現できる理論モデルです。

計算量と正当性

アルゴリズムの効率は、入力サイズ n に対する処理量の増え方（オーダー記号 O）で表します。実行時間の増え方が時間計算量、必要な記憶領域が領域計算量です。

多項式時間（n の何乗かで抑えられる）で解ける問題の集まりが P 問題、答えが与えられればそれが正しいかを多項式時間で検証できる問題の集まりが NP 問題です。NP の中で最も難しい一群が NP 完全問題で、そのどれか 1 つでも多項式時間で解ければ NP のすべてが解けます。P ＝ NP かどうかは未解決です。NP 完全問題と同等以上に難しい問題（NP に属するとは限らない）は NP 困難と呼ばれ、巡回セールスマン問題の最適化版がその例です。

プログラムが仕様どおりかを数学的に議論するのが正当性理論で、「停止すれば正しい結果を返す」ことが部分正当性、「必ず停止し、かつ正しい結果を返す」ことが全正当性です。任意のプログラムが停止するかどうかを判定する一般的なアルゴリズムは存在しない（停止問題は決定不能）ことが証明されており、テストが必要な理論的な根拠になっています。

コンパイラ理論とプログラム言語論

プログラム言語は、処理の手順を書く手続型言語、値の変換を関数の合成で書く関数型言語、事実と規則を宣言して処理系に推論させる論理型言語、データと操作をまとめるオブジェクト指向言語に大別されます。詳しくは第 6 章で扱います。

AI と機械学習 ― 学習の種類・過学習・評価指標

AI は「人間が知識を書き下してルールで解く」段階から、「データから規則を学習する」段階へ移りました。前者の代表がエキスパートシステムで、専門家の知識を if-then 形式で蓄えた知識ベースと、それを組み合わせて結論を出す推論エンジンからなります（知識工学の成果）。

後者が機械学習で、どのようなデータからどれだけ学べるかを扱う理論的な枠組みが学習理論、未知のデータに対しても正しく働く能力が汎化性能です。問題の種類では、与えられた事実から答えを絞り込む解析型問題（診断・分類）と、部品を組み合わせて解を作る合成型問題（設計・計画）に分けられます。

機械学習の 3 分類

「顧客をあらかじめ決めた区分に振り分ける」のは教師あり学習の分類、「顧客を似た者どうしにまとめ、区分そのものを見つける」のは教師なし学習のクラスタリングです。正解ラベルの有無で見分けます。主成分分析は、多数の変数を情報の損失が小さくなるように少数の合成変数へまとめる次元削減の手法で、令和 5 年秋期に出題されています。

データの分け方と過学習

手元のデータは訓練データ（パラメータを学習する）・検証データ（ハイパーパラメータの調整とモデル選択）・テストデータ（最終的な性能測定。一度だけ使う）に分けます。

人が指定する設定値（学習率、木の深さ、正則化の強さなど）がハイパーパラメータで、候補を総当たりするグリッドサーチや無作為に試すランダムサーチで調整します。

データを 1 回だけ分割して評価する方法がホールドアウト検証、データを k 個に分けて「1 個を検証・残りを訓練」を k 回繰り返し平均する方法が交差検証（k 分割交差検証）です。交差検証はデータが少ないときに評価のばらつきを抑えられます。

訓練データでの誤差が訓練誤差、未知のデータでの誤差が汎化誤差で、両者の差が大きいほど過学習が進んでいます。モデルが単純すぎて系統的にずれることをバイアス、複雑すぎて訓練データのゆらぎに振り回されることをバリアンスと呼び、片方を下げるともう片方が上がる関係（バイアスとバリアンスのトレードオフ）にあります。複数のモデルの予測を組み合わせて安定させるアンサンブル学習（ランダムフォレストはその一種）も汎化性能を上げる定番です。入力の小さな変化や想定外の入力で性能が落ちにくい性質は AI のロバスト性と呼ばれます。

混同行列と評価指標

分類モデルの性能は、予測と実際を突き合わせた 2 行 2 列の混同行列から導きます。どの指標も「分母が何か」を押さえれば区別でき、令和 7 年秋期の偽陽性率のように定義そのものが問われます（図 2-9）。

ディープラーニングと生成 AI

ニューラルネットワークは、入力を重み付きで足し合わせて活性化関数に通す素子（ニューロン）を層状につないだモデルです。層を深く重ねたものがディープラーニング（深層学習）で、出題では一貫して「多層の素子と信号線で構成し、パラメータを調整することで解を出力する」「脳の神経回路のように多層の処理を重ねて複雑な判断をする」という説明が正解になっています。誤答肢にはエキスパートシステム・遺伝的アルゴリズム・クラスタリングの説明が並びます。

通信理論 ― 伝送・変調・誤り検出/訂正・計測制御

通信理論のうち中分類「基礎理論」で実際に出るのは誤り検出・訂正（直近 10 年で 6 問）にほぼ集中しています。伝送路・変復調・多重化・同期方式はネットワーク分野（第 10 章）で問われるため、ここでは用語表で対応関係を押さえます。

アナログ伝送路にデジタルデータを乗せる装置がモデム（変調と復調を行う）です。暗号化（公開鍵・秘密鍵・PKI・SSL/TLS）も広い意味では符号理論に含まれますが、内容は第 12 章で扱います。

パリティチェックと 2 次元パリティ

最も単純な誤り検出がパリティチェックです。データ中の 1 の個数が偶数になるように 1 ビット付加するのが偶数パリティ、奇数にするのが奇数パリティで、1 ビットの誤りは検出できますが、2 ビット同時に反転すると見逃します（検出だけで訂正はできない）。合計値を送って照合するチェックサムも検出だけです。

データを 2 次元に並べ、行と列の両方にパリティを付けたものが 2 次元パリティ（水平垂直パリティ）です。1 ビット誤りがあると行と列の 1 つずつが不一致になり、その交点が誤りビットの位置なので、検出だけでなく訂正まで可能になります。

偶数パリティでは、データと付加したパリティを合わせた 1 の個数が偶数にならない行・列が不一致です。2 行目はデータの 1 が 1 個（奇数）なのに行パリティが 0、3 列目はデータの 1 が 2 個（偶数）なのに列パリティが 1 で、どちらも合計が奇数になり不一致です。不一致の行と列が 1 つずつなので、その交点である2 行 3 列のビットを反転すれば訂正完了です。「2 次元パリティは何ビットまで訂正できるか」に「2 ビット」や「検出のみ」を選ばせる誤答肢が定番なので、1 ビットの誤りを訂正できる（2 ビットの誤りは検出できても位置を特定できない）と覚えます。

ハミング符号 ― 検査式から誤り位置を求める

ハミング符号は、複数の検査ビットが受け持つ位置を重ねてずらすことで、どのビットが誤ったかを検査結果の組合せから特定できるようにした符号です。7 ビット符号語 x₁〜x₇ に対して 3 本の検査式を与える形が定番で、3 本の結果を並べた 2 進数がそのまま誤り位置を示します（図 2-10）。

CRC（巡回冗長検査）は、送信データを 1 つの多項式とみなし、あらかじめ決めた生成多項式で割った余りを検査符号として付加する方式です。受信側は同じ生成多項式で割り、余りが 0 なら誤りなしと判断します。連続した複数ビットの誤り（バースト誤り）に強く、通信やストレージで広く使われます。訂正はできず検出専用である点が、ハミング符号や 2 次元パリティとの違いです。主記憶で使われる ECC（Error Correcting Code：誤り訂正符号） はハミング符号系の訂正機能付き符号で、1 ビット訂正・2 ビット検出（SECDED）が代表的な実装です（ECC には方式差があり、すべてがこの仕様とは限りません）。

計測・制御の基礎

制御対象の状態をセンサーで読み取り（A/D 変換）、コンピュータが判断し、アクチュエーターを通じて機械的な動作に変える（D/A 変換）のが計測・制御の基本構造です。結果を測って入力に戻す制御がフィードバック制御（クローズドループ）、外乱をあらかじめ見込んで先回りする制御がフィードフォワード制御で、結果を測らずに指令だけ出すのがオープンループです。応答の速さ（応答特性）と振動しないこと（制御安定性）はトレードオフになります。

ToF センサーは、光を照射してから反射光が戻るまでの時間から距離を測る方式で、平成 31 年春期に出題されています。名前から動作原理を答えられるようにしておけば十分です。

ひっかけポイント

理解度チェック（科目 A 形式）

まとめ

本章の得点源は、公式が 1 本しかない計算問題と、定義の入替えで作られる用語問題です。次の表の左から順に、式を見た瞬間に数値を当てはめられる状態を目指してください。

直近 10 年（19 回）の科目 A では中分類「基礎理論」から 73 問、1 回平均 3.8 問が問 1〜6 に出題されており、直近 3 年の 21 問のうち 7 問は要旨・正解が過去問と一致する再出題でした。M/M/1・ハフマン符号・ハミング符号・カルノー図は同じ問題が数年おきに戻ってくるので、本章の「計算の型」を手で一度ずつ解いておけば、試験本番では読むだけで答えが出ます。

次章では、本章の計算量やグラフの考え方を土台に、探索・整列・木構造といった具体的なアルゴリズムと擬似言語の読み方を扱います。科目 B の必須問題（アルゴリズムとプログラミング）に直結する章です。