上頁 123456 次頁

初探「重差」的內在理路 (第 5 頁)

李國偉

 

首頁 | 搜尋

.原載於科學月刊第十六卷第二期
.作者當時任職於中央研究院數學所

註釋
對外搜尋關鍵字
 
演算法則

如果劉徽在自己的心婼T實有一條證明的道路,那麼說這條道路起自圖一中直角三角形相似關係的「端」,是一個合理的揣測。因為《周髀算經》中商高曰:「平矩以正繩,偃矩以望高,覆矩以測深,臥矩以知遠。」這種知識確實是當時數學家所熟悉 註10 。 但是這條證明的道路,在劉徽沒有把最基本的假設說出,沒有把推論過程中的計算寫明的情況下,仍不足以歸入現代數學所接受的「證明」之列。我們該用什麼樣的理論架構或模式,來看待這類實質意義遠超過實用性計算的理路呢?現代計算機科學中所謂的「演算法則」(algorithm)提供了一個非常好的出路。

「演算法則」的現代意義,就是一組有限多的規則,遵循這些規則便可解答特定的問題。它有幾個必要的條件:

一、有限性:必須在有限操作步驟之後停止。
二、確定性:如何執行演算的步驟必須明確的約定好,不可以涉及機率性的選擇。
三、輸入、輸出:明確的給定起始運算的資料,並且說明什麼是最終的結果。
四、有效性:每一個基本的運算步驟都已化約到最簡單的方法,不需另假巧思或額外的知識便可即刻執行。

以西算史上有名的歐幾里德相除法為例,寫成演算法則的形式便是:

歐氏算則
輸入:二正整數m、n。
輸出:m與n的最大公因數。
程序:
E1.以 nm,得餘數 r
E2.若 r=0,演算終止;輸出 n
E3.令 $m \leftarrow n$$n \leftarrow r$,回到 E1。 其中 $\leftarrow$ 表示把箭號右邊的值當作箭號左邊量的最新值 註11

用「演算法則」這個概念來衡量劉徽的解法,我們發現是合乎標準的。 「演算法則」與「證明」相去多遠呢?以近二十年理論計算科學發展的經驗看來, 解決問題有兩個階段:第一階段是設計好「演算法則」,第二階段是證明「演算法則」是正確的,確實能算出所需要的輸出。相當大量的問題,特別是概念上只涉及初等數學的問題,真正困難的步驟是第一階段。等到適用的「演算法則」設計好了,我們對問題就已經有了相當良好的認識與掌握,使得第二階段的正確性說明(proof of correctness)往往變成沒有必要明文書寫。這種現象的例子,在各種有關「演算法則」的教科書中比比皆是。因此當我們以「演算法則」的模式來了解劉徽的成就時,實在不必為他省了連現代人都會省的步驟而感覺遺憾了。

   

上頁 123456 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:石莉君 / 校對:康明軒 / 繪圖:簡立欣 最後修改日期:2/17/2002