数値解析・グラフ理論・待ち行列

イントロ

計算や記法の入口をつくる

基本情報技術者試験で扱う「数値解析・グラフ理論・待ち行列」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

とは、解を挟む区間を半分ずつ狭めて近似解を求める方法です。
見分けるポイント: は、絶対誤差を真値などの基準値で割った誤差です。は、頂点と辺で対象間の関係を表す構造です。は、到着と処理の確率的な関係から待ちを分析するモデルです。は、処理能力に対して到着する仕事量が占める割合です。

公式

計算・記法を、問題文の条件に当てはめて読む。

相対誤差

相対誤差=絶対誤差真値

誤差の大きさを、元の値に対する割合として見ます。

使うときのコツ

値の桁が違うときは絶対誤差だけで比べません。

待ち行列の利用率

ρ=λμ

到着率λとサービス率μから、処理能力がどれだけ使われているかを見ます。

使うときのコツ

ρが1に近いほど待ちが増えやすくなります。

解くコツ

近似、つながり、待ちのどれをモデル化しているかを先に判定する。単位、条件、対象範囲をそろえてから式や記法を使います。

例

場面: 受付窓口の到着率と処理率から待ちが増える条件を読む例
順に考えると: まず二分法が何を表すかを確認します。次にニュートン法との違いを、問題文の対象・条件・順序から分けます。ここでは近似、つながり、待ちのどれをモデル化しているかを先に判定する。
ここが結論: この例では、近似、つながり、待ちのどれをモデル化しているかを先に判定することが要点です。答えを選ぶときは、平均処理能力が平均到着数を少し上回れば常に待ちがないと思うという読み違いを避けます。

注意

確認

Q1

数値解析・グラフ理論・待ち行列を問題で読むとき、最も適切な見方はどれですか。

まとめ