記得高中時,建中電研社社刊有一則笑話:

如果高斯 (Gauss) 小學時就學程式設計,他可能就懶得發明等差級數公式了,他會直接坐在電腦前,輸入:

sum := 0
for i := 1 to 100 do
   sum := sum + i
end for

雖然是笑話一則,但也很貼切點出 algorithm(演算法;演算法則)的最原始用途:提供另一種解決數學題目的方法。

在前一篇文章〈運算思惟其實一點也不神祕〉中,我曾提到「運算思惟,目前公認有四大核心」,其中尤以第四核心最特別:

嚴格來說,運算思惟與其他領域(非 STEM 領域尤然)最大分野,就是演算法 (algorithm) 了。

現在,我們就來簡單看一看這個所謂的「最大分野」吧。



先談點嚴肅的歷史。沒興趣的人,可以跳過。

任何計算機概論教科書,都會提到現代通用型 computer(電腦、計算機)的一個直接源頭,是 18 世紀數學家 Charles Babbage 製作的差分機、構思的分析機。這種機械式的自動計算儀器,之所以能夠 "let it go" 放手讓它埋頭苦幹,背後的必要條件,就是我們人類要先將演算步驟不含糊地條列出來。精準,嚴密,一點瑕疵都不行。

此處的「演算步驟」,其實就是 algorithm。

Algorithm 最古可追溯至質數的篩法,可說是流著貴族的血液呢。後來一堆長除法、輾轉相除法、因數分解,都是 algorithm 的具體實例。

這麼說,algorithm 只是附庸於數學底下的「機械性計算」層次?

其實不然。近代比較正視 algorithm 價值、予以扶正地位的,要算是 19 世紀末開始的一系列數學革命,像 1900 年德國數學家希爾伯特提出的 23 道難題,希望替數學建立起一套公理化體系+形式化自動推導證明機制,以正本清源解決 19 世紀末開始出現的一堆撼動古典數學根基的非歐幾何集合悖論邏輯悖論。雖然這種夢想被著名的哥爾德不完備定理粉碎,但也從根本提升整個 algorithm 的理論地位,不再只是單純的「計算」而已。摘錄一段維基百科對這段歷史轉折的說明

The concept of algorithm has existed for centuries; however, a partial formalization of what would become the modern algorithm began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability" or "effective method"; those formalizations included the GödelHerbrandKleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939. Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem.

這就是前面我講的「嚴格來說,運算思惟與其他領域(非 STEM 領域尤然)最大分野,就是演算法 (algorithm) 了。」

所以,不要以為資訊系成天都只有在做「寫寫程式」這種連早慧的小學生都會的事呀。

(謎之音:維基百科短短的一段話,卻數盡當年 algorithms、formal languages 課程中令人生畏的高等議題呀。)



當然啦,大家現在常在講的 "computational thinking",講「運算思惟」,多半沒有觸及這麼深的理論層次。

如果不要扯到這麼遠,回到比較貼近一般人的角度,能不能具體講講 algorithm 是什麼,in plain English?

經典教科書 Introduction to Algorithms 給了一份十分親民的解釋:

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

維基百科也給了一段親民的開場白

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed.

關鍵字:

  • well-defined computational procedure
  • a sequence of computational steps
  • self-contained step-by-step set of operations

所以,如果用很粗淺的白話角度來看 algorithm,就是:根據明確給定的指示,一步步執行的有限步驟集合;自給自足,不假外求。

一點也不神秘吧?

當然啦,要再深究的話,即使是上面這段非常非常粗淺的親民說法,也是有很多值得進一步提問的:

  • 怎樣的指示 (computational step/procedure/operation) 才叫做明確 (well-defined)?
  • 怎樣才叫做自給自足 (self-contained)?
  • 怎樣才叫做一步步執行 (step by step)?

不斷追問,就能追問出其他領域(非 STEM 領域尤然)不太探討的深層議題了,但是,我知道你不想再回頭看到太理論的論述⋯⋯姑且就此打住。



看了 algorithm 的俗民版操作型定義之後,進一步思考:algorithm 的目的是什麼?

冼鏡光在《名題精選百則》提到:

從某個角度來看,計算機科學都是在為寫作程式服務:吸收各行各業,各個不同科目、範疇而來的問題,分析那些問題,並且可能的話,找出一個「高效率」的演算法來解決問題。

各行各業的問題,變化萬千,所以,單以直覺來想像,解決手法一定也是五花八門。

是的,只要翻開任何一本演算法經典級教科書的目錄,一定會震懾於演算法的數量。

不過,這些書也告訴我們,繁多花招之餘,還是有一些獨孤九劍等級的「破xx式」。

像 CLR 白皮書 Introduction to Algorithms 就將 "Divide and Conquer"(分而治之)及 recursion(遞迴、遞歸)列為重要的基礎心法,而 Introduction to Algorithms: A Creative Approach 一書甚至將 "Design of Algorithms by Induction" 這種數學歸納法、遞迴法視為最值得深刻掌握的通用心法。

所以,分而治之、遞迴,是 algorithm 的重要核心。不能說是全部,但至少是重要的關鍵。


以文章開頭的等差級數為例,如果用分而治之觀念來思考,該怎麼做呢?

我們可能會先把 1+2+3+...+100 的大問題,拆成 1+2+3 這種較容易處理的小問題,之後再利用加法的結合律去合併出最終答案。因此,先針對 1+2+3 這個小問題來思考:

sum := 0
sum := sum + 1
sum := sum + 2
sum := sum + 3

如果懂得觀察箇中的模式規律:「啊,不就只是一直把 1 加上去,把 2 加上去,把 3 加上去嘛!」,就會用初級的迴圈改寫成:

sum := 0
for i := 1 to 3 do
  sum := sum + i
end for

懂得寫到這一步,基本上,1+2+3+...+100 就不是難事了。

如果沒在數學課堂上睡著,學過數學歸納法,會發現,這簡直就是天生的遞迴應用:

function sigma(n) :=
  if (n <= 1) return 1;
  else return n + sigma(n - 1);
end function

sum := sigma(100)

所以,小結一下:分而治之遞迴、觀察尋求模式規律,是 algorithm 的重要核心。不能說是全部,但至少是重要的關鍵。



咦,「分而治之」、「遞迴」、「模式及規律」,好熟悉的字眼⋯⋯豈不正與運算思惟的另外三大核心相呼應嗎?

  • 呼應 decomposition 原則:分而治之的第一階段,就是在對原始問題進行拆解、分解,變成容易解決的次問題,或是在過程中容易尋求規律。
  • 呼應 pattern recognition 原則:遞迴,就是在針對初步切分的小問題,嘗試識別模式、尋求規律,以形成模式假說。
  • 呼應 abstraction 原則:遞迴,就是將原始問題提升至抽象層次,在抽象層次解決。

所以,運算思惟的前三核心(decomposition、pattern recognition、abstraction),是第四核心 (algorithm) 的重要基礎。而我前一篇文章〈運算思惟其實一點也不神祕〉就在申論:前三核心的能力,本來就是語文課程及數學課程就該好好培養的,並不是只有程式設計課程才能培養。

只不過,現今的語文課程及數學課程,花太多精力在搞背誦、蒐集解題花招,而沒有踏實聚焦在王道的議題探索及解題思惟上,導致 literacy capability 及 problem solving 能力都不足。這種貧乏的基礎,能夠進一步灌輸 computational thinking 嗎?



可以做個大總結了。

運算思惟 (computational thinking),目前公認的四大核心是:

  1. Decomposition:拆解、分解。
  2. Pattern recognition:模式識別、規律尋求。
  3. Abstraction:抽象化。
  4. Algorithms:演算法、演算法則。

這些核心能力,都不盡然只有在程式設計課程才能培養。即使是 algorithm 這項與其他領域最大分野,也有相當大的比例是奠基在前三項基本功。

君子務本,本立而道生。你看得出來基礎教育該著重在哪一個「本」了嗎?