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

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

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

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

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

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。而且运算公式也完全一样。同样适合交换律、结合律、分配率、吸收率和ド・モルガン法則。

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

１．１．１　信息量，信息源，逻辑运算

这本书讲得不详细，似乎只是个大纲。这些在大学学过的课程早就忘了，今天还要查查资料。
計算の基礎理論
1．情報量の計算：
有る事件の発生確率はP(ｊ)とすると、この事件が確定するため必要な情報量I(j)は
I(j)=-log_2 P(j) bit
だから、発生確率が1/2の事件は1bitの情報量がある。(なぜならば、発生確率1/2は1bitの0または1で確定できるから)
これは大学の「informatics」の基礎の基礎だった。ここまでは覚えている。
次の平均情報量H(エントロピー)はすっかりと忘れた。(注：平均情報量H(エントロピー)＝entropy就是熵的意思)
j1・・・jnというn個事件を確定するために、平均的に必要な情報量は：
H=P(j1)×I(j1)＋P(j2)×I(j2)＋・・・＋P(jn)×I(jn)=ΣP(ji)×I(ji)
上記の平均情報量は、j1・・・jnのn個事件の発生確率は等しい時は最大である。
Hmax=ΣP(ji)×I(ji)=log_2 n
2．情報源
马尔科夫(Markov)信息源
マルコフ情報源：ある時点で起こった事件の発生確率が、その前に起こったｎ個事件の発生確率に依存する情報源である。
n=1の時に、単純マルコル情報源と言う。
エルゴード情報源
情報源で起こる事件の発生確率は長い期間にわたり統計的に観察すると、ある値に収束することがある。このような情報源はエルゴード情報源である。
例えば、サイコロのある値が出る確率は長期間で観察する時、1/6に収束する。
＜すっかり忘れた。＞
3．論理演算(逻辑运算)
x and y ⇒　x・y
x or y ⇒　x＋y
not x ⇒^x　(xの上に横線)
同一の法則(同一律)：x・x=x x＋x=x
交換法則(交换律)：x・y=y・x x＋y=y＋x
結合法則(结合律)：x・(y・z)=(x・y)・z x＋(y＋z)=(x＋y)＋z
分配法則(分配率)：x・(y＋z)=x・y＋x・z x＋(y・z)=(x＋y)・(x＋z)
ド・モルガンの法則(中文叫啥来着？)：not（x・y）=not(x)＋not(y) not(x＋y)=not(x)・not(y)
4．カルノー図
論理演算式を簡略化するツールである。大学時代は結構得意だったが、今は全然できなくなった。後で資料を探す。