Saturday, December 24, 2005

Randomized algorithms and randomized life?


在看了一篇關於 randomized algorithm 的 paper 以後,總算利用 group meeting 的時間跟大家做了一次詳盡的報告。我的目的是想引發大家對這方面 topics 的興趣,希望老闆也能跟著投入這領域的研究。而目前看來效果還算不錯。

國內做這領域的學者不多,而且要上手的門檻高得多,加上我對於隨機的概念掌握度還不是甚高,因此常有霧裡看花的感覺。目前我的計畫是先從基本的機率與統計的書籍著手,先對機率統計有一點感覺,還有閱讀相關的 papers 以及 那本 randomized algorithms 的教科書。進度?當然愈快愈好,因為明年老闆要我試著提一個國科會計畫,而且我得把一些概念跟老闆分享討論,老闆才能真正一起投入這領域的研究。

令我吃驚的是,原本對隨機演算法嗤之以鼻的老師們,現在卻對它有高度的興趣。Knuth 就曾經表示隨機演算法是很重要的。

只是說…我畢業的時間說不定也帶著相當高的隨機度了。

目前待解的問題:

  • 由隨機抽樣的一些點中取 average degree 與原圖的 average degree 差異和相關機率的關連?

  • sublinear time algorithms 所花的時間事實上是否為 "expected running time"?

  • 假設現在每次執行的 input 都不一樣(這假設是十分合理的),而 randomized algorithm 每次回答的答案也不盡相同,假設它能回答一個 expected answer,那麼對多個 inputs 多次執行這 randomized algorithm 的 expected answer 又是怎麼樣的一個值?

以上這些問題都尚待釐清當中。


CCLin

1 comment:

Joseph, Chuang-Chieh Lin said...

目前這三個問題已解,也寫進了我的weekly reports裡。

C. C. Lin