筆記

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 的倍數。

連通與路徑連通 一個由 [a,b] 映射到 metric space M 的函數 f ，如果 [a,b] 中所有的收斂序列 tk -> t，經過 f 也會收斂 f(tk) -> f(t)，則我們說 f 是一個連續函數。 一個集合中，若 任意兩點皆可找到一個落在集合中的連續函數相連 ，則稱此集合 路徑連通( path connected ) 。 若兩開集合 U、V 符合以下性質，則說他們將集合 A 分開： (1) U、V 聯集包含 A，(2) U、V 與 A 皆有交集，(3) U、V、A 交集為空。 若一個集合 不能被兩個開集合分開 ，則我們說此集合 連通( connected )。 任意區間 [a,b] 都是連通的。 不可能存在兩個非空無交集的閉集合，包住一個閉區間 [a,b]。 路徑連通必連通。 若 S 是一個連通集合，且 T 被夾在 S 和 S 的 closure 之間，則 T 亦連通。 一個連通集合通過連續函數作用仍然連通。 實數的連通子集 <=> 一個區間。 在 Rn 中的一個連通開集合必路徑連通。

動態規劃 生產線問題，到達每一關最短的時間，可以由上一關的最短時間加上多的時間比較而知，由此遞迴需時O(2^n)。使用動態規劃只需 O(n)。 具有以下兩性質者可以利用動態規劃： optimal substructure：可以使用遞迴。 Overlapping Subproblems：遞迴時會重複遇到同樣的問題。 m*n 矩陣和 n*o 矩陣相乘需要運算 O(mno) 次，得到 m*o 矩陣。 因此一長串矩陣相乘，有不同的組合、括括號的方式，在最後一次相乘的各種方式中找出最小值，就可得到最快的方法，藉此可遞迴解決此問題。 在每一種方式中，計算兩子問題的最快方法再加上最後一次相乘的時間，即可算出某種括號方式的最快時間。但直接遞迴需要用到 O(3^n) 的時間。使用動態規劃只需 O(n^3)。 一個字串的 subsequence 是指由原字串剔除(沒有剔除也算在內)掉某些字元後剩下的字串，兩個字串的 longest common subsequence 是指兩個字串相同的子字串中最長的那些字串。 兩個字串的字尾如果相同，那字尾一定在 LCS 之中，且 LCS 是兩個字串都剪掉字尾後的 LCS 再加上字尾。若是字尾不相同，那麼 LCS 要嘛不包含第一個字串的字尾，要嘛不包含第二個字串的字尾，利用此性質可得一遞迴解法，時間 O(2^(m+n))，使用動態規劃只需 O(mn)。 電子字典中，每一個字被查詢的機率不同，每個錯字區間也是如此，希望設計出一個搜尋樹(最佳二元搜尋樹)，使得平均搜尋的時間最短，在一個搜尋樹中，搜尋時間的期望值即每個字或區間的機率乘上其所在的深度再相加，可以發現最佳搜尋樹的兩個子樹也要是最佳搜尋樹，而一棵樹的搜尋時間為整棵樹的機率加上兩個子樹的搜尋時間。藉此可得出一遞迴方法計算所有可能的搜尋樹得出最佳解。 使用動態規劃，由只有一個元素的搜尋樹開始，計算搜尋時間，層層疊上計算出所有可能的子搜尋樹的最佳解，最後即可得完整的最佳搜尋樹。

一個非空集合 S  countable，等價於： (1)存在由 S 到正整數的一對一函數 (2)存在由正整數到 S 的映成函數 countable 個的 countable set 聯集仍然 countable countable set 的 finite product 仍然 countable 實數中的任意區間皆不 countable

path VS trail 在一個 graph 中，我們將相鄰的頂點一個個連接起來，形成一個頂點序列，若其中每個頂點只出現一次，這就是一個 path 。 trail 是 path 的推廣， 我們將相鄰頂點一個個連接起來，形成一個頂點序列，若此序列沒有重複使用任一條 edge，則這個序列就是一個 trail。 由定義可知， 一個 path 必定也是一個 trail ，因為頂點不重複的 path ，其連線必定也不會重複；然而 trail 不一定是個 path ，因為 trail 可能使用了同一個頂點的兩條以上連線，如此一來就會造成該頂點重複。 然而我們可以經由修剪 trail 序列而造出 path 序列，只要將 trail 中重複的頂點之間的所有頂點去掉，例如：a-b-c-d-e-b-f   ->   a-b-f，直到序列中沒有重複的頂點即可 ，我們可以發現這個過程並沒有改變序列中任何頂點的鄰居，因此序列中相鄰的頂點仍然會是 graph 中相連的頂點。 簡單的說： path 不允許頂點重複； trail 不允許連線重複。