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

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

順便說一下，1946年的今天，世界上第一臺通用電腦——電子數(shù)值積分計算機在美國賓夕法尼亞大學正式啟用，就是那個ENIAC。

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

Cpl. Irwin Goldstein正在設置ENIAC一個函數(shù)表上的開關

“算法”一詞的來歷

中文的“算法”一詞至少在唐代就出現(xiàn)了，在此之前也有“術”“算術”等詞，最早出現(xiàn)在《周髀算經(jīng)》《九章算術》。而且，“算法”一詞的含義從古到今幾乎沒有發(fā)生變化。

英文的“算法”（algorithm）一詞來源于9世紀波斯數(shù)學家花拉子米（al-Khwārizmī，780?~850?）——就是那個解決一次方程及一元二次方程的方法的人?；ɡ用椎睦∥淖g名是“Algoritmi”。英文對“算法”原譯為“algorism”，意思是花拉子米的運算法則，在18世紀演變?yōu)椤癮lgorithm”。這個詞出現(xiàn)于12世紀，指的是用阿拉伯數(shù)字進行算術運算的過程。

蘇聯(lián)在1983年9月6日發(fā)行的紀念郵票，以紀念花拉子米1200歲生辰

歷史上的一些著名算法

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

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

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

《九章算術》

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

劉徽割圓術原理

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

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

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

牛頓法

17世紀之后算法的發(fā)展

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

Pascaline，1642年布萊茲·帕斯卡的算術機，主要用作加法器

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

倫敦科學館中巴貝奇分析機的復制品

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

愛達·勒芙蕾絲

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

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

圖靈機的藝術表示

在此之后，算法更偏向于計算機科學領域，各種解決不同問題的算法也層出不窮，涉及排序、統(tǒng)計、線性規(guī)劃、搜索、壓縮等方面。

到了現(xiàn)在，隨著人工智能和機器學習的發(fā)展，涉及到神經(jīng)網(wǎng)絡的算法變得越發(fā)重要。

拓展閱讀

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

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

參考資料

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容