隨機演算法

Prof. Michael Mitzenmacher的女兒(?)

[隨機演算法]

傳統演算法的設計著重於 deterministic 程序, 亦即當演算法的程序及輸入固定時, 輸出的產生是一個 deterministic 的過程. 隨機演算法的重點在於輸出的產生是一個隨機 (randomized) 的過程, 亦即同樣的程序及輸入並不保證同樣的輸出. 隨機演算法適合於經由數學驗證最佳解無法迅速取得的問題(如NP-complete problem), 或是找尋解之計算時間考量遠大於解的品質 (如路由方法), 隨機演算法可保證快速求解, 同時所得解的有效程度為一可接受的機率分布, 意即產生不良解的機率極小, 幾乎不會發生.


最近再修一門課有用到這本text book:

Probability and Computing, Randomized algorithms and probabilistic analysis
( by Mitzenmacher and Upfal, 2005. )

習題夭壽多，不過很多都很不賴，聽說有個大陸人花了五年把全部解完，但聽說終究是聽說，就像我當初剛進陽明也聽說過唯任很花的傳言(by某仁)，但歷史證明我們的班長唯任是怕老婆專情的。總而言之，我覺得這本書不錯，但我的能力跟時間有限，雖然這邊也有讀書會再讀這本書，但我想如果有更多人可以討論那是更好的，推薦給大家！

(合理期望有天可以靠msn跟各位求救這本書的疑問然後馬上得到解答)