偽·從零開始學演算法 - 1.2 演算法的歷史

我在寫1.1節的時候本來是要寫這個的，但是突然就忘了……就作為一節來寫吧。

順便說一下，1946年的2月14日，世界上第一台通用電腦——電子數值積分計算機在美國賓夕法尼亞大學正式啟用，就是那個ENIAC。

別只想著情人節，要不是幾十年來科技的進步，你們才沒機會在朋友圈、空間什麼的大秀恩愛。

「演算法」一詞的來歷

中文的「演算法」一詞至少在唐代就出現了，在此之前也有「術」「算術」等詞，最早出現在《周髀算經》《九章算術》。而且，「演算法」一詞的含義從古到今幾乎沒有發生變化。

英文的「演算法」（algorithm）一詞來源於9世紀波斯數學家花拉子米（al-Khwārizmī，780?~850?）——就是那個解決一次方程及一元二次方程的方法的人。花拉子米的拉丁文譯名是「Algoritmi」。英文對「演算法」原譯為「algorism」，意思是花拉子米的運演算法則，在18世紀演變為「algorithm」。這個詞出現於12世紀，指的是用阿拉伯數字進行算術運算的過程。

歷史上的一些著名演算法

對於算籌、算盤的操作的方法，我不知道是否屬於演算法。

約公元前300年記載於《幾何原本》中的輾轉相除法（歐幾里得演算法）被人們認為是史上第一個演算法，可以求兩數的最大公約數。直到今天，它還有很大的用途。

《九章算術》給出了四則運算、最大公約數、最小公倍數、開平方根、開立方根、求素數的埃拉托斯特尼篩法，線性方程組求解的演算法。

三國時代的劉徽給出求圓周率的演算法：劉徽割圓術，比阿基米德割圓術得出的結果更加精確。祖沖之使用該方法將圓周率的準確值計算到了3.1415926和3.1415927之間，保持了世界最準確圓周率達900年之久。

唐代以來，歷代更有許多專門論述「演算法」的專著。宋代的秦九韶提出的秦九韶演算法，直到今天仍是多項式求值比較先進的演算法。

在9世紀的阿拉伯世界，花拉子米寫成《代數學》，其對解決一次方程及一元二次方程的方法催生了代數——大家熟知的求多元（尤其是二元）一次方程和一元二次方程的解法就來源於此。700多年後，三次方程、四次方程的求根公式才被得出。

牛頓於1671年提出的牛頓法，相比於二分法可以更快速地求函數的根或者是函數的極值。

17世紀之後演算法的發展

17世紀起，早期的機械計算機出現了。從加法到傅里葉變換，它們的功能越來越強大。

工業革命帶來了紡織業的變革，出現了可以自動織出帶花紋的布的織布機，它們使用打孔卡輸入指令。這種設計也被英國數學家查爾斯·巴貝奇設計的分析機使用。

拜倫的女兒愛達·勒芙蕾絲（Ada Byron；Ada, Countess of Lovelace）於1842年為這個想像中的機器編寫求解伯努利微分方程的程序，因此愛達·勒芙蕾絲被大多數人認為是世界上第一位程序員。但是，這個機器因為種種原因，直到巴貝奇去世也沒有被真正地製造出來。

後來的數學家對演算法的貢獻大多在於數理邏輯的構建上，在此我因為知識缺乏，看不懂資料，不便講述。感興趣的話可以看一下參考資料。

20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要的作用。

在此之後，演算法更偏向於計算機科學領域，各種解決不同問題的演算法也層出不窮，涉及排序、統計、線性規劃、搜索、壓縮等方面。

到了現在，隨著人工智慧和機器學習的發展，涉及到神經網路的演算法變得越發重要。

拓展閱讀

The Best of the 20th Century: Editors Name Top 10 Algorithms

http://www.uta.edu/faculty/rcli/TopTen/topten.pdf

參考資料

• 普通高中課程標準實驗教科書（必修） 數學（A版） 必修3. 人民教育出版社
• 演算法 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95
• 電子數值積分計算機 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E9%9B%BB%E5%AD%90%E6%95%B8%E5%80%BC%E7%A9%8D%E5%88%86%E8%A8%88%E7%AE%97%E6%A9%9F
• 花拉子米 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E8%8A%B1%E6%8B%89%E5%AD%90%E7%B1%B3
• 九章算術 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E4%B9%9D%E7%AB%A0%E7%AE%97%E6%9C%AF
• 割圓術 (劉徽) - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E5%89%B2%E5%9C%86%E6%9C%AF_(%E5%88%98%E5%BE%BD)
• 牛頓法 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95
• Pascals calculator - Wikipedia
  https://en.wikipedia.org/wiki/Pascal%27s_calculator
• 分析機 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E5%88%86%E6%9E%90%E6%A9%9F
• 埃達·洛夫萊斯 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E6%84%9B%E9%81%94%C2%B7%E5%8B%92%E8%8A%99%E8%95%BE%E7%B5%B2
• 圖靈機 - 維基百科，自由的百科全書
  https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA

推薦閱讀：