筆記

連通與路徑連通 一個由 [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 不允許連線重複。

planar graphs 若一個 graph G 可以畫出一個兩兩 edge 不相交的平面圖，則我們說他是一個 planar graph。而這種不相交的畫法就稱為 G 的 plane graph。 一個 planar graph 可以有許多 plane 畫法。

Def：invariant subspace 若 T 為作用於 V 的線性算子(本文的 V 皆假設為有限維向量空間)，W 為 V 的子空間，且 T(W) 包含於 W，則我們說 W 是 T 作用下的的不變子空間 (T-invariant subspace)。 不變子空間中的元素經過線性變換後，仍會留在原本的子空間中，特徵空間正具有這樣的性質，因為其中向量經過線性變換只會有倍數的改變，因此當然落在原本的特徵空間之中，不僅是特徵空間，由任意幾個特徵向量織成的空間也具有此性質，因為經過線性變換後，其中的向量仍會是這幾個特徵向量的線性組合。 其他不變子空間：零空間、Range、Null、V。 *特徵空間與不變子空間： 特徵空間的每個向量經過線性變換後會乘上同一個倍數，而不變子空間的向量經過線性變換後，僅保證結果會是其基底的線性組合。