星期一, 3月 12, 2007

資料結構與演算法(下)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

張貼留言