simulation
陽春召我以煙景,大塊假我以文章。《李白.春夜宴桃李園序》
simulation
撰寫程式,模擬行為。沒有前例,那就創例。
範例:印出直角三角形
不加思索,窮舉試誤。
modeling
前事之不忘,後事之師。《戰國策》
modeling
把問題對應到耳熟能詳的模型,套用既有模型解決新問題。
範例:平行四邊形面積
小學數學老師教過:長方形的面積是「長乘寬」。儘管不知道原因,不過這個公式肯定是正確的。那麼,請問平行四邊形面積如何計算?
把平行四邊形凸出的三角形切下來,補在另一邊,平行四邊形就變成了長方形。想要計算平行四邊形面積,可以直接套用長方形面積公式。
平行四邊形的底,就是長方形的長;平行四邊形的高,就是長方形的寬。平行四邊形的元件,一一對應到長方形。
範例:約瑟夫問題(Josephus problem)
8個人圍成一圈,現在從第一個人開始報數,數到第5人時,就殺死這第5人;然後從被殺的下一位繼續重新報數,數到第5人時,就殺死這第5人。如此不斷數5人、殺此人,直到最後會剩下一個人,請問他是誰?
數人和殺人的動作可以對應到佇列(queue)的操作。首先把每個人依序塞入佇列,接著連續pop和push 4人,接著pop第5人時,不要將他塞回佇列裡面即可!
範例:用圖論作為模型,模擬小畫家倒墨水。
以圖論的觀點來看,flood fill algorithm其實就是運用depth-first search找到connected component。
範例:system of difference constraints in linear programming
問題:給定變數x₁到xɴ,並給定一些xᵢ-xⱼ≤c的式子,作為條件限制。請判斷有沒有解,如果有解就求出其中一組解。
這個問題可以巧妙的轉換成最短路徑問題。x₁到xɴ看作是圖上的N個點,一道xᵢ-xⱼ≤c的限制式子看作是一條xⱼ到xᵢ的邊,其權重是c。
如果無解,那麼圖上有負環。如果有解,那麼圖上各點的最短路徑長度就是其中一組解。為了讓圖上各點都有最短路徑長度值,可參考Johnson's algorithm的做法。
UVa 515 ICPC 2058
範例:sentiment relation in social balance theory
從前有一位心理學者認為,人與人之間的關係,可以粗略分為兩種:互相喜歡、互相討厭。這種關係稱作sentiment relation,是一種雙向關係,而且擁有喜歡與討厭兩種類型。假使兩人之間好惡分明,沒有亦敵亦友的情況,就會形成sentiment relation。
like hate A<------>B A<------>B
另外sentiment relation還具有相當特殊的性質,有點像是transitivity、symmetry、antisymmetry的總合。這種性質的最佳寫照,諸如同仇敵愾、合縱連橫等等,翻成白話就是這樣:
1. 朋友的朋友就是我的朋友。 2. 朋友的敵人就是我的敵人。 3. 敵人的朋友就是我的敵人。 4. 敵人的敵人就是我的朋友。
在sentiment relation所形成的社交結構當中,如果產生了好與惡的矛盾,那麼這樣的社交結構就是不平衡的;如果好與惡合理,那麼這樣的社交結構就是平衡的。心理學者相信,當社交結構不平衡的時候,個體會嘗試改變自己的觀點,讓社交結構趨向平衡。
balance: A A like like like / \ like hate / \ hate ----A---- / \ / \ / ha|te \ B-----C B-----C B-----C-----D like like hate hate imbalance: A A like like hate / \ hate like / \ like ----A---- / \ / \ / ha|te \ B-----C B-----C B-----C-----D hate hate like like
後來心理學者進一步發現,當社交結構達到平衡,所有人可以分成兩大陣營,使得陣營內部的關係都是互相喜歡,陣營與陣營之間的關係都是互相討厭。
說了這麼多終於要提到重點。現在問題來了,假設社交結構是平衡的,而我們也知道一些兩兩相互喜歡、相互討厭的資訊時,我們該如何確認誰在同一陣營、誰在不同陣營呢?
一、以bipartite graph作為模型:
把社交結構看作是bipartite graph,bipartite graph的兩側分別是兩大陣營。首先利用graph traversal走訪喜歡的邊,找出所有連通分量,並各自縮成一點。然後再度利用graph traversal走訪討厭的邊,嘗試建立bipartite graph,如果無法建立則表示社交結構不平衡。
二、以disjoint sets作為模型:
當x與y是朋友: x及朋友、y及朋友,都是好朋友。 x的敵人、y的敵人,都是好朋友。 當x與y是敵人: x及朋友、y的敵人,都是好朋友。 x的敵人、y及朋友,都是好朋友。
把陣營看作是disjoint sets,利用merge把好朋友們聯集在一起。要判斷同一陣營,就看看大家是不是同一群好朋友;要判斷不同陣營,就看看對方的敵人是不是跟自己是同一群好朋友。由於一開始每個人都沒有敵人,所以替每個人都設定一個虛擬的假想敵。
UVa 10158 10505 10608
範例:點燈遊戲(lights out puzzle)(minimum all-ones problem)
嘗試熄滅(或點燃)所有燈。按下任何一個開關,都會連帶影響自己及其四周的燈,亮變暗、暗變亮。
無論同時按或分開按、先按或後按,造成的影響都一樣。一個開關按兩次,將相互抵銷,如同按零次。
一、以函數當作模型,函數是各盤面之間的關聯:g(舊盤面) = 新盤面,g為一種按開關的方式。這種模型相當常見,但是不適用此題。
二、以函數當作模型,函數是開關和盤面的對應關係:f(按下的開關) = 盤面,f是遊戲規則。
只要求出f的反函數,就可以用盤面判斷按下的開關。巧妙的是,f是線性函數,故可以解一次方程組來找到反函數。解一次方程組可以用「高斯消去法」。
加法運算:f(同時按下開關A和B) = f(按下開關A) + f(按下開關B)。設定成xor。 倍率運算:f(按下開關A一共k次) = k f(按下開關A)。k模二之後,設定成and。
然而f不見得有反函數,端看遊戲規則和盤面形狀。當f有反函數,無論盤面長得如何,都一定有解。當f沒有反函數時,則難以確定盤面是否有解,屬於NP-complete問題。
UVa 10309 10318 ICPC 8045
reduction
套用模型當中,有一種情況是:原問題是某一個問題的特例。套用通例,解決特例,稱作「歸約」。
因為通例相對複雜、特例相對單純,所以原問題極可能存在更快更好的解法。
範例:最短間距(minimum gap problem)
一條鐵道,沿途設站。已知里程,請找出距離最近的兩站。
以數線作為模型,鐵道對應到數線、車站對應到點座標,距離最近的兩站對應到「數線上距離最近的兩個點」。
想要解決「數線上距離最近的兩個點」,可以套用先前介紹的「平面上距離最近的兩個點」。這兩個問題的本質是相同的,前者是一維版本,後者是二維版本;前者是特例,後者是通例。
只要把每個車站的座標,增加一個維度,該維度的數值通通設定為相同數值,然後計算「平面上距離最近的兩個點」,就得到距離最近的兩站。
「數線上距離最近的兩個點」是特例、「平面上距離最近的兩個點」是通例,我們有機會替「數線上距離最近的兩個點」找到計算時間更短、更有效率的演算法。
範例:用生命遊戲作為模型,模擬生命遊戲。
symbol, reasoning, structure
前言
學習數學、學習理科,分成三個階段:符號、推理、結構。
這是我個人意見。
符號symbol
p=mv。動量等於質量乘以速度。
數學式子非常簡單,只是一個乘法式子。舉例來說,質量2,速度3,6=2×3,得到動量6,我想大家都會計算。
圖解說明也非常簡單。畫一個正方形,代表物體。畫一條斜紋橫線,代表地板。畫一個箭頭,代表速度。寫上一個m,代表質量。
但是速度是什麼?質量是什麼?這才是問題所在。
為了幫助想像,只好舉例,只好類比。
速度:實際揮動手臂。動得很快,速度快。動得很慢,速度慢。
質量:如果是在地球表面上的話,可以稱重稱出大小。
動量:乘法是n份加法。質量速度的份量越多,動量就越多。
舉例來說,車子比人類更重、更快,所以動量更大。但是車子靜止不動的話,那就沒有動量。
大家聽完這些話,連結人生經驗,激發大腦的分門別類的機制,然後大家就對動量有一點點新的感受了。
符號本身是一種代稱。然而數學概念往往沒有實物可以參照。即便是實物也往往出現不同見解。每個人只能依賴自己的感受。舉例來說,我跟你對於富裕的理解不是同一件事情,我跟你看到的紅色不是同一種紅色。符號的意義只能靠自己去揣摩。藉由他人的行為舉止,揣摩符號的意義。有如學習語言。
符號同時也是一種泛稱。我在講p = mv的時候,其實我是在講車子在動、身體在動、……。甚至是我自己都沒想過的東西。怎樣算是p = mv,怎樣不算是p = mv,需要經年累月去揣摩。
推導derivation、推理reasoning
推導就是一個東西變成另一個東西。使用100%正確的變換方法。從已經確定的東西作為前提,一直變、一直變,變出新的結論。
(0) p = mv (1) d/dt p = d/dt mv 等號兩側同時微分,依然相等。 (2) d/dt p = m d/dt v 假設m是常數。根據分配律,依然相等。 (3) let f = d/dt p 設定新符號 let a = d/dt v f = ma 牛頓運動定律
推理就是替換這段過程當中的某些東西,重新推導一遍。替換前提、替換結論、替換中間過程。
比方說很多人不瞭解什麼是微分。那麼我們替換成其他數學元件。我把「微分」替換成「平均數」與「無限微小」。
(0) p = mv p₁+p₂+... m₁v₁+m₂v₂+... (1) ————————— = ————————————— 一段時間Δt的平均數 Δt Δt 等號兩側同加同除,依然相等。 p₁+p₂+... v₁+v₂+... (2) ————————— = m ————————— 假設m不隨時間改變 Δt Δt m₁ = m₂ = ... p₁+p₂+... (3) let f = ————————— when Δt→0 那一段時間很短很短 Δt v₁+v₂+... let a = ————————— when Δt→0 Δt f = ma 牛頓運動定律
也可以替換前提、替換結論,推導Δx = vΔt + 1/2 aΔt²。
大部分教科書只會推導,不會推理。大部分教師在課堂上也只會推導,不會推理。你可以自己推理。
結構structure
結構好比書籍目錄。
比方說:微分是重中之重,應該單獨建立章節。
chapter 1: 數學基礎知識:微分 chapter 2: p = mv chapter 3: f = ma
但是也可能是這樣:微分只是微不足道的配角。
chapter 1: p = mv chapter 2: f = ma chapter 2.1: 數學基礎知識:微分
甚至也可能是這樣:額外補充一些也很重要的東西。
chapter 1: 微積分 chapter 1.1: 微分 chapter 1.2: 積分 chapter 2: 運動定律 chapter 2.1: p = mv chapter 2.2: f = d/dt p chapter 2.2.1: f = ma
學者的腦子裡面都有好幾套結構。學者只會挑出其中一套結構寫成書籍。學者依照經驗,決定誰先誰後、誰大誰小。什麼是重點,什麼是順便,看了就知道。
做研究,本質上就是想出了一套與眾不同的結構,並且找到了結構缺失的地方,並且完善了結構。
如何建立結構呢?嘗試各種推理,然後物以類聚。
一個更複雜的例子:如何介紹台灣大學
從官方網站可以看到,台灣大學分成兩種單位:行政組織、學術單位。行政組織細分成學生事務處、教務處、總務處、圖書館、……。學術單位細分成文學院、理學院、工學院、醫學院、……。
如果你在路上遇到一個路人,你會這樣介紹台灣大學嗎?不會。你會告訴他台灣大學在台北。前門是羅斯福路,鄰近捷運公館站。後門是辛亥路,鄰近捷運科技大樓站。另一個後門在長興街,那裏是學生宿舍,只有公車。路人在意地理位置。
如果是網路筆戰,又有另外一套思路。網民在意的是文科台政北,理科四大四中,醫科台大陽明北醫。大家在意排名、在意優劣。
你得視情況拿出適合的結構。
如何選擇適當的結構呢?多聊天、多看書。
後話
先懂符號,再懂推理,最後才是結構。前面單純,後面複雜。
學者、著作,被公認為大師、經典,通常是三者之一有創新。
教師是否優秀,也可以從這三者來分析。
學生學習困難,通常是三者之一出了問題。甚至都有問題。
一、符號。
學生對應不上符號與概念。又或者,學生還沒辦法完全確定那是什麼、其他還有什麼。
舉個例子。世界上有一種長相特別的動物,馬的耳朵、犀牛的腿、豬的身體、象的鼻子。即便我這樣形容,你也不能十分確定這種動物的長相,除非你看過實物。
人生經歷豐富,時機成熟足以頓悟。有時候則是怎麼也悟不了。
二、推理。
學生不熟悉推導過程的某些東西。又或者,學生還沒習慣。
很多時候只是還沒習慣。例如籃球運動,你能看懂帶球上籃的動作,你也知道每個步驟:運球、收球、舉球、單手扶球,送球,一邊跑一邊做上述動作。萬事俱備,但是實際去做卻做不好,畢竟身體還沒習慣。數學知識也是同樣的道理,實際去算卻算不好,畢竟腦袋還沒習慣。
三、結構。
學生的知識量不足以撐起一個穩定的結構,甚至在對話過程當中不斷調整。又或者,學生的結構不是老師的結構,雞同鴨講。
例如教育部不讓台灣大學校長就任,那就需要建立第四種結構才能解釋得通。你跟學生聊體制,結果學生想的是排名:台大教授都很優秀,誰來都沒差吧,為什麼教育部需要做這種事?學生自己解釋不通,那就沒辦法弄懂。
ansatz
擬設
觀察問題,回想曾經遭遇的類似問題,其具備哪些特性。一開始就假設問題已經具備此特性。採用此特性進行推理,找出其他特性、以及不可能具備的特性,藉此減少問題當中尚未解明的部分。
擬設的同義詞是「八九不離十」。擬設是「幾乎正確的假設」,只是需要實際驗證。當問題找到答案了,始能驗證擬設是正確的。
另外,如果推理出現矛盾,那就表示一開始的假設不正確。此即邏輯學當中的proof by contradiction。
另外,即便推理沒有出現矛盾,也不表示一開始的假設正確、不正確。此即邏輯學當中的false imply anything。例如「先射箭再畫靶」。得到答案之後,還是得想辦法驗證一開始的假設是正確的。
擬設的知名範例是微分方程式求解。事先假設解的形式。
已有數學定理保證特定的微分方程式有唯一解。因此,得到答案之後,代入驗算確認無誤,一定會是唯一正確答案。此時,事先假設解的形式,一定會是唯一正確形式。
有機會我再補充更多例子。一時之間沒辦法想出例子。