Creative Approach 有什麼不同 (2) – 談談數學歸納法

數學歸納法,不是哲學上所講的歸納推理( inductive reasoning) ,反而比較接近哲學領域所講的演繹 (deduction)推理。所謂的歸納推理,是基於對特定目標觀察的結果,把「性質」或「關係」類推至類型,或者是基於對反覆現象的觀察,所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真,但不代表一定為真。

Creative Approach 有什麼不同

為了準備資格考,在圖書館借了 Introduction to Algorithms: A Creative Approach 的中譯本(沒法子,找不到原版),實驗室的同學翻了翻,覺得這本書一點兒都不出奇,和別的演算法書籍沒有什麼不同,尤其和這些年被奉為聖經的 CLRS 演算法大磚頭相比,相形下有點單薄了。 的確,中文書名建構式演算法,實在不怎麼響亮,而且在建構式數學已經被污名化的今日,這樣的書名實在是讓人很難不看低這本書。 但是在我的眼裡,這本書不同的地方可多著咧。 首先,作者的來頭不一般,這本書的作者 Udi Manber 可不是蛋頭型的學者,他不僅在學術上的成就卓著,是演算法界大師級的學者,他還是一個活力十足的行動派。 Udi Manber 是agrep 和 GLIMPSE 的(共同)作者。agrep 是他和吳昇(他的著作)老師在九零年代初共同發展的,他們共同寫作的 Agrep – A Fast Approximate Pattern-Matching Tool,依照 Google Scholar 的搜尋結果,被引用次數達到 143 次,以一篇年紀這麼大的文章,被引用次數達到這個程度,是很不容易的。簡單說,他是搜尋引擎相關技術演算法的先驅者之一。 離開學界,進入產業界,他也是一條過江猛龍。1998 年,他加入雅虎,職位是 chief scientist ;2002 年,他加入亞瑪遜網路書店,擔任 chief algorithms officer,這個 CAO 職位,還引起 IT 媒體界一陣騷動,紛紛評論這個職位對於企業的意義和影響(impact)。在 Amazon 期間,他還是搜尋引擎 A9 的 CEO。後來,毫不令人意外地,他在 2006 年加入了…

Hat Problem: why you should care ?

這是一篇舊聞了,是紐約時報 2001年4月10日,科學版上的一篇文章。但是剛在 Digg 上發現,看到有超過七百人次「頂」這篇 Why Mathematicians Now Care About Their Hat Color,連上紐約時報仔細拜讀,才真正認識了這個不簡單的策略遊戲。 遊戲規則 數學界一般認為猜帽子顏色的遊戲是由 Dr. Todd Ebert (DBLP)在1998年,他的博士論文中提出來的。 這是一個團隊參與的遊戲,參與人數從三人到更多人都可以,遊戲的勝負是以整個團隊的結果來決定結果。在遊戲過程中,參與者每人頭上都戴著紅色或藍色的帽子,參與者只能看到別人的帽子顏色,但是不能看到自己的帽子顏色。每個參與者必須猜測自己頭上帽子的顏色,參與者之間不能有任何形式的溝通,只能觀察別人的帽子,然後猜測自己的頭頂是什麼顏色。 猜測的選項有三個,紅色、藍色或棄權(pass),如果覺得自己無法下決定,可以選擇 PASS。當參與團隊中每個有作出猜測的人(棄權的人就不管了)的猜測結果都正確,則這個團體可以獲得獎金。 依照遊戲規則,在觀察和猜測時,遊戲玩家間不得有任何溝通行為,但是在遊戲開始前,這個團隊可以作「策略」討論,遊戲開始後,所有成員根據大家事先協商的策略,來決定自己的行動(猜測或放棄)。這個遊戲的核心就是 :有沒有一個「贏的策略」?這個策略的成功機率有多高? 三個人的策略 以最簡單的三人情況來說,三個人都是紅色或藍色的機率各是八分之一,所以有四分之三(扣掉全藍及全紅的情況)的機會,是兩個人的帽子顏色相同,第三個人是另外一種顏色。因此有個可能比較容易贏的策略,每個參與者觀察另外兩個人的帽子顏色,如果這兩個人的帽子顏色不同,則猜測者選擇放棄;如果另兩個人的帽子顏色相同,猜測者猜自己的帽子是另外一種顏色。 雖然當三個人的帽子顏色相同時,以上辦法是絕對沒有機會贏的, 不過這是參與者數目為三人的最佳解決方案(optimal solution),以下是從網路上找到的證明。 Each guess has a 50-50 chance of being correct. This means that when we consider possible outcomes there must be an equal number of correct and incorrect…