筆記

f：A->R 的黎曼積分：若 A 是 Rn 的有界子集，且 f 有界 將 f 擴展至一包含 A 的立方體 B 中，將 A 以外的點設為0。 對 B 做 partition P 得到上和與下和 對任意 partition 得上積分下積分 上下積分若相等則得黎曼積分 黎曼條件 ：f 黎曼可積，若且惟若對任意誤差 e，皆可 找到一 partition 使上下和之差距小於 e。

一、PID 若 F 是一個體，則 F[x] 的任意 ideal 皆 principle。 整數的 ideal 皆 principle。 一個定義有除法的 integral domain 只會有 principle 的 ideal。我們將這種 domain 稱為 principle ideal domain (PID) 。因此對體 F 而言，F[x] 也是 PID。 F[x]/< h> 中的元素為 deg 比 h 小的多項式所代表的 coset。   若 F 為一體，h 為 F[x] 中次數大於一的多項式，則以下三點等價： F[x]/< h> 是一個體 F[x]/< h> 是一個 integral domain h 在 F[x] 中不可分解 若 R 是一個  PID ，p 是 R 中一個非零非 unit 元素，則以下等價： (在一般的 integral domain 中，往下推是正確的，而 PID 使得往上推也可行。) < p> 為 max ideal R/< p> 是個 field < p> 為 prime ideal R/< p> 是個 integral domain p 是 prime p 不可分解

Weirestrass thm： f：[0,1] -> R 為一連續函數，則不論多近的距離 e ，皆存在一多項式 p ，使得 || f-p || < e，也就是說， 可以用多項式逼近任意 C([0,1],R) 中的函數。 [a,b] 中的多項式也在 C([a,b],R) 中 dense。 Stone-Weierstress thm： 若 A 為某距離空間中的一個緊緻集，若 B 包含於 C(A,R) 且滿足以下條件，則 B 在 C(A,R) 中也會 dense 。(也就是說 B 的 closure 等於 C(A,R))： B 中函數作加法、乘法及係數積具有封閉性。 B 包含常函數。 對 A 中任意兩不同點，存在 B 中一函數，使得此兩點函數值不同。 Abel's test： 若 fn 級數均勻收斂 ， gn 隨著 n 增加而單調遞增或遞減 ，且存在常數 M 使得對任意 n 及變數 | gn | < M ，則 gn*fn 之級數亦均勻收斂。 Dirichlet's test： 若存在 M 使得對任意變數及 n， fn 的部分和 |sn| <= M ，且 gn 隨著 n 增加而均勻遞降到零 ，則 fn*gn 之級數會均勻收斂 由 root test 之倒數得到冪級數的收斂半徑，在收斂半徑內冪級數絕對收斂，半徑外則發散。 冪級數在其收斂半徑中無限次可微，微分後具有相同收斂半徑。

若 f：U->C 在開集合 U 中可解析，則 f 在 U 中無限次可微。 若 f 在開集合 U 上可解析，則對 U 上一點 a，到 a 點的割線斜率函數 g 也會在 U 上可解析。 g = f(z)-f(a)/z-a，when z != a。 g = f'(a)，when z = a。 若 f 在一圓內可解析，且有 a1、...、an 等零點，將函數 g 定義為，當 z 不再零點上時，g(z) = f(z)/(z-a1)...(z-an)，而當 z 在零點上時則取其極限。則 g 在此圓內亦可解析。

一、環 (Ring) 與體 (Field) 環 是一個擁有兩個二元運算的集合，通常以加法和乘法表示，此集合在加法下會構成一個 可交換群 ，並在乘法下構成一個 monoid ，同時 乘法對加法具有分配律 ，也就是說，滿足以下性質的集合就稱為一個環： 具有加法及乘法運算，且具有封閉性。 有加法單位元 0。 有加法反元素 -a。 有加法結合律。 有加法交換律。 有乘法單位元 1。 有乘法結合律。 a*(b+c) = a*b + a*c (b+c)*a = b*a + c*a。

一、複數 我們重新將複數定義為 ( R^2, +, * ) ，其中 * 為一個特殊的乘法，運算結果為 ( 配對相乘後相減 , 交叉相乘後相加 )。 複數是一個 有序數對 ，也就是說除非兩座標相等，否則座標調換後為另一個複數。 實數可視為第二個座標為零的複數，而複數之運算也可視為實數之推廣。 若複數 z =(x,y) ，則 x 稱為 z 之實部 Re(z) ，y 稱為 z 之虛部 Im(z)。注意： 實部與虛部皆為實數。   兩複數相等，即兩者座標相等，即兩者實部與虛部相等。 我們通常用 1 表示 (1,0) ，用 i 表示 (0,1)，因此 z = (x,y) = x+ iy。 若複數 z = (x,y)，則 -z = (-x,-y)，1/z = (x/(x^2+y^2), -y/(x^2+y^2))。 複數是一個 field 。 兩複數無法比較大小。 複數 z =(x,y) 的長度( modulus ) |z| 即 z 在複數平面上到原點之距離 (x^2+ y^2)^(1/2)。 三角不等式：兩複數長度的差 <= 兩複數之和或差之長度 <= 兩複數長度的和 a+bi 之共軛複數為 a-bi ，為一長度相等角度相反(差一負號)之數。 一複數與其共軛相乘 = 此複數長度之平方。 先做運算再取共軛 = 先取共軛再做運算。 Re(z) = (z + z_)/2 、 Im(z) = ( z - z_ )/2i。 (以底線表示共軛) z = a+bi 的極座標：r(cosx + isinx) = r(cisx) = r exp(ix)，其中 r 為 |z|，x 為 z 與實數軸之夾角。 複數 z 極座標之角度可有無窮多種選擇，而兩種角度皆相差 2n(pi)，這些角度所成的集合稱為 z 之 argument，寫做 arg(z)。我們在 arg(z) 中選定 大於 -pi 小於等於 pi 者稱之為 principle branch of arg(z)，寫做 Arg(z)。因此， arg(z) = Arg(z) + 2npi 複數相乘為長度相乘，角度相加。

Minmum spanning tree 在一個無向連通圖中，一個包含所有頂點的樹稱為 spanning tree，若圖裡的連線有權重，則權重總和最小的 spanning tree 就是 Minmum spanning tree。而在一個圖中， MST 可能有好幾個。 每個頂點所相鄰權重最小的連線必定包含於 MST 之中。 將 MST 中某些點和連線合併後，剩下的樹仍然是合併後所產生之子問題的 MST。 由上兩點可知，此問題可使用貪婪演算法，將某些必包含於 MST 的點和連線合併後，在遞迴求剩餘圖的 MST。 Kruskal 演算法： 找到整個圖中權重最小的連線，將此連線相連的兩點合併，遞迴直到完成。時間複雜度為 O(E logV)。 (必須注意，若兩頂點已合併則之間的連線不可再使用。) Prim 演算法： 由某一點出發，找相鄰權重最小的連線，將連線兩端合併，遞迴。此演算法可使用 heap 達成，將出發點相鄰連線皆丟入堆疊中，再找出權重最小者，若連線的對面不是已合併的頂點，則將該頂點合併，且加入所有與它相鄰的連線於堆疊中。時間複雜度為 O(E logV)。

一、拉格朗日定理 coset： 若 H 是群 G 的子群， g 為 G 中元素， 則稱 Hg 為 H 包含 g 的 right coset 。 其中 Hg 即是 H 每個元素 h 與 g 相乘 (hg) 所成的集合。 (若是改變乘法方向則為 left coset。) 若 a,b 落在 H 的同一個 right coset ，則 a = hb，h 屬於 H。 H 的所有 right coset 會形成 G 的一個分割 (partition)。 (因為單位元素在 H 裡， G 裡的任一個元素必定在某個 coset 當中...) 若 H 為有限子群，則 H、Hg、gH 中的元素個數相同。 拉格朗日定理 ：若 G 是一個有限群，而 H 是一個子群，則 |H| 必整除 |G| 。 ( |為集合元素個數之符號| ) index of H ：|G|/|H|，在 G 之中 H 不同的 right coset 的個數。 若 G 為有限群，則 任意元素之 order 可整除 G 的元素個數 。 (任意元素皆可形成一個循環子群，拉格朗日定理) 若是 |G| = n，則 G 中任意元素的 n 次方皆為 1。 若是 |G| 為質數，G 必為循環群 。 尤拉函數 f(n) = 比 n 小且與 n 互質的正整數數量。 f(質數 p) = p-1。 f(兩質數相乘 p*q) = (p-1)*(q-1)。 f(n) = |Zn*|。 尤拉定理：a 的 f(n) 次方同餘 1 (mod n)，只要 a 與 n 互質。 費馬小定理：a 的 p-1 次方同餘 1 (mod p)，只要 p 是質數且 a 不是 p 的倍數。