基礎理論(3)

プログラムの基礎理論

オートマトン

コンピュータに形式言語で記述された分を入力して結果を出力するための仮想的な機械概念のこと
※有限オートマトン：状態と入力した値の組み合わせた有限個のもの

状態遷移表

形式言語で記述された文を入力して結果を出力するまでの状態を「初期状態」「中間状態」「最終状態」の3つに分類できる。初期状態は一つ、中間状態、最終状態は複数の場合がある。この状態の遷移を表したものを「状態遷移表」という。文を先頭から末尾まで解釈した結果として最終状態になったら「文を受理した」という

状態遷移表

		遷移先
		A	B	C
遷移元	A	0	1
	B	0		1
	C	0		1

状態遷移図

オートマトンの状態の遷移を図で表したもの。初期状態と中間状態を円、最終状態を二重の円で表し、遷移を矢印で表し、矢印の上にイベントを記入

構文や数式の表現

BNF(バッカス・ナウア記法）

文脈自由文法自体を定義するための言語のひとつ

＜＞	括弧＜＞の中の文字列は一つのメタ変数
::＝	「〜とは〜であると定義されている
｜	「または」の意味
その他の記号	その記号そのもの

(例)＜数字＞::＝0｜1｜2｜3｜4｜5｜6｜7｜8｜9
　　数字とは0または1…または9である

正規表現

いくつかの文字列を一つの形式で表現する方法

.	任意の１文字
＊	直前の文字またはパターンを0回以上繰り返す
？	直前の文字またはパターンを0回または1回繰り返す/td>
＋	直前の文字またはパターンを1回以上繰り返す
[m−n]	m〜nまでの連続した文字の中から１文字を選択する

(例)[A−Z]＋[0−9]＊
　　英大文字を１回以上繰り返した後に、数字を0回以上繰り返す

逆ポーランド表記法

演算子を計算式の後ろに記述することで、計算式をコンピュータで処理しやすい形式に変換する記述法
(例)　式Y＝(A−B)×C　⇒　YAB−C×＝

待ち行列理論

概要

顧客がサービスを受けるために行列に並ぶような確率的に挙動するシステムの混雑現象を、数理モデルを用いて解析することを目的とした理論
電話交換機、情報ネットワーク、生産システム、空港や病院などの設計や性能評価に応用される
性能評価指標としては、待ち行列長・待ち時間・スループットなどが用いられる

Ｍ／Ｍ／1モデル

ケンドールの記法で待ち行列のモデル
以下の３つの条件が成り立っている状態
●サービス要求の到着間隔がランダム(ポアソン分布)
●窓口を使用する時間は要求ごとにランダム(指数分布)
●待ち行列のサービス窓口は１個
※約束事：行列へ割り込む、列の途中で抜け出すことは考えない。サービス要求は到着順に受け付ける

平均到着率（λ：ラムダ）

単位時間あたりに到着する人(モノ)の数のこと
到着間隔：ある人(モノ)が到着してから次の人(モノ)が到着するまでの時間間隔のこと

平均到着率＝λ 平均到着間隔(TA)＝1／λ

平均サービス率（μ：ミュー）

一つの窓口でどれだけサービスを処理できるかの割合のこと
サービス時間：並んでいる人(モノ)を処理する時間

平均サービス率＝μ 平均サービス時間(Ts)＝1／μ

平均利用率(ρ：ロー）

窓口がどれだけ利用されているかということ

平均利用率(ρ)＝平均利用率(λ)×平均サービス時間(Ts) 　　　　　　＝平均利用率(λ)／平均サービス率(μ)

平均待ち時間（Tw）

サービスを受けるまでの待ち時間のこと

Tw：平均待ち時間 Ts：平均サービス時間

平均応答時間（T）

平均待ち時間と平均サービス時間を足した時間

通信理論

A/D変換

情報をアナログからデジタルへ変換することを「A/D変換」と呼ぶ。A/D変換では下記のようなステップを経て変換を行う

標本化(サンプリング)	オリジナルのアナログデータを一定間隔で分割し、情報を取り出す
量子化	取り出した情報を数値化する
符号化	標本化、及び量子化によって得られた数値を2進数に変換する
暗号化	符号化されたデータをデジタルデータに変換する

誤り検出方法

データを伝送するときにデータの誤りを検出する技術

パリティチェック方式		データを伝送するときに、検査用のビット(1ビット)を追加することで、データの誤りを検出する方式
	偶数パリティチェック	ビット列の[1]の個数が偶数になるようにパリティビットを追加する
	基数パリティチェック	ビット列の[1]の個数が奇数になるようにパリティビットを追加する
	垂直パリティチェック	ブロックと呼ばれる、ある一定単位のまとまり(通常7ビット)のデータに含まれる[1]の数をカウントし、その数の奇遇によって、パリティビットとよばれるデータを付加・送信する
	水平パリティチェック	ブロックごとに、BCC(Block Check Character)と呼ばれるパリティビット列を付加して、データ誤りが発生したかどうかを検出する
CRC方式		ビット列のデータをある生成多項式で割った余りを検査用の符号として、データに付加して送信する方式。誤りビットを特定できないため、誤り訂正は行えないが、ランダム誤りやバースト誤り(連続した複数のビット誤り)は検出できる
チェックサム		データをブロック化し、各ブロック内のデータを合計した検査符号。送信データの誤りのみ検出可能

誤り訂正方法

データを伝送するときに、データの誤りを訂正する技術

ハミング符号方式	データを伝送するときに、2ビットの誤りを検出し、1ビットの誤りを訂正する符号(ハミング符号)を追加することで、データの誤りを検出・訂正する方式
ECC	誤り訂正符号。バイト単位で構成されたSolomon符号と呼ばれる冗長符号を用いて、バイト単位で訂正処理を行う

伝送制御

基本形データ伝送制御手順

データをブロックに分割し、「伝送制御キャラクタ」を追加してデータを転送する手法。キャラクタ同期方式を使い、伝送できるのはテキストデータのみ。ATMの伝送など確実性が要求される場合に使用
誤り制御は「バリティチェック」を使用

HDLC手順(High level Data Link Control)

大量かつ、高速なデータ通信に対応。基本形データ転送制御手順では、任意長のデータのの転送が可能なため、テキスト以外の多様なデータにも対応。データはフレームという単位で送られ、相手の応答を待たずに連続して転送。また、誤り制御はより信頼性の高いCRC方式を使用

名称	説明
プラグシーケンス	フラグ同期化のためのビット(01111110)
アドレス	送信側のアドレス
制御	送信したフレーム番号
情報	伝送データ
フレームチェックシーケンス	CRC符号

無手順

名前通り、決まった手順が存在しない手順。一般に非同期方式を用い、あらかじめ送受信間で伝送制御文字を取り決めておきデータの伝送を行う