Category Archives: 計算算計

Benoît Mandelbrot 與碎形

By Shin | Published: 十月 21, 2010

雲、山、海岸線、閃電等都是自然界可看到的碎型，複雜而不規則。然而這是自然之所以美的原因。如果雲是圓形的，那多無聊。而如果數學不能捕捉自然之美，那是多麼可惜的事情。碎型理論揭去了這層神秘的面紗，告訴我們，這些自然事物的「規則」其實隱藏在另一個維度中。

Also posted in 人物 | Tagged 歷史, 碎形 | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem（下）

By Shin | Published: 十月 18, 2010

為什麼這麼慢呢？Bentley 和 McIlroy 認為問題出在我們花了太多工夫把兩個白色元素一步步挪到中間。與其如此，不如先把白色元素放到兩邊去，把陣列排成「白、紅、藍、白」。等排序完成，再把白色換回中間就可以了！

Posted in 計算算計 | Tagged Hoare 邏輯, 荷蘭國旗問題 | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem（中）

By Shin | Published: 十月 16, 2010

這是一個 O(N-M) 的程式。如果三色數量相同，我們平均需要大約 2(N-M)/3 次交換。如果我們當初選擇從檢查 a[b-1] 開始，平均需要的交換次數則是 N-M 次。

Posted in 計算算計 | Tagged Hoare 邏輯, 荷蘭國旗問題 | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem（上）

By Shin | Published: 十月 15, 2010

陣列裡頭每個元素都是紅、白、藍三色之一。如何把它們由左至右依紅、白、藍的順序排好呢？Dijkstra 希望採用三向分割法後能更容易表達紅（小於 pivot）和藍色（大於 pivot）的區塊絕對比原陣列短的性質。然而，在 Peter 的印象中 Dijkstra 從沒把這層考量寫下來。「我們如果不告訴學生，以後就沒人知道了呢！」他說。

Posted in 計算算計 | Tagged Edsger Dijkstra, Hoare 邏輯, 荷蘭國旗問題 | 3 Comments

Milner 消失的論文

By Shin | Published: 十月 15, 2010

令 Gordon 感興趣的是，稿子上方手寫著「投稿給 JACM, 1971 年九月」。但大家知道這篇論文一直都是技術報告。難道 JACM 把它退件了嗎？

Also posted in 人物 | Tagged Robin Milner, 歷史 | Leave a comment

ICFP 最具影響力論文獎

By Shin | Published: 十月 13, 2010

從 2006 年開始，每次的 International Conference on Functional Programming (ICFP) 回顧十年前發表的論文，看看哪篇最經得起歲月的考驗，在十年中發揮了最大的影響力。ICFP 2010 剛在上個月底落幕，而這是 ICFP 2000 的論文列表。如果您是評審，會頒獎給誰呢？