Author Archives: Shin

2012 「邏輯、語言與計算」暑期研習營 (FLOLAC ’12)

因為今年做的種種改變,FLOLAC 2012 的籌備比起往年慢了一些。這兩天發現已經有人在詢問了。是的,今年 FLOLAC 照常舉辦,而且將成為大學部的正式暑修課程!也因此,FLOLAC 開課時間改為暑期後半(8月27日至9月7日)而非傳統的七月。今年的國外講者是任職於 Max Planck Institute for Software Systems 的 Arthur Charguéraud, 將為我們介紹程式語言學界影響力日增的定理證明/程式驗證工具 Coq.

Posted in 活動消息 | Tagged | 1 Comment

Benoît Mandelbrot 與碎形

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

Posted in 人物 | Tagged , | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem(下)

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

Posted in 計算算計 | Tagged , | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem(中)

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

Posted in 計算算計 | Tagged , | Leave a comment

荷蘭國旗問題 The Dutch National Flag Problem(上)

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

Posted in 計算算計 | Tagged , , | 4 Comments

Milner 消失的論文

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

Posted in 人物 | Tagged , | Leave a comment

ICFP 最具影響力論文獎

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

Posted in 計算算計 | Tagged , , | 2 Comments

Noam Chomsky 來台演講

Noam Chomsky 將於八月九、十兩日分別在中央研究院、清華大學進行兩場演講。

Posted in 活動消息 | Tagged | Leave a comment

Haskell 2010 出爐

Haskell 語言的新標準 Haskell 2010 已在七月六日出爐了。

Posted in 計算算計 | Tagged , | Leave a comment

計算多項式

我有大約 25 分鐘的時間和同學們介紹函數程式演算. FLOLAC ’10 的同學少部份學過 Haskell 或其他函數語言,大部份只在一週前學了三小時的 OCaml, 寫了一些程式作業,但對 fold 之類的抽象觀念可能還難以掌握。

Posted in 計算算計 | Tagged , , , | Leave a comment