基礎理論

コンピュータは内部で 2進数（基数2） を使い、すべてのデータを処理しています。電子回路は電圧の ON（1） と OFF（0） の2状態で安定動作するため、2進数が最も適しています。

人間が日常的に使う10進数との変換方法を正確に理解することは、基本情報技術者試験の最重要基礎です。ここでは 基数変換 の手法に加え、固定小数点数 ・ 浮動小数点数 といったコンピュータ内部での数値表現、さらに各種 誤差 や 数値計算手法 、 文字コード まで幅広く学びます。

基数と基数変換

基数（radix） とは、数値を表現するときに使う数字の種類の数です。2進数は基数2、10進数は基数10です。

10進数 → 2進数

整数部は 2で割って余りを下から読む 方法、小数部は 2を掛けて整数部を上から読む 方法を使います。

例: 26.375（10進数）→ 2進数

整数部 26:

• 26 ÷ 2 = 13 … 余り 0
• 13 ÷ 2 = 6 … 余り 1
• 6 ÷ 2 = 3 … 余り 0
• 3 ÷ 2 = 1 … 余り 1
• 1 ÷ 2 = 0 … 余り 1
• 下から読む → 11010

小数部 0.375:

• 0.375 × 2 = 0.75 → 整数部 0
• 0.75 × 2 = 1.5 → 整数部 1
• 0.5 × 2 = 1.0 → 整数部 1
• 上から読む → .011

結果: 26.375₁₀ = 11010.011₂

2進数 → 10進数

各桁に2の累乗を掛けて合計します。

11010.011₂ = 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰ + 0×2⁻¹ + 1×2⁻² + 1×2⁻³ = 16 + 8 + 0 + 2 + 0 + 0 + 0.25 + 0.125 = 26.375

8進数・16進数との相互変換

2進数は桁数が多くなるため、人間が読みやすい 8進数 や 16進数 が実務で使われます。

基数	使用する数字	2進数との対応	主な用途
2進数	0, 1	―	コンピュータ内部
8進数	0〜7	3桁ずつまとめる	Unixファイルパーミッション
10進数	0〜9	―	日常の計算
16進数	0〜9, A〜F	4桁ずつまとめる	メモリアドレス、色コード

16進数では 10=A, 11=B, 12=C, 13=D, 14=E, 15=F と表記します。

例: 2進数 → 16進数

10110110₂ を4桁ずつ区切ると 1011 | 0110 → B6₁₆

例: 16進数 → 2進数

3F₁₆ → 0011 1111₂（3→0011, F→1111）

固定小数点数と浮動小数点数

固定小数点数

小数点の位置を固定して数値を表現する方式です。整数の表現にも使われ、2の補数 によって負の数を扱います。

2の補数の求め方:

1. 元の数値のビットをすべて反転（0→1, 1→0）
2. 反転結果に1を加える

例: 8ビットで -43 を表現

1. +43 = 00101011
2. ビット反転 → 11010100
3. +1 → 11010101（= -43）

検算: 00101011 + 11010101 = 100000000（9ビット目のオーバーフローを無視すると0になる）

2の補数を使う利点は、加算回路だけで減算も実現できる ことです。A - B = A + (-B) として計算できます。

浮動小数点数（IEEE 754）

非常に大きな数や非常に小さな数を表現するために、小数点の位置を動かす方式です。IEEE 754 規格で標準化されています。

浮動小数点数は 符号部 ・ 指数部 ・ 仮数部 の3つの領域に分かれます。

形式	全体のビット数	符号部	指数部	仮数部
単精度	32ビット	1ビット	8ビット	23ビット
倍精度	64ビット	1ビット	11ビット	52ビット

正規化 とは、仮数部の最上位ビットが必ず1になるように指数を調整することです。IEEE 754 では正規化された仮数の先頭の1を省略して格納します（ ケチ表現 ）。これにより、実質的に1ビット分多くの精度を確保できます。

例: -6.5 を単精度で表現

1. 6.5₁₀ = 110.1₂
2. 正規化: 1.101 × 2²
3. 符号部 = 1（負）
4. 指数部 = 2 + 127（バイアス値）= 129 = 10000001
5. 仮数部 = 10100000000000000000000（先頭の1を省略した残り）

結果: 1 10000001 10100000000000000000000

算術演算における誤差

コンピュータの数値演算では、有限のビット数で計算するため様々な 誤差 が発生します。FE試験では以下の誤差の区別が頻出です。

誤差の種類	説明	具体例
丸め誤差	有限ビットで表現しきれない値を四捨五入等で近似	10進数の0.1は2進数で無限小数→打切りで誤差
桁落ち	絶対値がほぼ等しい2数の減算で有効桁数が激減	1.000001 - 1.000000 = 0.000001（有効桁1桁）
情報落ち	絶対値が大きく異なる2数の加減算で小さい方の情報が失われる	1.0×10²⁰ + 1.0 → 1.0のほうが消える
打切り誤差	無限級数の計算を途中で打ち切ることで生じる	sin(x) のテイラー展開を有限項で近似
オーバーフロー	計算結果が表現可能な最大値を超える	8ビット符号なし整数で 255 + 1 → 0
アンダーフロー	計算結果が表現可能な最小値（0に最も近い値）を下回る	浮動小数点で極小値同士の乗算→0に

試験では「この計算で発生する誤差は何か？」という形式で出題されます。桁落ち と 情報落ち の違いを明確に押さえましょう。桁落ちは「近い値の引き算」、情報落ちは「大小差がある値の足し引き」です。

数値計算・数値解析の手法

FE試験では以下の数値計算手法が出題されます。

手法	目的	概要
ニュートン法（ニュートン・ラフソン法）	方程式の近似解	接線の x 切片を次の近似値とし反復。収束が速い（2次収束）が初期値依存
二分法	方程式の近似解	区間を半分に分けて解を絞り込む。確実だが収束は遅い
台形公式	定積分の近似	区間を分割し各区間を台形で近似して面積を求める
ガウスの消去法（掃き出し法）	連立方程式の解	行列の行操作で上三角行列にし、後退代入で解を求める

ニュートン法の手順:

f(x) = 0 の解を求めるとき、初期値 x₀ から次の漸化式で近似値を更新します。

xₙ₊₁ = xₙ - f(xₙ) / f'(xₙ)

例: f(x) = x² - 2 の解（√2 の近似値）を x₀ = 1 から求める

• f'(x) = 2x
• x₁ = 1 - (1-2)/(2×1) = 1 - (-1/2) = 1.5
• x₂ = 1.5 - (2.25-2)/(2×1.5) = 1.5 - 0.25/3 ≈ 1.4167
• x₃ ≈ 1.4142（√2 ≈ 1.41421356... にすぐ収束）

文字の表現

コンピュータは文字も数値（ 文字コード ）として扱います。

文字コード	ビット数	特徴
ASCII	7ビット（128文字）	英数字・記号・制御文字。すべての文字コードの基本
Shift_JIS	1〜2バイト	日本語対応。JIS X 0208 の文字をシフトして配置。レガシーシステムで使用
EUC-JP	1〜3バイト	Unix系で使われた日本語文字コード
Unicode	規格全体	世界中の文字を統一的に扱う。符号化方式は複数ある
UTF-8	1〜4バイト	Unicode のエンコーディング。ASCII互換で Web の標準。1バイト〜4バイトの可変長
UTF-16	2または4バイト	Unicode のエンコーディング。Java や Windows 内部で使用

ASCII では A = 65（0x41）、a = 97（0x61）、0 = 48（0x30）です。大文字と小文字の差は32（0x20）であることを覚えておくと便利です。

論理演算 は、真（1, True）と偽（0, False）の2つの値を対象とした演算です。コンピュータの CPU はこの論理演算の組み合わせで、すべての計算を実現しています。

論理演算はプログラムの条件分岐、ビット操作、データベースの検索条件、ネットワークのサブネットマスク計算など、IT のあらゆる場面で使われます。基本情報技術者試験では、真理値表の読解、論理式の変換、論理回路の設計が頻出テーマです。

基本論理演算と真理値表

論理演算のすべての入力パターンと出力結果を一覧にしたものが 真理値表 です。

A	B	AND（論理積）	OR（論理和）	XOR（排他的論理和）	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

NOT A
A=0 → 1
A=1 → 0

各演算の意味:

• AND（論理積 A·B） — 両方とも1のときだけ1。「AかつB」
• OR（論理和 A+B） — どちらか一方でも1なら1。「AまたはB」
• NOT（否定 Ā） — 0と1を反転。「Aでない」
• XOR（排他的論理和 A⊕B） — 2つの入力が異なるとき1。パリティチェックや暗号に活用
• NAND（否定論理積） — ANDの否定。NANDゲートだけですべての論理回路を構成可能
• NOR（否定論理和） — ORの否定。NORゲートだけでもすべての論理回路を構成可能

NAND と NOR はそれぞれ単独で 万能ゲート（Universal Gate） と呼ばれ、IC 設計の基本部品として重要です。

ブール代数とド・モルガンの法則

ブール代数 は、論理演算を代数的に扱う体系です。以下の基本法則を用いて論理式を簡略化できます。

法則	式
交換法則	A·B = B·A、A+B = B+A
結合法則	(A·B)·C = A·(B·C)、(A+B)+C = A+(B+C)
分配法則	A·(B+C) = A·B+A·C、A+(B·C) = (A+B)·(A+C)
吸収法則	A+A·B = A、A·(A+B) = A
相補法則	A·Ā = 0、A+Ā = 1
べき等法則	A·A = A、A+A = A

ド・モルガンの法則

論理式を変換するための最重要法則です。

第1法則: NOT(A AND B) = NOT A OR NOT B

第2法則: NOT(A OR B) = NOT A AND NOT B

つまり「AND と OR を入れ替えて、各項を否定」すれば全体の否定になります。

例: 「20歳以上 かつ 学生」の否定 → 「20歳未満 または 学生でない」

プログラムの条件式を否定するとき、ド・モルガンの法則を使うと正確に変換できます:

// 元の条件
if (age >= 20 && isStudent) { ... }
// 否定（ド・モルガン適用）
if (age < 20 || !isStudent) { ... }

カルノー図

カルノー図 は、真理値表を2次元の格子に配置して論理式を視覚的に簡略化する手法です。隣接する1のセルをグループ化することで、冗長な項を除去できます。

例: 2変数のカルノー図（f = A·B + Ā·B を簡略化）

	B=0	B=1
A=0	0	1
A=1	0	1

B=1 の列がすべて1なので、f = B に簡略化できます。

3変数以上のカルノー図では、隣接セルが グレイコード 順（1ビットだけ異なる配置）になっている点に注意します。

論理回路

論理演算を電気回路で実現したものが 論理回路 です。MIL記号（米軍規格記号）で表されます。

半加算器（Half Adder）

1桁の2進数の加算を行う回路です。XOR回路 で和（S）を、AND回路 で桁上げ（C）を出力します。

入力A	入力B	和 S（XOR）	桁上げ C（AND）
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

全加算器（Full Adder）

下位桁からの 桁上げ入力（Cin） も含めた加算を行います。半加算器を2つと OR回路1つで構成されます。

CPU 内部では全加算器を n個並べたリプルキャリーアダー で n ビットの加算を行います。

フリップフロップ

フリップフロップ（FF） は、1ビットの情報を記憶できる 順序回路 です。論理回路が「組み合わせ回路（入力だけで出力が決まる）」と「順序回路（過去の状態も影響する）」に分かれる点が重要です。

種類	特徴
RS-FF	Set/Resetで状態を切り替える。S=R=1は禁止入力
D-FF	クロック信号の立ち上がりでD入力の値を記憶
JK-FF	RS-FFの禁止入力を解消。J=K=1で反転動作
T-FF	入力があるたびに状態が反転。カウンタに使用

レジスタは複数のフリップフロップを並べたもので、CPU のデータ保持に使われます。

集合と命題

集合 とは、ある条件を満たす要素の集まりです。集合演算は論理演算と密接に対応しています。

集合演算	記号	対応する論理演算	意味
和集合	A ∪ B	OR	AまたはBに属する要素の集合
積集合	A ∩ B	AND	AかつBに属する要素の集合
差集合	A − B	A AND NOT B	Aに属しBに属さない要素の集合
補集合	Ā（A̅）	NOT	全体集合のうちAに属さない要素の集合

ベン図 で視覚的に理解できます。2つの円が重なる部分が積集合、両方の円を合わせた部分が和集合です。

集合にもド・モルガンの法則が成り立ちます:

• (A ∪ B) の補集合 = Ā ∩ B̄
• (A ∩ B) の補集合 = Ā ∪ B̄

命題論理

命題 とは、真か偽かが確定する文のことです。「5は素数である」は命題（真）、「x は3より大きい」は x が決まらないと真偽不明なので命題ではありません。

用語	記号	説明	例（元の命題「雨ならば地面が濡れる」）
含意（ならば）	P → Q	PならばQ	雨 → 地面が濡れる
逆	Q → P	QならばP	地面が濡れる → 雨
裏	¬P → ¬Q	PでないならばQでない	雨でない → 地面が濡れない
対偶	¬Q → ¬P	QでないならばPでない	地面が濡れない → 雨でない

重要な性質:

• 元の命題が真なら 対偶も必ず真 （逆は成り立たないことがある）
• 逆と裏は互いに対偶の関係 （一方が真なら他方も真）
• 逆が真とは限らない（地面が濡れていても、スプリンクラーかもしれない）

試験では「対偶を取って証明せよ」「逆は必ずしも真ではない」といった出題が定番です。

図中で同じ色の命題は 真偽が一致 します。元の命題と対偶（青）は常に同じ真偽値を持ち、逆と裏（橙）も常に同じ真偽値を持ちます。ただし、青グループと橙グループの真偽値は一致するとは限りません。

確率 とは、ある事象が起こる可能性を 0 から 1 の数値で表したものです。確率 0 は「絶対に起こらない」、確率 1 は「必ず起こる」を意味します。基本情報技術者試験では、確率の計算問題が頻出するため、順列・組合せの基本から確実に理解しましょう。

順列と組合せ

順列（Permutation） は、n 個の中から r 個を取り出して並べる場合の数です。

_nP_r = n! / (n−r)!

組合せ（Combination） は、n 個の中から r 個を取り出す（順序を区別しない）場合の数です。

_nC_r = n! / (r! × (n−r)!)

例: 5人の中から3人を選んで一列に並べる → ₅P₃ = 5 × 4 × 3 = 60 通り

例: 5人の中から3人を選ぶ（順序不問） → ₅C₃ = 5! / (3! × 2!) = 10 通り

確率の基本法則

加法定理（和の法則）は、互いに排反な事象 A と事象 B のどちらかが起こる確率を求めます。

P(A ∪ B) = P(A) + P(B)

事象が排反でない場合は、重複分を引きます。

P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

乗法定理（積の法則）は、事象 A と事象 B がともに起こる確率を求めます。A と B が独立であれば次のようになります。

P(A ∩ B) = P(A) × P(B)

例: サイコロを2回振って、1回目が偶数かつ2回目が3以上になる確率

• 1回目が偶数: P(A) = 3/6 = 1/2
• 2回目が3以上: P(B) = 4/6 = 2/3
• 両方とも起こる: P(A ∩ B) = 1/2 × 2/3 = 1/3

条件付き確率とベイズの定理

条件付き確率 は、事象 B が起きたという条件のもとで事象 A が起こる確率です。

P(A|B) = P(A ∩ B) / P(B)

ベイズの定理 は、結果から原因の確率を逆算する公式です。

P(A|B) = P(B|A) × P(A) / P(B)

例: ある工場の製品の 1% が不良品（事象 A）。検査装置は不良品を 95% の確率で不良と判定し（P(B|A) = 0.95）、良品を 3% の確率で誤って不良と判定する（P(B|A̅) = 0.03）。検査で不良と判定された製品が本当に不良品である確率は？

• P(B) = P(B|A) × P(A) + P(B|A̅) × P(A̅)
• P(B) = 0.95 × 0.01 + 0.03 × 0.99 = 0.0095 + 0.0297 = 0.0392
• P(A|B) = (0.95 × 0.01) / 0.0392 ≈ 0.242

検査で不良と判定されても、本当に不良品である確率は約 24.2% にとどまります。このように事前確率が低い場合、偽陽性が多くなるという直感に反する結果が生じます。

期待値と分散

期待値（Expected Value） は、確率変数の「平均的な値」を表します。各値にその確率を掛けて合計します。

E(X) = Σ(xᵢ × P(xᵢ))

例: サイコロの出目の期待値 = 1×(1/6) + 2×(1/6) + … + 6×(1/6) = 21/6 = 3.5

分散（Variance） は、データが期待値からどれだけ散らばっているかを示す指標です。

V(X) = E(X²) − {E(X)}²

標準偏差（Standard Deviation） は分散の平方根で、元のデータと同じ単位で散らばりを表現できます。

σ = √V(X)

例: あるシステムの応答時間が {2, 4, 4, 4, 6} 秒のとき

• 期待値: E(X) = (2+4+4+4+6) / 5 = 4.0
• E(X²) = (4+16+16+16+36) / 5 = 88/5 = 17.6
• 分散: V(X) = 17.6 − 4.0² = 17.6 − 16.0 = 1.6
• 標準偏差: σ = √1.6 ≈ 1.265

確率分布

確率変数がとりうる値とその確率の対応関係を 確率分布 といいます。試験で問われる代表的な分布を押さえましょう。

分布	特徴	具体例
二項分布	成功確率 p の試行を n 回繰り返したとき、成功回数の分布	コイン投げで表が出る回数
ポアソン分布	一定期間に平均 λ 回起こる稀な事象の発生回数の分布	1時間あたりのサーバ障害回数
正規分布	平均値を中心に左右対称の釣鐘型。自然界や社会の多くの現象が従う	テストの得点分布

二項分布 の確率は次の式で計算します。

P(X = k) = ₙCₖ × pᵏ × (1−p)ⁿ⁻ᵏ

例: 不良率 5% の製品から 3 個取り出して、ちょうど 1 個が不良品である確率

P(X=1) = ₃C₁ × 0.05¹ × 0.95² = 3 × 0.05 × 0.9025 = 0.1354

正規分布 では、平均 ± 1σ の範囲に約 68.3%、± 2σ に約 95.4%、± 3σ に約 99.7% のデータが含まれます。これを 3シグマルール と呼びます。

統計の基本指標と回帰分析

データの特徴を把握するための 代表値 と 散布度 を整理します。

指標	説明	計算例（データ: 3, 5, 5, 7, 10）
平均値	すべての値の合計 ÷ データ数	(3+5+5+7+10) ÷ 5 = 6.0
中央値（メジアン）	データを昇順に並べた中央の値	5（3番目の値）
最頻値（モード）	最も多く出現する値	5（2回出現）

相関係数 は、2つの変数間の直線的な関係の強さを -1 から 1 で表します。

• 1 に近い → 強い正の相関（一方が増えると他方も増える）
• -1 に近い → 強い負の相関（一方が増えると他方は減る）
• 0 に近い → 相関がない（直線的な関係がない）

回帰分析 は、2つの変数の関係を数式（回帰直線）で表す手法です。例えば「広告費 x と売上 y の関係」を y = ax + b の形で表現し、将来の売上を予測します。最もよくあてはまる直線を求める方法を 最小二乗法 といい、実測値と予測値の差（残差）の二乗和を最小にする a, b を求めます。

グラフ理論 は、ネットワークや関係構造を数学的に扱う分野です。IT分野ではネットワーク設計、データベースの関連図、プロジェクト管理などで活用されます。

グラフの基本用語

グラフは 頂点（ノード） と 辺（エッジ） で構成されます。

用語	説明
頂点（ノード）	グラフの点。ネットワークの拠点など
辺（エッジ）	頂点同士を結ぶ線。通信回線など
次数	ある頂点に接続する辺の数
有向グラフ	辺に方向がある（一方通行）
無向グラフ	辺に方向がない（双方向）
重み付きグラフ	辺にコスト（距離・時間など）が設定されたグラフ
隣接	辺で直接つながっている2頂点の関係

グラフ理論の重要な性質として、無向グラフでは すべての頂点の次数の合計 = 辺の数 × 2 が成り立ちます。これは1つの辺が2つの頂点の次数に寄与するためです。

オイラー路とハミルトン路

オイラー路 は、グラフのすべての辺をちょうど1回ずつ通る経路です。有名な「ケーニヒスベルクの橋」の問題がその起源です。

• オイラー路が存在する条件: 奇数次数の頂点が 0個または2個
• オイラー回路（始点に戻る）: 奇数次数の頂点が 0個

ハミルトン路 は、グラフのすべての頂点をちょうど1回ずつ通る経路です。

• オイラー路は「すべての辺を1回」、ハミルトン路は「すべての頂点を1回」
• ハミルトン路の存在を効率的に判定する一般的な方法は知られていない（NP完全問題）

上のグラフでは、A-B-C-A-D-C がオイラー路の一例です（すべての辺を1回ずつ通る）。A の次数は 3、B の次数は 2、C の次数は 3、D の次数は 2 で、奇数次数の頂点が A と C の 2 個なのでオイラー路が存在します。

最短経路問題

重み付きグラフにおいて、ある頂点から別の頂点への最短経路（コスト最小の経路）を求める問題です。代表的なアルゴリズムに ダイクストラ法 があります。

ダイクストラ法の手順:

1. 始点の距離を 0、他のすべての頂点の距離を ∞ に設定する
2. 未確定の頂点の中から距離が最小の頂点を選び、確定する
3. 確定した頂点に隣接する未確定の頂点について、経由した場合の距離が現在の距離より短ければ更新する
4. すべての頂点が確定するまで 2〜3 を繰り返す

例: 以下のグラフで頂点 S から頂点 G への最短経路を求めます。

手順	確定頂点	S	A	B	G
初期	―	0	∞	∞	∞
1回目	S	0	4	2	∞
2回目	B	0	3	2	7
3回目	A	0	3	2	5
4回目	G	0	3	2	5

2回目で B を確定した後、B 経由で A への距離を計算すると 2+1=3 で、直接の 4 より短いので更新します。同様に A 経由で G への距離は 3+2=5 で、B 経由の 7 より短いので更新します。

最短経路は S → B → A → G（コスト 5） です。ダイクストラ法は 辺の重みがすべて非負 の場合に使用できます。

最適化問題

最適化問題 は、制約条件のもとで目的関数の値を最大化（または最小化）する問題です。

線形計画法（LP: Linear Programming） は、制約条件と目的関数がすべて1次式（線形）である最適化問題を解く手法です。

例: ある工場が製品 X と製品 Y を生産する。

• 目的: 利益を最大化（利益 = 3X + 5Y）
• 制約: 材料制約 X + 2Y ≤ 14、時間制約 3X + 2Y ≤ 18、X ≥ 0, Y ≥ 0

グラフ上で制約条件を満たす領域（実行可能領域）を描き、目的関数が最大となる頂点を求めます。線形計画法では、最適解は必ず実行可能領域の 頂点 に存在します。

上の例では、連立方程式 X + 2Y = 14 と 3X + 2Y = 18 を解くと X = 2, Y = 6 が交点です。このとき利益 = 3 × 2 + 5 × 6 = 36 が最大値です。

ナップサック問題 は、容量制限のあるナップサックに価値と重さが異なる品物を詰め込み、価値の合計を最大化する問題です。ITでは、限られたリソースに対する最適なタスク割り当てなどに応用されます。

巡回セールスマン問題（TSP） は、すべての都市を1回ずつ訪問して出発地に戻る最短経路を求める問題です。都市数が増えると計算量が爆発的に増加する NP困難 問題として知られています。

待ち行列理論

待ち行列理論 は、窓口に到着する客の待ち時間やシステムの混雑度を数学的に分析する理論です。ITではサーバへのリクエスト処理、コールセンター、プリンタの印刷待ちなどのモデル化に使われます。

最も基本的なモデルが M/M/1 モデル です。

記号	意味
1つ目の M	到着がポアソン分布に従う（ランダムに到着）
2つ目の M	サービス時間が指数分布に従う
1	窓口（サーバ）が1つ

M/M/1 モデルの公式

到着率 λ（ラムダ）: 単位時間あたりの平均到着数 サービス率 μ（ミュー）: 単位時間あたりの平均処理数

利用率 ρ（ロー）: 窓口が使用中である割合

ρ = λ / μ

安定条件: ρ < 1（到着率がサービス率を超えると行列が無限に伸びる）

指標	公式	意味
平均滞在時間 W	W = 1/(μ−λ)	到着から退去までの平均時間
平均待ち時間 Wq	Wq = ρ/(μ−λ)	待ち行列での平均待ち時間
平均系内人数 L	L = ρ/(1−ρ)	系内（待ち＋サービス中）の平均人数
平均待ち人数 Lq	Lq = ρ²/(1−ρ)	待ち行列の平均人数
窓口の空き率	1 − ρ	窓口が空いている割合

リトルの公式 は、待ち行列理論における最も基本的な関係式です。

L = λ × W

この式は「系内の平均人数 = 到着率 × 平均滞在時間」を意味し、分布の形に依存せず成り立つ普遍的な法則です。

計算例

あるWebサーバに毎秒平均 3 件のリクエストが到着し（λ = 3）、サーバは毎秒平均 5 件を処理できる（μ = 5）とします。

• 利用率: ρ = 3/5 = 0.6（60%）
• 平均滞在時間: W = 1/(5−3) = 0.5 秒
• 平均待ち時間: Wq = 0.6/(5−3) = 0.3 秒
• 平均系内リクエスト数: L = 0.6/(1−0.6) = 1.5 件
• リトルの公式で検算: L = λ × W = 3 × 0.5 = 1.5 件 ✓
• 窓口の空き率: 1 − 0.6 = 0.4（40%）

情報量とエントロピー

情報量 とは「ある事象がどれだけ意外か（驚きの度合い）」を数値化したものです。確率が低い事象ほど情報量は大きくなります。

クロード・シャノンが定義した 自己情報量 の公式は次のとおりです。

I(x) = −log₂ P(x)　[ビット]

• P(x): 事象 x が起こる確率
• 確率 1/2 の事象 → −log₂(1/2) = 1 ビット
• 確率 1/8 の事象 → −log₂(1/8) = 3 ビット

エントロピー（平均情報量） は、情報源から得られる情報量の期待値です。

H = −Σ P(xᵢ) × log₂ P(xᵢ)　[ビット]

具体例: コインの表裏（各確率 1/2）のエントロピーを計算すると、

H = −(1/2 × log₂(1/2) + 1/2 × log₂(1/2)) = −(1/2 × (−1) + 1/2 × (−1)) = 1 ビット

エントロピーは、すべての事象が等確率のとき 最大 になります。偏りがあるほどエントロピーは小さくなり、確実に結果が分かる（確率1）場合はエントロピーは 0 です。

符号化

データを効率よく表現・伝送するための技術が 符号化 です。代表的な手法を見ていきます。

ハフマン符号

ハフマン符号 は、出現頻度の高い文字に短いビット列、頻度の低い文字に長いビット列を割り当てる 可変長符号 です。データ圧縮の基礎として広く使われています。

手順:

1. 各文字の出現頻度を求める
2. 頻度の低い2つを選んで合成し、二分木を構築
3. 枝に 0/1 を割り当て、根から葉までのパスが符号になる

この例では A=0, B=10, C=110, D=111 となり、頻度の高い A が最も短い符号を持ちます。

ランレングス符号化

ランレングス符号化（連長圧縮） は、同じ値が連続する区間を「値 × 繰り返し回数」で表現する方式です。

• 例: AAABBBCCCCC → A3B3C5
• FAX のような白黒2値画像の圧縮に効果的

誤り検出・訂正

データ通信ではノイズによりビットが反転（0→1 や 1→0）することがあります。これを検出・訂正する仕組みが重要です。

方式	機能	仕組み
パリティビット	1ビット誤り検出	データに1ビット付加し、1の個数を偶数（偶数パリティ）または奇数（奇数パリティ）に揃える
CRC（巡回冗長検査）	複数ビット誤り検出	データを生成多項式で割った余りを検査ビットとして付加
ハミング符号	1ビット誤り訂正 + 2ビット誤り検出	複数のパリティビットを特定位置に配置し、誤りの位置を特定
チェックサム	誤り検出	データを一定の単位で合計し、その値を検査用に付加

パリティビットの例（偶数パリティ）:

データ	1の個数	パリティビット	送信データ
1011001	4（偶数）	0	10110010
1010101	4（偶数）	0	10101010
1101001	4（偶数）	0	11010010
1110001	4（偶数）	0	11100010

受信側で1の個数を数え、偶数でなければ誤りが発生したと判定します。ただし、2ビット同時に反転した場合は検出できません。

CRC はイーサネットやUSBなどの通信プロトコルで広く利用されています。パリティビットより高い検出能力を持ちますが、誤りの訂正はできません。

ハミング符号 は、2のべき乗の位置（1, 2, 4, 8, ...）にパリティビットを配置し、複数のパリティの組み合わせから誤りの位置を二進数で特定します。

通信理論

デジタル通信の性能を評価する基本指標と理論を学びます。

伝送速度と帯域幅

用語	定義
ビットレート（bps）	1秒間に伝送できるビット数
ボーレート（baud）	1秒間の信号変化回数
帯域幅（Hz）	使用する周波数の範囲
スループット	実効的なデータ転送速度

ビットレートとボーレートの関係は次の式で表されます。

ビットレート = ボーレート × log₂ M

M は1回の信号変化で表現できる状態数です。例えば4値変調（M=4）なら、1ボーあたり log₂ 4 = 2 ビットを伝送できます。

シャノンの通信路容量定理

通信路で伝送できる最大のビットレート（通信路容量 C ）は次の式で求まります。

C = B × log₂(1 + S/N)　[bps]

• B: 帯域幅 [Hz]
• S/N: 信号電力対雑音電力比（SN比）

この定理は「どんなに高度な符号化を使っても、この上限を超える通信速度は実現できない」という理論的限界を示しています。

変調方式

方式	変化させるもの	特徴
ASK（振幅変調）	搬送波の振幅	仕組みが単純だがノイズに弱い
FSK（周波数変調）	搬送波の周波数	ノイズに比較的強い
PSK（位相変調）	搬送波の位相	効率が良く広く使用
QAM（直交振幅変調）	振幅と位相の両方	多値化に適し高速通信で利用

計測・制御（A/D変換とD/A変換）

コンピュータはデジタル信号（離散値）を扱いますが、現実世界の多くの情報はアナログ信号（連続値）です。この変換を担うのが A/D変換（アナログ→デジタル）と D/A変換（デジタル→アナログ）です。

A/D変換の3ステップ

ステップ	処理	説明
1. 標本化（サンプリング）	一定間隔でアナログ信号の値を取得	サンプリング周波数で品質が決まる
2. 量子化	サンプリング値を離散的な値に丸める	量子化ビット数で精度が決まる
3. 符号化	量子化した値を2進数で表現	デジタルデータとして記録

サンプリング定理（ナイキストの定理）

アナログ信号を正確に復元するためには、元の信号に含まれる 最大周波数の2倍以上 のサンプリング周波数が必要です。

fₛ ≥ 2 × f_max

具体例: 音声CDは人間の可聴域の上限 20kHz を考慮し、サンプリング周波数を 44.1kHz（20kHz の2倍以上）に設定しています。量子化ビット数は16ビット（65,536段階）、ステレオ2チャンネルです。

CDのビットレート = 44,100 × 16 × 2 = 1,411,200 bps ≈ 1.41 Mbps

この定理を満たさない場合、エイリアシング（折り返し雑音） と呼ばれるひずみが発生し、元の信号を正しく復元できなくなります。

形式言語とチョムスキー階層

形式言語 とは、有限個のアルファベット（記号の集合）と生成規則によって厳密に定義された言語です。プログラミング言語も形式言語の一種です。

言語学者ノーム・チョムスキーは、形式言語を生成規則の制約の強さにより4段階に分類しました。これを チョムスキー階層 と呼びます。

タイプ	名称	認識する機械	例
タイプ0	帰納的可算言語	チューリングマシン	一般の計算問題
タイプ1	文脈依存言語	線形有界オートマトン	自然言語の一部
タイプ2	文脈自由言語	プッシュダウンオートマトン	プログラミング言語の構文
タイプ3	正規言語	有限オートマトン	正規表現で表せるパターン

下のタイプほど制約が強く（表現力が低い）、上のタイプの部分集合になります。つまり、正規言語 ⊂ 文脈自由言語 ⊂ 文脈依存言語 ⊂ 帰納的可算言語 という包含関係があります。

なぜ重要か: コンパイラの設計では、トークンの識別に正規言語（タイプ3）、構文の解析に文脈自由言語（タイプ2）を使い分けます。問題の性質に合った言語クラスを選ぶことで、効率的な処理が可能になります。

オートマトン

オートマトン は、入力に応じて状態が遷移する抽象的な計算モデルです。形式言語の認識能力に直接対応しています。

有限オートマトン（FA）

有限オートマトン は、有限個の状態を持ち、入力記号に応じて状態を遷移する機械です。正規言語を認識できます。

• DFA（決定性有限オートマトン） — 各状態で入力記号ごとに遷移先が1つだけ決まる
• NFA（非決定性有限オートマトン） — 遷移先が複数ありうる。DFA と等価な表現力を持つ

例: 文字列が "ab" を含むかどうかを判定する DFA

この状態遷移図では、q0 が初期状態、q2 が受理状態です。入力に "a" の後 "b" が現れると q2 に到達し、以降はどんな入力でも q2 に留まります。DFA では各状態から各入力記号に対して遷移先が必ず1つだけ決まる点がポイントです。

プッシュダウンオートマトン（PDA）

有限オートマトンに スタック（後入れ先出しのメモリ） を追加したモデルです。スタックにより括弧の対応（ネスト構造）を管理できるため、文脈自由言語を認識できます。

例えば「開き括弧と閉じ括弧の数が一致する文字列」はプッシュダウンオートマトンで認識できますが、有限オートマトンでは認識できません。

チューリングマシン

無限長のテープと読み書きヘッドを持つ理論上の計算モデルです。「計算可能な問題」すべてを解くことができ、現代のコンピュータと同等の計算能力を持つとされます（ チャーチ＝チューリングのテーゼ ）。

正規表現とBNF記法

正規表現

正規表現（Regular Expression） は、文字列のパターンを記述するための記法です。正規言語と等価な表現力を持ちます。

記法	意味	例	マッチする文字列
.	任意の1文字	a.c	abc, aXc, a1c
*	直前の要素の0回以上の繰り返し	ab*c	ac, abc, abbc
+	直前の要素の1回以上の繰り返し	ab+c	abc, abbc（ac は不可）
?	直前の要素が0回または1回	colou?r	color, colour
[abc]	文字クラス（いずれか1文字）	[aeiou]	a, e, i, o, u
[0-9]	範囲指定	[0-9]+	1, 42, 999
^	行頭	^Hello	行頭の Hello
$	行末	end$	行末の end
`(a	b)`	選択（a または b）	`(cat

具体例: メールアドレスの簡易パターン → [a-zA-Z0-9.]+@[a-zA-Z0-9]+\.[a-zA-Z]+

BNF記法

BNF（バッカス・ナウア記法） は、文脈自由文法の生成規則を記述するためのメタ言語です。プログラミング言語の構文定義に使われます。

<digit>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number> ::= <digit> | <number> <digit>
<expr>   ::= <number> | <expr> + <number> | <expr> - <number>

• <...>: 非終端記号（さらに展開される記号）
• ::=: 「は〜と定義される」
• |: 「または」

拡張版の EBNF では { } （0回以上の繰り返し）や [ ] （省略可能）などの記法が追加されています。

計算量理論

アルゴリズムの効率を評価する指標が 計算量（オーダー） です。

O記法（オーダー記法）

入力サイズ n に対するアルゴリズムの実行時間（または空間）の増加率を、最も影響の大きい項で表します。

計算量	名称	例
O(1)	定数時間	配列の添字アクセス
O(log n)	対数時間	二分探索
O(n)	線形時間	線形探索
O(n log n)	準線形時間	マージソート、クイックソート（平均）
O(n²)	二乗時間	バブルソート、選択ソート
O(2ⁿ)	指数時間	部分和問題の全探索

n が大きくなるほど計算量の差は劇的に開きます。例えば n = 1000 の場合、O(n) は1,000回の処理ですが、O(n²) は1,000,000回、O(2ⁿ) は天文学的な回数になります。

P問題とNP問題

分類	意味
P問題	多項式時間（O(nᵏ) ）で解ける問題
NP問題	多項式時間で解の正しさを検証できる問題
NP完全問題	NP問題の中で最も難しいクラス。すべてのNP問題が多項式時間で帰着可能
NP困難問題	NP完全以上に難しい問題（解の検証も多項式時間でできない場合を含む）

P ≠ NP 予想: 「P問題とNP問題は異なるクラスである」という未解決問題で、コンピュータサイエンス最大の難問の一つです。NP完全問題の代表例にはSAT問題（充足可能性問題）や巡回セールスマン問題があります。

コンパイラ理論

コンパイラ は、高水準言語（ソースコード）を機械語（オブジェクトコード）に変換するソフトウェアです。翻訳は複数のフェーズで行われます。

フェーズ	処理内容	使う形式言語
字句解析	ソースコードをトークン（最小単位）に分割	正規言語
構文解析	トークン列から構文木（パースツリー）を構築	文脈自由言語
意味解析	型の整合性チェックや変数の宣言確認	―
最適化	実行効率を向上させるためにコードを変形	―
コード生成	機械語やアセンブリ言語を出力	―

字句解析 では正規表現を使って識別子・キーワード・数値リテラルなどを認識します。構文解析 では BNF で定義された文法規則に従い、構文木を生成します。

関連する用語として、インタプリタ はソースコードを1行ずつ解釈・実行する方式です。Python や JavaScript がこれに該当します（ただし JavaScript はJITコンパイルも行います）。また、コンパイラとインタプリタの中間的な方式として、Java のように中間コード（バイトコード）にコンパイルし、仮想マシン（JVM）で実行する方式もあります。

AIの歴史と基本概念

人工知能（AI: Artificial Intelligence） とは、人間の知的活動をコンピュータで実現する技術の総称です。AI研究はこれまで3つのブームを経験してきました。

ブーム	時期	特徴	キーワード
第1次AIブーム	1950〜60年代	探索と推論	迷路探索、定理証明
第2次AIブーム	1980年代	知識表現	エキスパートシステム、知識ベース
第3次AIブーム	2010年代〜	機械学習・深層学習	ビッグデータ、GPU、ディープラーニング

第1次・第2次ブームでは「知識を人間が与える」アプローチが主流でしたが、現実世界の複雑さに対応しきれず冬の時代を迎えました。第3次ブームでは「データから機械が自ら学習する」アプローチが突破口となり、画像認識や自然言語処理で人間に匹敵する性能を達成しています。

弱いAIと強いAI

分類	説明	例
弱いAI（特化型AI）	特定のタスクに特化したAI	画像認識、将棋AI、チャットボット
強いAI（汎用AI / AGI）	人間と同等の汎用的な知能を持つAI	現時点では実現していない

現在実用化されているAIはすべて「弱いAI」です。試験では エキスパートシステム（第2次ブーム）と 機械学習（第3次ブーム）の違いが問われることがあります。

機械学習の種類

機械学習（Machine Learning） は、データからパターンやルールを自動的に学習する技術です。学習方法により3種類に大別されます。

教師あり学習

入力データと 正解ラベル（教師データ） のペアを与えて学習させます。

• 分類: メールがスパムかどうか、画像に写っている動物の種類
• 回帰: 住宅価格の予測、気温の予測

教師なし学習

正解ラベルなしで、データの構造やパターンを発見します。

• クラスタリング: 顧客を購買行動で自動グループ分け
• 次元削減: 高次元データの可視化（主成分分析など）

強化学習

エージェントが環境と相互作用し、報酬 を最大化する行動方針（方策）を学習します。

• 応用例: ゲームAI（囲碁の AlphaGo）、ロボット制御、自動運転

主要な機械学習アルゴリズム

アルゴリズム	種類	特徴
決定木	教師あり（分類・回帰）	条件分岐の木構造で予測。結果の解釈がしやすい
ランダムフォレスト	教師あり（分類・回帰）	複数の決定木を組み合わせて多数決。過学習に強い
SVM（サポートベクターマシン）	教師あり（分類）	データ間のマージン（余白）を最大化する境界線を求める
k-NN（k近傍法）	教師あり（分類）	予測対象に最も近い k 個のデータの多数決で分類
k-means	教師なし（クラスタリング）	データを k 個のクラスタに分割。重心を繰り返し更新
主成分分析（PCA）	教師なし（次元削減）	分散が最大になる軸を見つけて次元を圧縮

決定木の例: 「天気は？ → 晴れなら外出、雨なら風速は？ → 弱ければ外出、強ければ在宅」のように、条件分岐を木構造で表現します。

ランダムフォレスト は、学習データからランダムに複数のサブセットを作成し、それぞれで決定木を構築します。最終的な予測は全決定木の多数決（分類）または平均（回帰）で決定します。個々の木は不正確でも、集合知により高い精度を実現する アンサンブル学習 の代表例です。

SVM はデータを2つのクラスに分ける境界線（超平面）を求めます。境界線とデータ点の距離（マージン）を最大化することで、未知のデータに対しても高い分類精度を得られます。

ディープラーニング

ディープラーニング（深層学習） は、多層の ニューラルネットワーク を用いた機械学習手法です。

ニューラルネットワークの基本構造

各ニューロンは入力に 重み を掛けて合計し、活性化関数 を通して出力します。学習とは、予測と正解の誤差を最小化するように重みを調整するプロセス（誤差逆伝播法）です。

活性化関数

関数	式	特徴
シグモイド	σ(x) = 1/(1+e⁻ˣ)	出力が0〜1。勾配消失問題が起きやすい
ReLU	f(x) = max(0, x)	現在最も広く使われる。計算が高速
softmax	f(xᵢ) = eˣⁱ / Σeˣʲ	出力の総和が1。多クラス分類の出力層で使用

代表的なアーキテクチャ

モデル	正式名称	得意分野	特徴
CNN	畳み込みニューラルネットワーク	画像認識	畳み込み層とプーリング層で画像の空間的特徴を抽出
RNN	再帰型ニューラルネットワーク	時系列データ	前の時刻の出力を次の入力に使い、系列データを処理
Transformer	―	自然言語処理、画像など	自己注意機構（Self-Attention）により系列の長距離依存関係を効率的に捉える

過学習と対策

過学習（オーバーフィッティング） とは、訓練データに対しては高い精度を示すが、未知のデータ（テストデータ）に対しては精度が低下する現象です。モデルが訓練データのノイズや個別の特徴まで暗記してしまうことが原因です。

対策	説明
正則化（L1/L2）	重みのペナルティを損失関数に加え、モデルの複雑さを抑制する
ドロップアウト	学習中にランダムにニューロンを無効化し、特定のニューロンへの依存を防ぐ
交差検証（k分割交差検証）	データを k 個に分割し、各回で異なる1つをテストに使って汎化性能を評価
早期終了（Early Stopping）	テストデータの誤差が増加し始めた時点で学習を停止
データ拡張	画像の回転・反転・ノイズ追加等で訓練データを人工的に増やす

交差検証の手順（5分割の例）:

1. データを5等分する
2. 1つ目をテスト用、残り4つを訓練用にしてモデルを評価
3. テスト用ブロックを変えて合計5回繰り返す
4. 5回の評価結果の平均をモデルの性能とする

この手法により、データの偏りによる評価のばらつきを軽減できます。

AIの応用分野

AI技術は多くの分野で実用化されています。試験で問われやすい主要分野を整理します。

分野	概要	代表的な技術・モデル
自然言語処理（NLP）	テキストの意味を理解・生成する	Transformer, BERT, GPT, 形態素解析
画像認識	画像から物体やパターンを識別する	CNN, 物体検出（YOLO）, セマンティックセグメンテーション
音声認識	音声をテキストに変換する	RNN, CTC, Whisper
生成AI	テキスト・画像・音声などを新たに生成する	大規模言語モデル（LLM）, 拡散モデル, GAN

生成AI

大規模言語モデル（LLM: Large Language Model） は、大量のテキストデータで学習した Transformer ベースのモデルです。文章生成、要約、翻訳、質疑応答など幅広いタスクに対応します。GPT や Claude がこれに該当します。

GAN（敵対的生成ネットワーク） は、データを生成する 生成器 と、本物と偽物を判定する 識別器 を競わせることで、リアルなデータを生成する手法です。

注意点: 生成AIには ハルシネーション（もっともらしいが事実と異なる出力） のリスクがあり、出力結果の検証が不可欠です。また、学習データに含まれるバイアスが出力に反映される AIバイアス の問題も重要です。