1　計算の基礎理論

1.1 情報理論

情報量は、情報の大きさを定量化したもの。
情報源には、マルコフ情報源やエルゴード情報源などがある。

事象Jが起こる確率(生起確率)をP(J)とすると、情報量I(J)は次式で定義される。

I(J)=-log_2 P(J) (ビット)

事象J1と事象J2が互いに独立であるとき、J1とJ2が同時に起きたときの情報量I(J1,2)は次のようになる。

I(J1,2)=-log_2 P(J1,2)=-log_2 |P(J1) × P(J2)|
=-log_2 P(J1) - log_2 (J2) = I(J1) + I(J2)

これを情報量の加法性という。

平均情報量(H)は情報量の期待値で定義される。

H=P(J1)×I(J1)+P(J2)×I(J2)+…+P(Jn)×I(Jn) =ΣP(Ji)×I(Ji)

マルコフ情報源

ある時点で起こった事象の生起確率が、それ以前に起こったn個の事象の生起確率に依存する情報源。n=1の場合は単純マルコフ情報源という。

エルゴード情報源

情報源で起こる事象の生起確率を長時間にわたり統計的に観察すると、ある値に収束するような情報源。一般に、世の中の事象は、エルゴード情報源と見なせることが多い。

1.2 理論と集合

1.3 グラフ理論

木は閉じていないグラフ
木の巡回法には、幅優先順と深さ優先順がある

幅優先順…同一レベルの点を順に巡回
先行順…親、左部分木、右部分木の順に巡回
中間順…左部分木、親、右部分木の順に巡回
後行順…左部分木、右部分木、親の順に巡回

2　プログラムの基礎理論

2.1 オートマトン

オートマトンはコンピュータの動作をモデル化したもの
オートマトンは状態遷移図として考えればよい

オートマトンは、コンピュータなどの計算機構を数学的に表すモデルの総称で、情報の入出力のための入出力装置、入力情報と現在の情報から次の状態を制御する状態制御装置で構成される。

オートマトンの応用例
有限オートマトンは、コンパイラの字句解析のおいて、字句の切り出しに用いることができる。字句解析は、原始プログラムの文字列から、字句(名前、予約語、定数、区切り記号)を切り出すことである。

2.2 計算量と正当性

計算量は、アルゴリズムの評価の尺度のひとつ
正当性には、部分正当性と全正当性がある

計算量

領域計算量…プログラムの実行開始から終了までに使用する記憶容量
時間計算量…プログラムの実行開始からしゅうりょうまでの所要時間
最大計算量…入力データが最悪の場合を想定したときの計算量
平均計算量…平均的な計算量
一般に、平均計算量を算出するのは、最大計算量と比較して難しいといわれ、ほとんどの場合、最大計算量が使用される

正当性

部分正当性…入力条件を満たしたプログラムを実行すると、停止した時点で得られる結果が、出力条件を満たしていることを証明すること。表明(各変数どうしに成立している関係を表現したもの)を用いる。プログラムの部分部分において、プログラムが正しいことを示すこと。
全正当性…入力条件を満たしたプログラムを実行すると、必ず停止する(停止性)とともに、得られる結果は出力条件を満たすことを証明することである。部分正当性が成立すれば、その集合である全正当性が成立するということで、プログラムが全体として正しいということである。

2.3 演算と精度

浮動小数点の規格のひとつにIEEE754がある
誤差の発生する原因に、丸め、桁落ち、情報落ちなどがある

IEEE754

IEEE754(1985)標準では、32ビットの浮動小数点を次の形式で表現する。
S：符号、1ビット
E：指数部、8ビット、2進数、バイアス値127
M：仮数部、23ビット、2進少数値
この形式で表される数値は(-1)^S (2^(E-127)) (1.M)となる。

誤差

絶対誤差
測定値、観測値、計算値などの結果から真値を代数的に引いた絶対値

相対誤差
測定値、観測値、計算値などの結果と真値との比。誤差を真値で割ったもの。

系統誤差
何らかの原因により、測定値、観測値、計算値などの結果が真値と比較して、同じ方向に偏ってしまう誤差。

誤差の発生する原因

丸め誤差
けた落ち
情報落ち
打切り誤差

3　数理応用

3.1　確率と確率分布

順列は要素の並び、組み合わせは要素の組み合わせで並び方は問わない
確率は、"事象の数÷全事象の数で計算

3.2　PERT

PERT(Program Evaluation and Review Technique)は日程計画に使う
日程を短縮するにはクリティカルパスの作業を短縮する

プロジェクトの所要日数は、前進計算によって求める。前進計画では、最早結合点時刻を求める。最早結合点時刻は、そのイベントを最も早く開始できる日程である。また、後進計算によって最遅結合点時刻を求める。最遅結合点時刻は、そのイベントを最も遅く開始できる日程である。また、最早結合点時刻と最遅結合点時刻の等しいイベントを結んだ経路が、クリティカルパスである。

3.3　待ち行列

待ち行列理論は、オンラインシステムの性能計算に使う
代表的な待ち行列理論は、M/M/1型

ケンドールの記法

4　プログラム言語

4.1　プログラム構造と基本制御構造

プログラム構造には再帰、再使用可能、再配置可能などがある
プログラムの基本構造は連接、選択、繰り返し

**プログラム構造**
再帰	プログラム実行中に、実行中の手続き自体を呼び出すことが可能な構造
再使用可能	主記憶に再ロードしなくても複数のタスクから使用可能
歳入可能	同時に複数のタスクで使用可能
逐次再使用可能	同時には使用不可能(待ち行列を作る)
再配置可能	プログラム実行中に主記憶の格納位置を動的に変更が可能

基本制御構造
連接…goto分や判断を含まない逐次的に実行される分だけで校正する論理構造。
選択…条件が成立するかどうかで実行する処理が違うときに使用する論理構造。
繰り返し…条件が成立している間、同じ処理を繰り返す論理構造。

手続きと関数
参照呼出し…サブプログラムの中で引数の値を変更すると、呼んだ側の値も変わる。
値呼び出し…サブプログラムの中で引数の値が変更されても、呼んだ側での値は変わらない。

4.2　コンパイル技法

コンパイルは字句解析、構文解析、意味解析、最適化、コード生成の順
数式解析のひとつに逆ポーランド記法がある

コンパイラの処理手順
字句解析→構文解析→意味解析→最適化→コード生成

逆ポーランド記法
コンパイルするときに、算術式を機械語に変換する過程で用いる算術式の内部表現。数式の()をはずし、実際に計算する順序で演算子が現れる。基本的には、変数の後に演算子を配置する。

1 計算の基礎理論