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

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

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

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

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

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になるため、有効桁数が激減する。
３．情報落ち：数値が事実上無視されてしまう現象。大きな値と小さな値の加減算を行った場合。
４．打切り誤差：打ち切りは、極限操作を有限のところで打ち切ることである。例えば無限級数の和、無限に計算することは不可能なので、適当な誤差の範囲で計算を打ち切るような場合。

１．１計算の基礎理論(3)

１．１．３グラフ理論　（图论）

俺晕！这一个小节就是俺们大学里的一门课啊。这区区1页纸，说了这点儿皮毛，到底让俺掌握到哪种深度呢？
图论，在大学都没学好——当时教课的老师都不会。

---

グラフ：辺の集合と点の集合からなる図形である。
木：閉路のないグラフである。(閉路＝loop自分自身に戻ってくるパス)
ｎ進木：ノードが高々ｎ個の子を持つ木をｎ進木或いはｎ分木と言う。
順序木(ordered tree)：ノード間に順序がある木。
探索木：各ノードに要素を格納している木。
2分探索木：各ノードに値を持ち、左の子の値≦自ノードの値≦右の子の値となっている2分木を2分探索木と言う。
ヒープ(heap)：ノードの値と子の値の間に大小関係が成立している2分木である。関係は自ノードの値≦子ノードの値と自ノードの値≧子ノードの値と二種類がある。
AVL木：どのノードにおいても、左右の部分木の高さが高々１しか違わない2分木である。考案したAdelson-Velskii-Landisの頭文字からAVL木と呼ばれる。
B木：m≧3。葉以外の各節点の子供の数の最大はmである。子供の数の最小は≧m/2の最小整数。根の子供の数のは最小で2である。根から葉までの深さはどの葉についても同じである。

１．１計算の基礎理論(2)

１．１．２　集合

集合：同じ属性の集まりである。
a∈S　元素a属于集合S。
S1⊂S2 集合S1包含于(属于)S2。亦即集合S1是集合S2的子集。
集合的运算
集合的运算有：
和(∪)、積(∩)、差(―)(上线)。其实这分别等于逻辑运算的and、or和not。而且运算公式也完全一样。同样适合交换律、结合律、分配率、吸收率和ド・モルガン法則。