このページでは，基本情報技術者試験をはじめとする情報処理技術者試験で頻出となる，極限値・グラフ理論・待ち行列理論について，図や例を用いてシンプルにまとめています。各分野の基本用語や考え方を中心に，初学者の方でも理解しやすい構成にしています。
極限値とは
極限値とは，数の列などが収束や発散して近づく値のことをいいます。
収束する
ある値に限りなく近づくこと
発散する
限りなく大きな値（または，小さな値）になること
例）収束と発散
練習問題（極限値）
問 次の極限値を求めなさい。
(1)  | (2)  |
(3)  | (4)  |
(1) 1 (2) ∞ (3) －9 (4) 32
広告
グラフ理論とは
グラフ理論とは，図形の性質を解析する理論のことをいいます。
有向グラフと無向グラフの違いと例
有向グラフとは，枝（エッジ）に方向性のあるグラフのことをいいます。どちらからどちらにつながっているのかを表すことができます。
無向グラフとは，枝（エッジ）に方向性のないグラフのことをいいます。
隣接行列とは
隣接行列とは，有限なグラフを表すために用いられる正方行列のことをいいます。
広告
待ち行列理論とは
待ち行列とは，スーパーのレジなどを待つときにできる行列のことをいいます。
待ち行列理論とは，ある行列に並んだときに，平均でどれだけ待たされるかを分析する理論のことをいいます。待ち時間に影響を与えると考えられる要素には，次のようなものがあります。
到着率とは
到着率は，行列に，人などが，どのくらいの頻度でやって来るかということを表します。
※ 到着間隔…行列に，人などが到着してから次の人などが到着するまでの時間（到着率の逆数）。到着間隔がランダムな場合をM，一定の場合をD，一般分布の場合をGと表す（到着間隔がランダムな場合は，ポアソン分布に従う）。
サービス時間とは
サービス時間は，実際の作業にかかる時間のことです。
※ サービス時間がランダムな場合をM，一定の場合をD，一般分布の場合をGと表す（サービス時間がランダムな場合は，指数分布に従う）。
窓口の数
窓口の数は，並ぶ場所の数のことです。
待ち行列モデル
待ち行列は，次のように表記します。
到着率 ／ サービス時間 ／ 窓口の数
M／M／1モデルとは
M／M／1モデルは，到着率がランダム（ポアソン分布に従う）で，サービス時間がランダム（指数分布に従う）で，窓口が1つの場合の，待ち行列のモデルです。
※ Mは，到着率やサービス時間がランダムであることを表す。
例）ある店にレジが1台あり，そのレジには平均で10分に1人の客が並び，1人当たりの精算時間が2分である場合，
(1) 利用率
利用率 ＝ 2(分) ÷ 10(分) ＝ 0.2
(2) 平均到着率
平均到着率 ＝ 1到着間隔 ＝ 110（分） ＝ 0.1(人)
※ 1分当たりの到着数
※ 平均到着率を使用して利用率を求めることもできる。利用率 ＝ 0.1(人) × 2(分) ＝ 0.2
(3) 平均待ち時間
平均待ち時間 ＝ ρ1 － ρ × サービス時間 ＝ 0.21 － 0.2 × 2(分) ＝ 0.5(分)
※ ρ1 － ρ （ρ ＝ 利用率）は，行列に並んでいる客の平均の数を表す
(4) 平均応答時間
平均応答時間 ＝ 平均待ち時間 ＋ サービス時間 ＝ 0.5(分) ＋ 2(分) ＝ 2.5(分)
まとめ
今回は，基本情報技術者試験で頻出となる，極限値・グラフ理論・待ち行列理論について，基礎をシンプルにまとめてみました。これらの分野は，用語の意味と考え方を押さえることが重要だと思います。
理解が進んだら，過去問題等にもチャレンジしてみてください。
