笨事
今晚外出吃飯，回來遇大雨，與好友一同回來，我穿著雨衣騎車，好友坐我後面(未著雨衣)，我騎車騎到一半，他大叫一聲，啊，他說他有兩件輕便型雨衣在包包裡。
囧
---
聽 孫燕姿 逆光 中
星期六, 3月 24, 2007
星期五, 3月 23, 2007
所學為何？
有一天我的室友和我聊天時(我幾乎天天和我室友聊天)，我室友問起我，為什麼我肯為了念書(大部分是CLRS)而那麼衝，我不會累嗎？
Absolutely yes.
我並沒有和Josh Ko 一樣，能夠在高三到現在還是保持大概相同的想法與目標，我說過，我高三曾經念書念到壓力極大，剛好又被人發卡XD，每天一直念書一直念書，靠的就是每天聽三十分鐘的音樂(內容一定固定為F.I.R. - Fly away為開頭，中間一定有DAI - 樂園, for the future)，似乎就只是為了這些歌中的信念活下去。
到大學了，念書，有時候真的會覺得，原文書難念的跟鬼一樣，我到底是為了什麼而活下去？不為了什麼很複雜的目標，就只是想要活下去而己。
在我高一時代，我曾經花了一個晚上看完吉川英治所寫的 宮本武藏，雖然吉川英治的文筆很美麗(這當然跟譯者也有關係)，如同他所著的三國英雄傳，渲染了小說的每一個角色，把個性強化了，回到本文，宮本武藏一生的信念只有如下八個字
一切即劍，萬里一空
一直到了很多很多年以後，我才漸漸了解這兩句話的涵意，這可不是高中的時候以為這很帥，然後就一直放在msn狀態上，這對我而言是一個有趣的回憶。
宮本武藏本身對於生活的態度就是"一切即劍"，意思也很簡單，每件事物的存在都有它一定的道理，而劍道就可以從此中體會，每件事物，都有劍道的意涵(我的文化水平不高，只能做到如此解釋)，相較於佐佐木小次郎的"劍即一切"，他是用劍道來解釋一切的東西，是極為霸道的，可以得到一定的道理，但是否違背了大自然的運行？
兩個人的決鬥說明了一切。
今天的我，就是以"一切即劍"的觀點在看待Computer Science，每件事物存在都有它一定的道理，而我的基礎遠遠的不足以讓我觀察這個世界，所以我選擇繼續努力，這是我思考層面的觀點。就現實層面而言，我有很多支持我的親人與好友，這更是我要活下去的動力。
那麼為什麼我選擇了Computer Science？ 這答案或許就跟宮本武藏選擇劍道一樣，沒有太多花俏的理由，只是為了實現生活的一種方式
---
我不懂日文，但是我真的覺得DAI給人活下去的力量
星期二, 3月 20, 2007
balance
從昨天馬不停蹄的念書(假設寫隨機客的上課筆記blog也算)，昨天晚餐沒吃，今天早餐只喝牛奶，午餐麵包，由於課相當的輕鬆，還是一樣保持高度的念書熱誠，只是到下午，胃莫名奇妙的痛起來，痛到食慾不佳，這會讓我想起我在高中寫程式寫到胃痛的日子(也是一樣整天不吃)，似乎我想做事，就會比Josh還糟，連飯都不吃了XD
念書念到沒時間吃飯，好像不是理由XD
---
睡了一覺之後，只剩些微了
I2A
老酒新調，了無新意，目前自修，準備搭配OOPs上的Instruction to Algorithm Fall, 2005課程來自修，現在用Leture 1學習，效果比直接讀書來的好的多。
看到老師上課的簡報...嗯...不予置評
星期一, 3月 19, 2007
資料結構與演算法04 by 隨機客
非正題：嗯，今天是騎車去上課有史以來最塞的一次，也是我有史以來上課最認真聽的一次(拿著筆電狂打)事實上還有很多不懂的地方，寫到這裡就要很感謝，哈密瓜的討論，Josh Ko的支持與校正，隨機客上課的精采，這些都是我邊碎碎念騎車邊快樂上課的動力:)
2007/03/19 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Minimum Spanning Tree MST 和 Epilogue(時間來不及所以省略)
- Minimum Spanning Tree - Boruvka' s algorithm
此問題主在描述，在一圖形G中，每個edge都有不同的權重，找出連結所有node的最輕解(edge 的權重和相加為最小)用比較正式的描述則變成
這個問題的主要起源是Boruvka被波蘭政府委託在Bohemia這塊土地上牽電線，而讓每個城市都有線，而要怎麼樣牽電線會讓所耗費的成本為最小，就成為Minimum Spanning Tree的原始問題(yen3註：也蠻經典的XD)- Input: A connected n-node m-edge graph G with edge weight w.
- Output: A spanning tree T of G with minimum w(T).
但是先假設一個狀況，才能使用Boruvka' s algorithmWe may assume that all edge weights are distinct(yen3註：假設每一個邊的權重(重量)是不一樣的，而這樣子的假設不失一般性(JK註：不失一般性的原因，如果遇到這樣的狀況，也可以加以修改而符合假設。)
，原因是，在真實世界上，也很難找到一樣權重的路)
(JK註：假設並不會得問題的範圍變狹隘。)(相同權重的邊，稍微加一個數字造成些微的不同，雖然相同權重的邊有些許的不同，但是所算出的結果仍然一樣。)
那麼解法呢，Boruvka' s algorithm 方法如下(s.9)- 尋找每個node對外連接node的lightest incident edge加以連接
- 將已連接的connected component視為一點，尋找connected component 的 lightest incident edge再加以連接
- 集合每一個maximal subtree of F 成為一個single node(yen3註：我解釋的不好，所以照簡報)
連接每個maximal subtree為單一集合，即為答案
那麼簡單而言，讓每一個city伸出一隻手出去，往鄰邊伸出一隻手，從重量最輕的邊伸出去，如果每個ctiy都伸出最輕的手，則是Minimum spanning tree, 若無如此，，each city 都伸出lightest edge尋找spanning tree，則將connecting component縮成一個點再將已形成的spannign tree視同為一個node，再尋找每個node's lightest edge，直到連結全部node為止。
那麼演算法的效率呢，是一個expected linear time從O(m log n)一直至O(m, a(m, n))甚至optimal time(比任何已知的演算法都來的快)，但是不是真正的linear time，無人知道，在s.7中有提到基於兩種基礎所發展出來的演算法。- Unit-cost RAM Model
每一個數字用log n的數字來表示，允許任何連續O(log n) bit做加減乘除，皆可在linear time 上做到。 - Deterministic comparison based algorithms
需要把資料兩兩做比較的演算法，所以最多為O(n logn)
當然，眼尖的人會發現此slight的論文發表時間有所問題，但是不是那麼的重要，所以我們略過:)
那麼演算法的正確性呢？對於任何一點，連接此node的lightest edge
此點為週圍鄰邊最輕的，此edge必得在MST上在s.12上，紅色代表為最輕的邊，n-1個點皆在右邊，假設Red edge 不在MST上，那麼右邊為一個connected ，變成第二個點在MST上，但是權重卻比red edge重，矛盾(JK註：證明) - Minimum Spanning Tree - Kruskal' s algorithm
- 每個node自為成一個集合
- For each edge (u,v), taken in non-decreasing order by weights
if Find-set(u) ≠Find-set(v) then
(從權重最輕的邊依序處理，若兩集合不相等，則此兩邊必為相連的MST，所以印出edge(u, v)，把u, v兩個集合做一個結合成新集合)
Output edge (u,v)
Union(u,v) - Minimum Spanning Tree - Prim's algorithm
前面的方法稍微散亂，這個演算法的方法的方法蠻簡單的(JK註：要先實作priority queue，本質上和Dijkstra最短路徑演算法相同)從任一點開始，尋找權重最輕的邊，每連一個點，就視為一個connected component，縮為一個點，再尋找權重最輕的點，相連，直至連接G 上所有node為止
至於正確性呢，證法也同Boruvka' s algorithm - Advanced Topic - Expected O(m)-time comparison-base algorithm for MST [Karger-Klein-Tarjan, JACM 1995](yen3註：此處目前無人校稿，)
呃，事實上要了解並不難，但是要先了解三個特性- Cut Property - 給一個MST，任意選一edge把所有node分成兩半，任意的crossing edges，一定比剛剛切掉的edge權重來的重
- Cycle Property - 任一cycle in graph G，此cycle一定有一權重最重的edge，而此edge一定不在MST上
- Uniqueness Property - 若任一edge權重都不一樣，那麼MST只有唯一解
證明呢，我打算在下一篇blog說明，因為我認為我的思考還不夠完備，那時候寫也是不夠的XD
此外還要再說明T-heavy edges(s.40)定義為在任一spanning tree of G，必然有一邊權重為最重的edge(u, v)，那麼根據cycle property ，此edge必不在MST上所有不在MST的edge必為T heavy edge(if and only if)。
給一個spanning tree，把所有的T heave edge 丟掉，則此spanning tree必為Minimum Spanning Tree.
也因為有了這個性質，要證明一個spanning tree是不是MST是非常簡單的，在linear time即可做到(s. 44. 45)
那麼方法為The strategy: Using random sampling to further delete at least a constant factor of edges on average after each phase of edge contraction.(yen3註：這這裡不是那麼了解，課堂上的大意為random 取node，然後把T heave node刪掉，約取三次，最後會最多只剩n/3 nodes需要再做處理)
事實上為換湯不換藥的方法，採用的是disjoint-set
至於正確性的證明是和Boruvka' s algorithm 一模一樣的。但是效率會好一點，會等於O(m log m) = O(m log n)
臨時趕完有品質很差的感覺(雖然品質從來沒好過)，不過換來的是，有一個禮拜的時間可以修正和擴充
Josh Ko 於 2007/03/20 校稿
---
寫到後面有一種很累的感覺
問題
有人跟我反應上課筆記看不懂，我是沒有差啦，反正我還錯誤很多需要訂正:) 現在的確是分段寫(04已經累積至1200字左右，尚未寫完)，但是正在想會不會一篇文章太長，所以要分開po(我絕對沒有要賺篇數)，這個問題...就再說吧，目前會為了完整性一次po。
下雨
這似乎對要前往台大的我不太妙，不過已經告訴自己風雨無阻了
補記：從7:30騎車至08:50，一路塞車到台大，還好沒有下大雨:)
補記2：回來從1:30至2:10，頗為順利，公里表為7050(三個禮拜前到校為6450)
---
筆電+筆記本 = 全身行囊
星期日, 3月 18, 2007
資料結構與演算法02 by 隨機客
非正題
工院盃快結束了，我所能做的事也暫告一段落，所以我決定在下次上課前趕快把上課隨筆寫出來，不然lag到就麻煩了，也很久沒有寫blog了。
2007/03/05 資料結構與演算法(下)02 呂學一 投影片
這堂課最主要講的是Graph 圖論(The adjancency among a set of nodes)，重點落在Depth First Search DFS而今天主要著重在三個問題上，但是在進入這三個問題前，什麼是Graph?
G = (V,E) to denote that G is a graph, where V consists of the nodes of G and E consists of the nodes of G and E consists of the edges of G. (yen3註：簡而言之，一張圖G由節點V，和連接邊E所組成)，通常使用(n,m) 元素個數來代表(V,E)的集合。
而要怎麼表示一個Graph呢，最常見的有兩種方法
- adjacency matrix
一個很直覺的方法，使用一個space為O(n^2)來儲存(yen3註：很直覺存法就是使用二維陣列)，若(1,2)有所連結，則在table的(1,2)(2,1)標示為1，代表有其連結，其優點是速度快，在Insertion, Deletion, Query 都是O(1) ，缺點是，若是連接邊集中於某些點JK：若是matrix 很稀疏，意指邊很少的狀況下，則會浪費很多空間。- Adjacency list
很直覺的方法，為絕大部分Graph Algorithm所使用的Data Structure，方法是，每一個節點建立一個sortedlist(JK註，不一定為sorted，為sorted也沒什麼好處)，若和此邊有所連接，則插入(見s.8)(yen3註：在C++中，可用link list或者是STL中的vector儲存節點)，優點是節省空間，缺點是速度較慢，Insertion, Deletion 為O(1) (yen3註：O(n) 也是有可能的，端看如何設計) ，Query 為O(deg) (deg 為資料深度)， Space 為O(m) (m 為edge數)- Adjacency list with balanced search tree
方法與第二種相同，只是儲存資料時改用BST來儲存，如此在Query則會降成O(log deg)。
那麼三個問題又是什麼呢，分別如下
- Connected components
什麼是Connected components呢，定義如下Each connected component of graph G=(V,E) is maximan subset U of V such that any tow nodes in U are connected in G.(yen3註：簡而言之，在一圖型G中，尋找subgraph G 包含最多節點n)
解法，則 - Topological sort(拓撲排序)
首先，Topological sort是使用在directed graph上，這時候又會牽扯到DAG(directed acyclic graph - a directed graph that does not contain any cycle.(yen3註：簡而言之，不會有任任何成為cycle的node，就是不能從A node出發再回到A node))，其example在s.30，其pesudo code在綠色字處，加入計算每個節點被拜訪到的先後順序(yen3註：上課時沒有證明，不過用實例跑過一次，確實相同)，而，在把答案output時，將t從大到小輸出，原因也蠻直觀的，因為排序最後的節點，是會最先被參觀到的，而排序最前的節點，由於並無人指向，所以是最後被參觀到的，所以一個圖G，並不一定只有一組解，可能會有好幾組解(yen3註：原因，我好難解釋Orz)。證明從s.35開始 - Strongly Connected components
定義如下Each strongly connetced component of graph G= (V,E) is a max imal subset U of V such that any two nodes in U are reachable(through directed paths) from each ohter in G.(yen3註：在directed graph中，尋找max cycle的subgraph)
演算法的方法也很簡單，步驟如下- 用
Topological sortDFS讓每個node有一順序 - 將圖上的directed edge全部反向
- 再跑一次
Topological sortDFS(根據第一次跑出來的Topological sort list來執行)，每一個list代表一個答案
那麼為什麼這樣子的演算法可以成立，隨機客使用了非常直觀的證明方法而避免掉課本一拖拉庫的證明(s.49, 50)(yen3註：時間太久，我竟然忘了XD)。 - 用
請盡量指教，謝謝:)
(Josh Ko：正確性的證明需提一下，至少命題要寫)
(yen3：下次把一篇拆成好幾天寫就有機會，感謝指正)
---
下次要早點寫，而且分好幾天寫....好累
訂閱：
文章 (Atom)