１．２ プログラムの基礎理論

１．２．１アートマトン(图灵自动机)

有限自动机、无限自动机的概念。
有限自动机的状态迁移。入力は受理された(输入受理)的概念。
图灵自动机一般用在编译程序的字句解析中。

１．２．２計算量と正当性

計算量：領域計算量と時間計算量がある。
領域計算量：プログラムの実行開始から終了までに使う記憶容量。
時間計算量：プログラムの実行開始から終了までの所要時間。

O記法
Ｏ(1)＜Ｏ(log_2 n)<Ｏ(ｎ)<Ｏ(nlog_2 n)<Ｏ(n^2)<Ｏ(n^3)<...<Ｏ(n^c)<Ｏ(2^n)<Ｏ(3^n)<...<Ｏ(c^n)<Ｏ(n!) Ｏ(fn)+O(gn)=Ｏ(max(O(fn),O(gn)))--也就是说，两个算法的复杂度相加，等于其中复杂度大的。试想：两个程序同时执行，执行的时间取决于复杂的一方。 Ｏ(fn)×Ｏ(gn)=Ｏ(fn×gn)

１．２．３演算と制度

IEEE754浮動小数点数：这个还没有理解，需要查资料。包括IEEE754小数10进制和2进制的相互转换。还有一般的10进制整数转换和小数的转换方法。
誤差：
絶対誤差、相対誤差、系統誤差。
誤差発生する原因：
１．丸め誤差：丸め：丸め誤差の「丸め」とは、任意の桁数以上の精度の数値を端数として処理してしまうことであり、四捨五入や切り上げ、切り捨てなどを含んでいる。丸め処理は主に数値の桁数を揃えるために行われる。
２．桁落ち：有効桁数がなくなる現象である。例えば、ほぼ等しい数値同士の引き算など、上位桁が0になるため、有効桁数が激減する。
３．情報落ち：数値が事実上無視されてしまう現象。大きな値と小さな値の加減算を行った場合。
４．打切り誤差：打ち切りは、極限操作を有限のところで打ち切ることである。例えば無限級数の和、無限に計算することは不可能なので、適当な誤差の範囲で計算を打ち切るような場合。