情報理論（基礎理論）

学習のポイント

主要な情報理論である「BNF」「逆ポーランド記法」「状態遷移図」「有限オートマトン」「待ち行列」などの概念をしっかりマスターしましょう。

1.　BNF

「BNF」とは、「プログラム言語の文法を厳密に表現する」もので、すべて文字のみで表現します。表現方法には、「順次」「選択」「反復」があります。 ●順次 <x>：：=<a><b> ここで、「：：=」は定義するという意味です。この場合、「x」という構文はaとbの並びであるという意味です。 ●反復 <x>：：=<a>・・・ これは、「x」という構文は、「a」という文字の繰り返しの意味です。 ●選択 <x>：：=<a | b> これは、「x」という構文は、aかまたはbであるという意味です。 <x>：：=[<a>] これは、「x」という構文は、aか空であるという意味です。

2.　逆ポーランド記法

「逆ポーランド記法」とは、「数式をコンピュータで処理しやすいように変換したもの」です。以下の数式を逆ポーランド記法で表現して見ましょう。 数式　f = a - b ÷ (c + d) まず、(c + d)は、cd+ と表現します。 次に、b ÷ (c + d)は、bcd+÷　と表現します。 次に、a - b ÷ (c + d)は、abcd+÷- と表現します。 最後に、f = a - b ÷ (c + d)は、fabcd+÷-= となります。これが結果です。 ●ポーランド記法 これは、例えば。a+bを逆ポーランド記法では、ab+　と表現しますが、ポーランド記法では、+ab と表現します。演算子が逆になります。

3.　状態遷移図

「状態遷移図」とは、「ある状態から別の状態、または、自分自身へ遷移」していくように描いた図のことを言います。以下のような感じです。 上記の例は、「A」「B」「C」という3種類の状態があり、それの遷移を表現しています。状態遷移図は、表形式の「状態遷移表」で表現することも出来ます。 ●有限オートマトン 「オートマトン」とは、「事象の発生とそれに応じた動作を時系列的にモデル化」したものです。「有限オートマトン」とは、オートマトンの最も単純なモデルで、時系列的な流れを「状態遷移図」で表現することが多いです。通常は、「初期状態」と「終了状態」があります。 上記は、有限オートマンです。左側の黄色の矢印が「初期状態」で右側の黄色の矢印が「終了状態」です。例えば、a->cの場合は、P1-P2-P3の順に状態が遷移して最後がP3のため、終了状態なので「受理された」と言います。また、a->b->c->a->cの場合は、P1-P2-P3-P3-P2のため最後がP3でないので「受理されません」と言います。

4.　待ち行列

「待ち行列」は、窓口が1個の場合、ケンドール記号を使用すると「M/M/1」と表現します。 このモデルでは、以下の三つの条件が成り立っている状態を指します。 1. サービス要求の到着間隔がランダム（ポアソン分布に従う） 2. 窓口を使用する時間は要求ごとにランダム（指数分布に従う） 3. 待ち行列のサービス窓口は1個 M/M/1の待ち行列で，待ち時間をW，平均サービス時間をS、利用率をPとしたとき，次の式が成り立ちます。 W = P÷(1-P)×S 例えば、利用率が0.6で平均サービス時間が3分の場合， 0.6÷（1－0.6）×3（分）＝4.5（分） 平均待ち時間は、4.5分となります。 尚、利用率は、「到着率÷サービス率」より求めます。 ・到着率…単位時間当たりの利用者数 ・サービス率…単位時間当たりに処理できる数

pafuイーランスクール