二分法・グラフ・待ち行列｜近似と誤差、混み具合の計算【基本情報技術者試験 科目A】

科目A 第1章 基礎理論1-6　数値解析・グラフ・待ち行列最終更新 2026-09-26

答えが式できれいに出ないとき、コンピュータは近づけて求めます。 この回では、その代表である二分法と、近似につきものの誤差の呼び分け、 点と線で関係を表すグラフ、そして混み具合を計算する待ち行列を扱います。 計算問題として出るのは、待ち行列と誤差です。

二分法 ── 範囲を半分にしていく

2乗して 2 になる数（√2）を、割り算と掛け算だけで求めます。 まず、答えが 1 と 2 のあいだにあることは分かります（1×1＝1、2×2＝4 なので）。 あとは真ん中で試して、どちら側にあるかを見るだけです。

√2 を求める（x × x ＝ 2 になる x を探す）。まず 1 と 2 のあいだ

1回目  中点 1.5     1.5 × 1.5 ＝ 2.25 → 2 より大きい → 1 〜 1.5
2回目  中点 1.25   1.25 × 1.25 ＝ 1.5625 → 2 より小さい → 1.25 〜 1.5
3回目  中点 1.375 1.375 × 1.375 ＝ 1.890625 → 2 より小さい → 1.375 〜 1.5

3回で、もとの幅 1 が 0.125 まで狭まりました（実際の √2 は 1.41421…）。

1回ごとに範囲が半分になるので、10回で約1000分の1まで狭まります。 この進め方を二分法といいます。接線を引いて次の候補を決めることで、より少ない回数で近づける方法がニュートン法です。 また、分かっている値のあいだを埋めて推定するやり方を補間法といいます。

誤差の呼び分け

近似で求めた以上、真の値とのずれが残ります。ずれの表し方は2つです。

真の値 3.141 592 65…  を  3.14  で計算した

絶対誤差   3.141 592 65 − 3.14 ＝ 0.001 592 65
相対誤差   0.001 592 65 ÷ 3.141 592 65 ＝ 約 0.000 5（0.05%）

大きい数を扱うときは、絶対誤差が大きくても、割合では小さいことがあります。

打切り誤差は「途中でやめたから」、丸め誤差は「桁が足りないから」です。 原因が違うので、対策も違います。打切り誤差はくり返しの回数を増やせば減り、丸め誤差は桁数の多い形式を使えば減ります。

グラフ ── 点と線で関係を表す

数学の「グラフ」は、折れ線グラフのことではありません。点と、それを結ぶ線で関係を表したものです。

無向グラフ（線に向きがなく、行き来できる）

      A---B
       \ /
        C

有向グラフ（矢印の向きにだけ進める）

      A-->B
      ^   |
      |   v
      +---C

点を頂点、点どうしを結ぶ線を辺といいます。路線図は無向グラフ、作業の順序は有向グラフで表します。

コンピュータで扱うときは、行と列に頂点を並べた表の形にします。これを隣接行列といいます。

無向グラフ（A−B、A−C、B−C）の隣接行列

      A  B  C
   A  0  1  1      1 ＝ 辺がある
   B  1  0  1      0 ＝ 辺がない
   C  1  1  0      ← 対角線をはさんで左右対称

有向グラフ（A→B、B→C、C→A）の隣接行列

      A  B  C
   A  0  1  0      A から B へは行ける
   B  0  0  1      B から A へは行けない
   C  1  0  0      ← 左右対称にならない

行が「どこから」、列が「どこへ」です。無向グラフは行き来できるので、必ず左右対称になります。

待ち行列 ── 混むほど、待ち時間は跳ね上がる

レジやサーバの混み具合を計算するのが待ち行列です。 試験で出るのは、窓口が1つの形（M/M/1 モデル）です。

レジ1台。1人の対応に平均 4 秒。レジが動いている割合（利用率）は 0.5

平均待ち時間  0.5 ÷ (1 − 0.5) × 4 ＝ 4 秒
平均応答時間  4 ＋ 4 ＝ 8 秒（待ち時間 ＋ 対応の時間）

利用率は、1時間に来る人数 ÷ 1時間にさばける人数でも求まります（前者を平均到着率、後者を平均サービス率といいます）。1時間に450人来て、900人さばける力があるなら 0.5 です。

1 − 利用率は、窓口が空いている割合です。 空きが小さくなるほど、割り算の答えは大きくなります。 利用率が 1 に近づくと分母が 0 に近づくので、待ち時間は際限なく伸びます。 これは、客が等間隔ではなくばらばらに来ることを前提にした計算です。

ここで効くのが利用率です。同じ対応時間でも、利用率が上がると待ち時間は急に伸びます。

利用率が 0.5 から 0.9 へ1.8倍になっただけで、待ち時間は 4 秒から 36 秒へ9倍に伸びます。 「まだ余裕がある」と見えるうちに手を打つ理由が、この伸び方です。

最適化と、そのほかの道具

残りは名前と役割を押さえます。最適化問題は、条件の中でいちばん良い答えを探す問題です。問題の呼び名と、その解き方の呼び名が別にあります。

⚠️ 数式処理は最適化とは別で、数値ではなく式のまま 因数分解や微分をコンピュータに行わせることを指します。

まとめ

次に読む