發現

真的要寫一份說明document的話，用字要嚴謹，這好像不是現在的我所能辦到的，不過願盡力一試，當然，排版要有一定的乾淨程度，這是一必然要求，SIC已經完成，SIC/ XE，我想我會照我自己的意思來寫

才能?

才能能當飯吃之外還能做什麼？

當水喝XD

---
為什麼我早起就要那麼冷Orz

資料結構與演算法(下)05 by 隨機客

非正題：今天上課算是比較輕鬆的一次(是進入狀況還是課比較好懂呢?我也不知道XD)，上課還被隨機客詢問(當然，我答不出來XD)，興起了換位子的念頭XD

---

2007/03/26 資料結構與演算法(下) 呂學一 投影片
今天上課的主題是Shortest-Path Tree Algorithm, 主要分有Bellman-Ford, Dijkstra Algorithm

在進入Algorithm前，先行討論此問題的背景

• The setting
  
  • The graph G = (V, E) is directed with edge length w. (此圖必需是個有權重的有向圖)
  • The length of each edge could be negative. (允許圖上的edge 為 negative)
  
  


• The problem
  
  • Input: A directed Graph G=(V, E) with weight edge w.
    A node r of G
  • Output: A tree T rooted at r such that the path of T from r to each node u of T is a shortest path from r to u in G.(yen3註：一個root 為r 的shortest path tree.)
  
  


• We may assume that each node in the graph is reachable from r.(yen3註：假設r 可以到達每個node)
  那麼在Graph中，有unreachable node，則一開始則remove掉，而不失一般性(Without loss of generality)，為什麼呢？
  尋找對r所有的unreachable node只需要花linear time，用DFS(depth First Search)從r開始，把所經過的點編號，而沒有被編號到的node就是unreachable node，而執行DFS只需要linear time，故此假設不失一般性


• Can a shortest path between node u and v contain a cycle? (是否會有cycle在shortest path tree上呢?)
  答案是否，我們把cycle weight sum分成三種狀況
  • cycle weight sum is positive: 此狀況不可能發生，因為這一定不是shortest path，因為一定不會通過，因為把此cycle 拿掉則path會更短
  • cycle weight sum is negative: u到v根本沒有shortest path，繞了n圈為最短，則繞了n+1圈會更短，則繞不完，所以有negative cycle weight的Graph, 則shortest path 不存在(這是一個if and only if)
  • cycle weight sum is 0: 則不會通過，就沒有cycle，這樣子可把cycle做一個remove的動作，使其cycle不在shortest path上


• Single-source shortest-path problem
  在此問題上為single path，但是與一般的path定義不同，一般的path定義為該node通過後則不能再通過，但是在此，我們比較確切關心edge weight sum


• Such a shortest-path tree always exists? 不一定，原因如上
  若r至任何一點u，都是reachable，就找所有可以走到的方法，事實上有可能是無限條，但是限制在G has no negative edge 和remove unreachable node 和 only think about single path ，則shortest path 則會變成有限條


• The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. (尋找shortest distance和shortest path 是等價的問題)
  何謂等價的問題，若A和B是等價的問題，則找到A的答案之後，我們可以在linear time 找到B的答案，且找到B的答案之後，也可以在linear time 找到A的答案
  那麼為什麼shortest distance 和 shortest path是等價的問題？若已知shortest path，則把edge weight求其和即為distance，可在linear time 找到，若是shortest distance呢？從r到v的點，我們從v點找起，把指向v點的edge weight掃描一次，若剛好等於，則是shortest path 的一個解，若小於此weight，則扣掉該重量，進行recursion，由於只有m個邊，我們可以保證在linear time 找到


• 補充說明：在演算法上所定義的linear time並不是指O(n)，而是指執行效率相對於input size，若input size 為O(n^2)，而RunTime也是O(n^2)，則我們說該演算法是linear time

終於可以描述演算法嘍XD

• Bellman-Ford Algorithm
  此演算法的方式如下
  
  • 設一個array d[u]為從r 到u的距離
  • 對其array做初始化的動作
    • Let d[u] = infinty for each node u of G
    • let d[r]=0(自己到自己距離為0)
  • Repeat improve對於d[u] for d(u)的估算
  
  而Relaxing edge(u,v)為

      If d[v] > d[u]+w(u,v) then
          let d[v] = d[u] + w(u,v)

  那何謂A phase of improvement

      For each edge(u, v) of G do
          relax edge(u, v)

  問題又來了，試問phase of improvement 要跑幾次才能確保答案的正確呢？
  如果node為n個，則跑n-1次就可確保答案正確性，每當我們跑了phase of improvement，則會有一點被改善(yen3註：竟然不會證Orz)
  那麼效率呢，由於有n個node，m個edge，每個點皆跑m個edge，所以Time Complexity = O(mn)
  
  第二個問題是，若圖中有negative cycle，則我們要怎麼得知？
  問題也很簡單，已知演算跑n-1次已經得解，若跑了第n個phase 而仍然有d[u]被改變的情形，則知道與原先預想的不合，此圖有negative cycle
  為什麼？在s.31說明(yen3註：證明竟然忘了...真神Orz)
  
  若該Graph 為一個 Directed Acyclic Graph DAG呢? 方法如下
  

  • 先對該DAG做topological sort
  • 根據topological sort 的順序，由小到大(slight 上寫由for 1 to n)做relaxing動作

  其Running Time 是 O(m+n)


• Dijkstra Algorithm
  
  (題外話：Edsger W. Dijkstra 是提出“Goto is considered harmful.”的人)(yen3註：此話真的是powerful，對於現在學assembly language的我而言更是一個有趣的問題。)
  
  此演算法是一個極具powerful的演算法，此演算法求shortest path是建立在無non-negative weight edge, non-negative-cycle的DAG上，方法如下(此方法不用依靠topological sort做前置作業)
  

  • 做與Bellman-Ford Algorithm同樣的初始化動作(與對其array做初始化的動作相同)
  • 每一個iteration中，尋找unprocessed node中，尋找到目前為止smallest path做relaxing，直到每一點都做完為止(換句話說，在所有未處理的點找到該點花費最少的來做處理)

  
  此方法的正確性呢?由s.50得知。假設u是unprocessed minimal node，而在處理到u node時出錯了，而y node 與processed node 的範圍只用一條edge連結，所以我們確信d[y] = d(y)，但是我們又說u是unprocessed minimal node，而用y連過去則會讓d[u] > d(u) >=d(y) = d[y] 矛盾(yen3註：證的真爛Orz)
  
  則Running Time用 Naïve implementation: O(n2 + m).
  With Fibonacci heap: O(n log n + m).

---

---
聽Josh Ko說明才得知簡報上的數學式是用TeX4PPT做的，來找找做個介紹

塞車

騎摩拖車遇到塞車算是很大的難題之一，雖然演算法學的是圖論，但是關係不大XD 唯一的關係，你得避開車潮，今日六點半起床(上大學以來最早)，七點出發...還是躲不了塞車的惡夢，下禮拜決定六點起來好了

---
再塞我前天就睡台大(會不會有兩個人做惡夢XD)

XD

家樂福的XD
家福福的XD2

---
是男人就該逛家樂福

笨事

今晚外出吃飯，回來遇大雨，與好友一同回來，我穿著雨衣騎車，好友坐我後面(未著雨衣)，我騎車騎到一半，他大叫一聲，啊，他說他有兩件輕便型雨衣在包包裡。

囧

---
聽 孫燕姿 逆光 中

所學為何？

有一天我的室友和我聊天時(我幾乎天天和我室友聊天)，我室友問起我，為什麼我肯為了念書(大部分是CLRS)而那麼衝，我不會累嗎？

Absolutely yes.

我並沒有和Josh Ko 一樣，能夠在高三到現在還是保持大概相同的想法與目標，我說過，我高三曾經念書念到壓力極大，剛好又被人發卡XD，每天一直念書一直念書，靠的就是每天聽三十分鐘的音樂(內容一定固定為F.I.R. - Fly away為開頭，中間一定有DAI - 樂園, for the future)，似乎就只是為了這些歌中的信念活下去。

到大學了，念書，有時候真的會覺得，原文書難念的跟鬼一樣，我到底是為了什麼而活下去？不為了什麼很複雜的目標，就只是想要活下去而己。

在我高一時代，我曾經花了一個晚上看完吉川英治所寫的 宮本武藏，雖然吉川英治的文筆很美麗(這當然跟譯者也有關係)，如同他所著的三國英雄傳，渲染了小說的每一個角色，把個性強化了，回到本文，宮本武藏一生的信念只有如下八個字

一切即劍，萬里一空

一直到了很多很多年以後，我才漸漸了解這兩句話的涵意，這可不是高中的時候以為這很帥，然後就一直放在msn狀態上，這對我而言是一個有趣的回憶。

宮本武藏本身對於生活的態度就是"一切即劍"，意思也很簡單，每件事物的存在都有它一定的道理，而劍道就可以從此中體會，每件事物，都有劍道的意涵(我的文化水平不高，只能做到如此解釋)，相較於佐佐木小次郎的"劍即一切"，他是用劍道來解釋一切的東西，是極為霸道的，可以得到一定的道理，但是否違背了大自然的運行？

兩個人的決鬥說明了一切。

今天的我，就是以"一切即劍"的觀點在看待Computer Science，每件事物存在都有它一定的道理，而我的基礎遠遠的不足以讓我觀察這個世界，所以我選擇繼續努力，這是我思考層面的觀點。就現實層面而言，我有很多支持我的親人與好友，這更是我要活下去的動力。

那麼為什麼我選擇了Computer Science？ 這答案或許就跟宮本武藏選擇劍道一樣，沒有太多花俏的理由，只是為了實現生活的一種方式

---
我不懂日文，但是我真的覺得DAI給人活下去的力量

記錄

記錄一：已經校稿的成果拖了三天，我對不起Josh..Orz
記錄二：為了VHDL從九點畫到四點
記錄三：7個人去家樂福買了約4300元

balance

從昨天馬不停蹄的念書(假設寫隨機客的上課筆記blog也算)，昨天晚餐沒吃，今天早餐只喝牛奶，午餐麵包，由於課相當的輕鬆，還是一樣保持高度的念書熱誠，只是到下午，胃莫名奇妙的痛起來，痛到食慾不佳，這會讓我想起我在高中寫程式寫到胃痛的日子(也是一樣整天不吃)，似乎我想做事，就會比Josh還糟，連飯都不吃了XD

念書念到沒時間吃飯，好像不是理由XD

---
睡了一覺之後，只剩些微了

I2A

老酒新調，了無新意，目前自修，準備搭配OOPs上的Instruction to Algorithm Fall, 2005課程來自修，現在用Leture 1學習，效果比直接讀書來的好的多。

看到老師上課的簡報...嗯...不予置評

噁心？

efang說"資料結構與演算法0x by 隨機客" 看起來有很噁心的感覺，我看起來覺得還好啊....可能最近傾向寫這些東西吧。本來想寫有關"浮華"的文章，總覺得怎麼寫都不怎麼順手，Josh Ko 已用魔術師的禮帽述說的非常完備，所以我也不多做廢話。

事實上寫了那麼多，只會感覺到自己的基礎深深的不足，遇到證明無從著力，真的要再加油

下期預告：SIC (Simplified Instructional Comptuer), SIC/XE (extra equipment)簡介

資料結構與演算法04 by 隨機客

非正題：嗯，今天是騎車去上課有史以來最塞的一次，也是我有史以來上課最認真聽的一次(拿著筆電狂打)事實上還有很多不懂的地方，寫到這裡就要很感謝，哈密瓜的討論，Josh Ko的支持與校正，隨機客上課的精采，這些都是我邊碎碎念騎車邊快樂上課的動力:)

---

2007/03/19 資料結構與演算法(下) 呂學一 投影片

今天上課的主題是Minimum Spanning Tree MST 和 Epilogue(時間來不及所以省略)

• Minimum Spanning Tree - Boruvka' s algorithm
  此問題主在描述，在一圖形G中，每個edge都有不同的權重，找出連結所有node的最輕解(edge 的權重和相加為最小)用比較正式的描述則變成
  

  • 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被波蘭政府委託在Bohemia這塊土地上牽電線，而讓每個城市都有線，而要怎麼樣牽電線會讓所耗費的成本為最小，就成為Minimum Spanning Tree的原始問題(yen3註：也蠻經典的XD)
  
  但是先假設一個狀況，才能使用Boruvka' s algorithm

  We may assume that all edge weights are distinct(yen3註：假設每一個邊的權重(重量)是不一樣的，而這樣子的假設不失一般性(JK註：不失一般性的原因，如果遇到這樣的狀況，也可以加以修改而符合假設。)，原因是，在真實世界上，也很難找到一樣權重的路)
  (JK註：假設並不會得問題的範圍變狹隘。)(相同權重的邊，稍微加一個數字造成些微的不同，雖然相同權重的邊有些許的不同，但是所算出的結果仍然一樣。)

  
  那麼解法呢，Boruvka' s algorithm 方法如下(s.9)
  
  1. 尋找每個node對外連接node的lightest incident edge加以連接
  2. 將已連接的connected component視為一點，尋找connected component 的 lightest incident edge再加以連接
  3. 集合每一個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

事實上為換湯不換藥的方法，採用的是disjoint-set方法的資料結構，方法比較簡單(JK註：Disjoint set的實作比較簡單)(s.14)

1. 每個node自為成一個集合
2. For each edge (u,v), taken in non-decreasing order by weights

   if Find-set(u) ≠Find-set(v) then
   Output edge (u,v)
   Union(u,v)

   (從權重最輕的邊依序處理，若兩集合不相等，則此兩邊必為相連的MST，所以印出edge(u, v)，把u, v兩個集合做一個結合成新集合)

至於正確性的證明是和Boruvka' s algorithm 一模一樣的。但是效率會好一點，會等於O(m log m) = O(m log n)


• 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需要再做處理)

---

臨時趕完有品質很差的感覺(雖然品質從來沒好過)，不過換來的是，有一個禮拜的時間可以修正和擴充


Josh Ko 於 2007/03/20 校稿
---
寫到後面有一種很累的感覺

問題

有人跟我反應上課筆記看不懂，我是沒有差啦，反正我還錯誤很多需要訂正:) 現在的確是分段寫(04已經累積至1200字左右，尚未寫完)，但是正在想會不會一篇文章太長，所以要分開po(我絕對沒有要賺篇數)，這個問題...就再說吧，目前會為了完整性一次po。

下雨

這似乎對要前往台大的我不太妙，不過已經告訴自己風雨無阻了

補記：從7:30騎車至08:50，一路塞車到台大，還好沒有下大雨:)
補記2：回來從1:30至2:10，頗為順利，公里表為7050(三個禮拜前到校為6450)
---
筆電+筆記本 = 全身行囊

資料結構與演算法03 by 隨機客

老師帶領學生去東京比賽，停課一次XD

資料結構與演算法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，方法是，每一個節點建立一個sorted list(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)

  
  
解法，則使用(JK註：因為disjoint sets無法在linear time解決，所以才使用DFS)了disjoint sets的概念(s.18)，而pseudo code在s.23，至於使用DFS是否為linear time? 見我們需見到subroutine visit中的for loop，此處證明為O(m+n)(yen3註：太晚寫筆記，我忘了怎麼證了Orz)。中間插話，上帝有一本美麗的數學證明本(s.25)XD


• 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)

  
  演算法的方法也很簡單，步驟如下
  

  1. 用Topological sortDFS讓每個node有一順序
  2. 將圖上的directed edge全部反向
  3. 再跑一次Topological sortDFS(根據第一次跑出來的Topological sort list來執行)，每一個list代表一個答案

  
  那麼為什麼這樣子的演算法可以成立，隨機客使用了非常直觀的證明方法而避免掉課本一拖拉庫的證明(s.49, 50)(yen3註：時間太久，我竟然忘了XD)。
  

---

請盡量指教，謝謝:)

(Josh Ko：正確性的證明需提一下，至少命題要寫)
(yen3：下次把一篇拆成好幾天寫就有機會，感謝指正)
---
下次要早點寫，而且分好幾天寫....好累

BST

Basic Binary Search Tree 大致上已經建構完成(basic的原因，不具備balanced的功能XD)，花了很長的時間在寫ctor, dtor, copy ctor, operator=，不過整個class的效率不佳(基本上都以recursion建成，以後可以思考拆掉)，程式碼目前只有330行，算很小，就算在insert node的這個功能上加入balanced，我相信也不會大到那裡去~

---
AVL Tree建完回頭建link list..XD

沒時間

第一次覺得沒時間可以用，利用自身的筆電優勢，大概把BinarySearchTree寫完了，327行，尚未整理，一整個很有dirty work的感覺，晚上要當工院盃場務，回到宿舍已無體力繼續，印出來之後，完成一個AVL Tree or RB Tree指日可待

事實上沒時間最可惜的是，要寫"資料結構與演算法02" 一直找不到時間XD

---
沒時間(Sun yanzi, Start自選輯)

最近

發現要念書時間不夠用，對於利用電腦整理重點更有心得，但是總覺得有一種被制約的感覺。有人問我"一把鍵盤改變全世界"(msn狀態)是什麼意思，我很高興的說的，因為資工人就利用鍵盤所輸入的文字在改變世界，但是轉眼一想，我們不就受限於簡單的鍵盤上嘍，但是相較而言，用簡單的鍵盤創造無限可能，這或許就跟用鋼琴，就幾十個黑鍵白鍵，譜出全世界最美麗的樂章，有一樣的感覺

---
但是我想要成為資工人，而不能成為鋼琴家XD

資料結構與演算法(下)01 by 隨機客

非正題
當初一時高興之下決定每個禮拜前往台大旁聽的決定，現在已經是第三個禮拜，想想也是覺得複雜了些(早上七點起來+來回60km機車)，但是現在想想，上這堂課是蠻值得的，一直都很想為這堂課寫一些blog note，但是，呃，苦無時間，原因很多，所以且戰且走吧:)，這還是我蠻常說的一句話。

---

2007/02/26 資料結構與演算法(下) 呂學一 投影片

這堂課主要講述的是隨機演算法(yen3註：跟隨機客有異曲同工之妙XD)，主要著重於兩個重點

• Randomized quick sort

sorting 乃萬古常青的演算法問題，quick sort更是在1960年代時被提出，在投影片的一開始複習quick sort的特性(標準的divide and conquer)與algorithm的運作方式(yen3補註：這中間有非常的漂亮動畫說明，考據指出，只用了powerpoint的內建功能)。

quick sort的時間最佳為O(n logn)，最糟為O(n^2)，這中間的效率在於pivot的選取，重點來了，怎麼選？當然，一般化的想法，選中位數，中位數的選取幾乎可以獨立成為一個演算法的課題(在簡報中提到許多paper都在選中位數，而這篇關鍵性的paper author幾乎都得了Turing Award XD)，證明出選中位數是linear time，於是隨機客在這邊丟出一個問題，是否在做quick sort的選取pivot時，一定要用到如此複雜的選中位數呢？

當然有其他解法，Randomized 選取pivot是一個解，隨機演算法本身的撰寫無難度可言，難的是，如何得知效率(time and space complexity)？亂數是否真的夠亂(yen3註：C library 下的rand() 是個眾所皆知的假隨機亂數)，經過證明，經過隨機選取的亂數當pivot，有一半的機率會達到最佳效率，也可以證明出O(n logn) 是成立的(隨機客將中間證明省略)


• Randomized maximum cut

掃黑的藝術(yen3註：XD)
給一個圖G，找出從A node 至B node能夠將最多edge切掉，但是也有一個問題，each node no more than 3 neighbors. 問題規定如題，求出最大切割的time complexity 也是O(c^n) c為constant ，n 為節點數...如果n 非常大，此題接近無解

Approximation Algorithms(近似演算法)現身啦，噹噹噹(近似演算法的哲學：放下對完全的堅持，往往就可以找到新的出路。知所進退，則近道矣。)在此問題上，使用隨機演算法選取node進行切割，則有機率是最佳解的一半(但是時間就是生出亂數的時間XD)，隨機近似演算法就變成一個很好的解法(yen3註：後面看不太懂，要再念書。)

對隨機演算法不要有一個誤解，無論input data為何，都不影響其效率，也就是說，對於best case和wroest case，隨機演算法皆保有同一個效率，並不因input改變，因此，沒有必要對所有可能的input 算出每一個時間複雜度，若是這樣子，此隨機演算法不成立。當然，隨機演算法也有其罩門，這世界上是否真的有亂數產生器？(Pseudo-random generator exists if and only if one-way function exists.)到目前為止沒有人知道有沒有，因為事實上證明出現有的亂數產生器都是有跡可循的，若是用C library 上的rand() ，照著一定公式所產生的亂數，也有演算法可以很大的機率猜出下一個會出現的數字是什麼(以bit的觀點)。在這也提到了P vs NP problem (列入Hilbert's 23 open questions)。

亂數沒有那麼好產生，也早就有人證明出依照現在所存的方法，所產生的亂數都是假隨機亂數(也就是有跡可循的亂數)，要能夠產生真正夠亂的亂數依舊是一個難題，世界上沒有一個公平的硬幣，所以就有了一個題外話的數學小證明，號稱20世紀最聰明的人von Neumann，提出了丟硬幣的方法(見投影片p.38)。用了簡單的機率，即得證。

---

有錯誤請盡量指正，謝謝:)

---
寫的好長好亂，下次我是不是該改成wiki..XD