演算法的發展史

⑴ 求算術起源至今的發展史 先中國再外國 一一列舉

我國數學在世界數學發展史上，有它卓越的貢獻。早在遠古時代，人們就用繩結表示事物的多少，在彩陶中繪有大量的直線、三角、圓、方、菱形、五邊形、六邊形等對稱圖案，在房屋遺址的基地上，亦發現幾何圖形，表明遠古的人們在一定程度上已經具有數和形的概念。

在新石器時期的彩陶缽上，有多種刻畫符號，其中丨、、、×、+等，很可能是我國最早的記數符號。產生文字之後，在殷商的甲骨文中出現了記數的專用文字和十進制記數法，並且運用規和矩作為簡單的繪圖和測量工具。《前漢書·律歷志》記載了用竹棍表示數和計算的方法，稱為算籌和籌算。在春秋早期乘法口訣被稱為「九九」歌，已經成為很普通的知識。

春秋戰國時期，學術繁榮，產生了相當精彩和可貴的數學思想；公元前6世紀，已經有了關於簡單體積和比例分配問題的演算法，在《考工記》中記載了分數和角度的資料；到秦始皇時，統一了度量衡，並且基本上採用了十進制的度量單位，在《墨經》中提出了幾何名詞的定義和幾何命題等。《杜忠算術》和《許商算術》是最早的數學專著，但這兩部書都失傳了。至今仍保留的古代數學專著是《算數書》，全書共有60多個小標題、90多個題目，書中內容涉及了整數和分數的四則運算、比例問題、面積和體積問題等、並且含有「合分」、「少廣」等數學思想。

大約公元前1世紀完成了《周髀算經》（書中大部分內容於公元前7到6世紀完成），書中記述了矩的用途、勾股定理及其在測量上的應用，相似直角三角形對應邊成比例的定理、開平方問題、等差級數問題，應用古「四分歷」計算相當復雜的分數運算等，此書為重要的寶貴文獻。

古代數學的著名著作是《九章算術》，大約成書於公元1世紀東漢初年，全書列舉了246個數學問題及解決問題的方法。共有九章：第一章「方田」介紹土地面積的計算、含有正方形、矩形、三角形、梯形、圓、環等面積公式，弓形面積和球形表面積的近似公式，還有分數四則運演算法則、約分、通分、求最大公約數等方法；第二章「粟米」介紹了各種糧食折算的比例問題，及解比例的方法，稱為「今有術」；第三章「衰（Cuǐ）分」介紹了按等級分配物資或按一定標准攤派稅收的比例分配問題、等差數列和等比數列問題等；第四章「少廣」介紹了已知正方形面積或正方體體積，求邊長或棱長的開平方或開立方的方法，已知球的體積求直徑的問題等；第五章「商功」介紹了立體體積計算，包括長方體、稜柱、棱錐、稜台、圓柱、圓錐、圓台、楔形體等體積的計算公式；第六章「均輸」介紹了計算按人口多少、物價高低、路程遠近等條件，合理攤派稅收、民工的正比、反比、復比例、等差級數等問題；第七章「盈不足」介紹了盈虧類問題的演算法；第八章「方程」介紹了一次聯立方程問題，引入了負數的概念，及正負數的加減法則；第九章「勾股」介紹了勾股定理的應用和簡單的測量問題，其後，歷史上著名數學家劉徽、祖沖之、李淳風、賈憲等，都曾經深入研究和注釋過《九章算術》並且提出許多新的概念和新的方法。在諸如勾股定理的證明、重差術、割圓術、圓周率近似值、球的體積公式、二次和三次方程的解法。同餘式和不定方程的解法等方面做出了重要的新貢獻。

我國古代數學專著有《勾股圓方圖注》、《九章算術注》、《孫子算經》、《五經算術》、《綴術》等。特別應該指出的是，劉徽在《九章算術注》中對《九章算術》的大部分數學方法作了嚴密的論證，對於一些數學概念提出了明確的解釋，為中國數學發展奠定了堅實的理論基礎。祖沖之在《綴術》中得出了比劉徽所提出的值更精密的圓周率，成為舉世公認的重大成就。賈憲在《黃帝九章演算法細草》中提出的「開方作法本源」圖和增乘開方法，以及《孫子算經》中的「孫子問題」，《張邱建算經》中的「百雞問題」、珠算盤和珠算術等等，均在世界數學發展史上有深遠影響。 大約在3000年以前中國已經知道自然數的四則運算，這些運算只是一些結果，被保存在古代的文字和典籍中。乘除的運算規則在後來的「孫子算經」(公元三世紀)內有了詳細的記載。中國古代是用籌來計數的，在我們古代人民的計數中，己利用了和我們現在相同的位率，用籌記數的方法是以縱的籌表示單位數、百位數、萬位數等；用橫的籌表示十位數、千位數等，在運算過程中也很明顯的表現出來。「孫子算經」用十六字來表明它，「一從十橫，百立千僵，千十相望，萬百相當。」
和其他古代國家一樣，乘法表的產生在中國也很早。乘法表中國古代叫九九，估計在2500年以前中國已有這個表，在那個時候人們便以九九來代表數學。現在我們還能看到漢代遺留下來的木簡(公元前一世紀)上面寫有九九的乘法口訣。
現有的史料指出，中國古代數學書「九章算術」(約公元一世紀前後)的分數運演算法則是世界上最早的文獻，「九章算術」的分數四則運算和現在我們所用的幾乎完全一樣。
古代學習算術也從量的衡量開始認識分數，「孫子算經」(公元三世紀)和「夏候陽算經」(公元六、七世紀)在論分數之前都開始講度量衡，「夏侯陽算經」卷上在敘述度量衡後又記著：「十乘加一等，百乘加二等，千乘加三等，萬乘加四等；十除退一等，百除退二等，千除退三等，萬除退四等。」這種以十的方冪來表示位率無疑地也是中國最早發現的。
小數的記法，元朝(公元十三世紀)是用低一格來表示，如13.56作1356 。在算術中還應該提出由公元三世紀「孫子算經」的物不知數題發展到宋朝秦九韶(公元1247年)的大衍求一術，這就是中國剩餘定理，相同的方法歐洲在十九世紀才進行研究。
宋朝楊輝所著的書中(公元1274年)有一個1—300以內的因數表，例如297用「三因加一損一」來代表，就是說297=3×11×9，(11＝10十1叫加一，9＝10—1叫損一)。楊輝還用「連身加」這名詞來說明201—300以內的質數。
(二)屬於代數方面的材料
從「九章算術」卷八說明方程以後，在數值代數的領域內中國一直保持了光輝的成就。
「九章算術」方程章首先解釋正負術是確切不移的，正象我們現在學習初等代數時從正負數的四則運算學起一樣，負數的出現便豐富了數的內容。
我們古代的方程在公元前一世紀的時候已有多元方程組、一元二次方程及不定方程幾種。一元二次方程是借用幾何圖形而得到證明。 不定方程的出現在二千多年前的中國是一個值得重視的課題，這比我們現在所熟知的希臘丟番圖方程要早三百多年。具有x3+px2+qx=A和x3+px2=A形式的三次方程，中國在公元七世紀的唐代王孝通「緝古算經」已有記載，用「從開立方除之」而求出數字解答(可惜原解法失傳了)，不難想像王孝通得到這種解法時的愉快程度，他說誰能改動他著作內的一個字可酬以千金。
十一世紀的賈憲已發明了和霍納(1786—1837)方法相同的數字方程解法，我們也不能忘記十三世紀中國數學家秦九韶在這方面的偉大貢獻。
在世界數學史上對方程的原始記載有著不同的形式，但比較起來不得不推中國天元術的簡潔明了。四元術是天元術發展的必然產物。
級數是古老的東西，二千多年前的「周髀算經」和「九章算術」都談到算術級數和幾何級數。十四世紀初中國元代朱世傑的級數計算應給予很高的評價，他的有些工作歐洲在十八、九世紀的著作內才有記錄。十一世紀時代，中國已有完備的二項式系數表，並且還有這表的編制方法。
歷史文獻揭示出在計算中有名的盈不足術是由中國傳往歐洲的。
內插法的計算，中國可上溯到六世紀的劉焯，並且七世紀末的僧一行有不等間距的內插法計算。
十四世紀以前，屬於代數方面許多問題的研究，中國是先進國家之一。
就是到十八，九世紀由李銳(1773—1817)，汪萊(1768—1813)到李善蘭(1811—1882)，他們在這一方面的研究上也都發表了很多的名著。
(三)屬於幾何方面的材料
自明朝後期(十六世紀)歐幾里得「幾何原本」中文譯本一部分出版之前，中國的幾何早已在獨立發展著。應該重視古代的許多工藝品以及建築工程、水利工程上的成就，其中蘊藏了豐富的幾何知識。
中國的幾何有悠久的歷史，可靠的記錄從公元前十五世紀談起，甲骨文內己有規和矩二個字，規是用來畫圓的，矩是用來畫方的。
漢代石刻中矩的形狀類似現在的直角三角形，大約在公元前二世紀左右，中國已記載了有名的勾股定理(勾股二個字的起源比較遲)。
圓和方的研究在古代中國幾何發展中佔了重要位置。墨子對圓的定義是：「圓，一中同長也。」—個中心到圓周相等的叫圓，這解釋要比歐幾里得還早一百多年。
在圓周率的計算上有劉歆(？一23)、張衡(78—139)、劉徽(263)、王蕃(219—257)、祖沖之(429—500)、趙友欽(公元十三世紀)等人，其中劉徽、祖沖之、趙友欽的方法和所得的結果舉世聞名。
祖沖之所得的結果π=355/133要比歐洲早一千多年。
在劉徽的「九章算術」注中曾多次顯露出他對極限概念的天才。 在平面幾何中用直角三角形或正方形和在立體幾何中用錐體和長方柱體進行移補，這構成中國古代幾何的特點。
中國數學家善於把代數上的成就運用到幾何上，而又用幾何圖形來證明代數，數值代數和直觀幾何有機的配合起來，在實踐中獲得良好的效果．
正好說明十八、九世紀中國數學家對割圓連比例的研究和項名達(1789—1850)用割圓連比例求出橢圓周長。這都是繼承古代方法加以發揮而得到的(當然吸收外來數學的精華也是必要的)。

(四)屬於三角方面的材料
三角學的發生由於測量，首先是天文學的發展而產生了球面三角，中國古代天文學很發達，因為要決定恆星的位置很早就有了球面測量的知識；平面測量術在「周牌算經」內已記載若用矩來測量高深遠近。

劉徽的割圓術以半徑為單位長求圓內正六邊形，十二二邊形等的每一邊長，這答數是和2sinA的值相符(A是圓心角的一半)，以後公元十二世紀趙友欽用圓內正四邊形起算也同此理，我們可以從劉徽、趙友欽的計算中得出7.5o、15o、22.5o、30o、45o等的正弦函數值。

在古代歷法中有計算二十四個節氣的日晷影長，地面上直立一個八尺長的「表」，太陽光對這「表」在地面上的射影由於地球公轉而每一個節氣的影長都不同，這些影長和「八尺之表」的比，構成一個餘切函數表(不過當時還沒有這個名稱)。

十三世紀的中國天文學家郭守敬(1231—1316)曾發現了球面三角上的三個公式。 現在我們所用三角函數名詞：正弦，餘弦，正切，餘切，正割，餘割，這都是我國十六世紀已有的名稱，那時再加正矢和余矢二個函數叫做八線。

在十七世紀後期中國數學家梅文鼎(1633—1721)已編了一本平面三角和一本球面三角的書，平面三角的書名叫「平三角舉要」，包含下列內容：(1)三角函數的定義；(2)解直角三角形和斜三角形；(3)三角形求積，三角形內容圓和容方；(4)測量。這已經和現代平面三角的內容相差不遠，梅文鼎還著書講到三角上有名的積化和差公式。十八世紀以後，中國還出版了不少三角學方面的書籍。

⑵ 演算法的歷史

「演算法」即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi，因為al-Khwarizmi在數學上提出了演算法這個概念。「演算法」原為algorism，意思是阿拉伯數字的運演算法則，在18世紀演變為algorithm。歐幾里得演算法被人們認為是史上第一個演算法。 第一次編寫程序是Ada Byron於1842年為巴貝奇分析機編寫求解伯努利方程的程序，因此Ada Byron被大多數人認為是世界上第一位程序員。因為查爾斯·巴貝奇(Charles Babbage)未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。 因為well-defined procere缺少數學上精確的定義，19世紀和20世紀早期的數學家、邏輯學家在定義演算法上出現了困難。20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用。

⑶ 演算法的描述、特性以及概念

描述演算法的方法有多種，常用的有自然語言、結構化流程圖、偽代碼和PAD圖等，其中最普遍的是流程圖。

分類：演算法可大致分為基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法，厄米變形模型，隨機森林演算法。

特徵：有窮性，演算法的有窮性是指演算法必須能在執行有限個步驟之後終止；確切性，演算法的每一步驟必須有確切的定義；輸入項：一個演算法有0個或多個輸入，；輸出項；可行性，演算法中執行的任何計算步驟都是可以被分解為基本的可執行的操作步，即每個計算步都可以在有限時間內完成。

(3)演算法的發展史擴展閱讀

演算法歷史：

「演算法」即演演算法的大陸中文名稱出自《周髀算經》；而英文名稱Algorithm 來自於9世紀波斯數學家al-Khwarizmi，al-Khwarizmi在數學上提出了演算法這個概念。「演算法」，意思是阿拉伯數字的運演算法則，在18世紀演變為"algorithm"。

因為巴貝奇未能完成他的巴貝奇分析機，這個演算法未能在巴貝奇分析機上執行。 20世紀的英國數學家圖靈提出了著名的圖靈論題，並提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現解決了演算法定義的難題，圖靈的思想對演算法的發展起到了重要作用。

⑷ 求排序演算法的發展史

對於今天排序技術的探索可以追溯到19世紀，美國人口統計局的Herman Hollerith發明了第一批具有排序裝置的製表機，成功地應用到1890年的美國人口普查。關於Hollerith及其製表機的故事，Leon E. Truesdell曾在【The Development of Punch Card Tabulation（Washington: U. S. Bureau of the Census, 1965）】中進行了有趣而詳盡地描述。

排序常式曾經是為存儲程序式計算機編寫的第一個程序，因為它集中體現了計算機潛在的非數值應用。馮·諾伊曼在1954年為了檢驗EDVAC計算機指令代碼的適用性以及評價他所建議的計算機組織的優點，編寫了內部歸並排序程序，Knuth在【Computing Surveys 2(1970), 247~260】中描述了這個發展細節。

在德國，K. Zuse於1945年獨立編寫了用於直接插入排序的程序，作為他的Plankalkul語言中線性表操作的例子之一，這一開創性的工作推遲了近30年才發表。

1946年在穆爾學校舉行的有關計算的專題討論會上，John Mauchly作了「排序和整理」的演講，是第一個公開發表的關於計算機排序的討論，包括直接插入排序和折半插入排序。

到1952年左右，內部排序的許多方法已在程序設計領域廣為流傳，但理論上的研究卻相對很少。Daniel Goldenberg用Whirlwind計算機編寫了5個不同方法的排序程序，分別就最好情況和最壞情況進行了分析。

由Howard B. Demuth於1956年撰寫的博士論文【Electronic Data Sorting. Stanford University, 1956】可以說是一篇非常值得關注的論文，因為這篇論文有助於奠定計算復雜性理論的基礎。論文利用循環的、線性的以及隨機的存儲器，考慮了排序問題的3個抽象模型，並對每個模型提出了最優（或接近最優）的方法。Demuth的論文建立了如何把理論同實踐相聯系的重要思想。

事實上，計算的大多數早期歷史都出現在比較難以得到的報告中，因為那時僅有少數人同計算機打交道。有關排序文獻的第一次付印是在1955年，用的是三篇重要的綜述性文章。第一篇文章是由J. C. Hosken撰寫的【Proc. Eastern Joint Computer Conference 8(1955), 39~55】，綜述了在計算機上進行排序的方法，以及所有可利用的專用設備，文中的54項參考文獻大多數是以廠家的手冊為基礎的。第二篇文章是由E. H. Friend撰寫的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956), 134~168】是排序技術發展史的一個重要里程碑，Friend對相當多的內部和外部排序演算法給出了細致的描述。第三篇文章是由D. W. Davies撰寫的【Proc. Inst. Elec. Engineers 103B, Supplement 1(1956), 87~93】。

1962年11月ACM主持召開了一次關於排序的研討會，在會上宣讀的大多數論文都發表在COMMUNICATIONS OF THE ACM1963年5月的刊物上，這些論文是當時技術發展水平的很好代表。