演算法歷史

① 關於歷史時間演算法的!

公元紀年是指耶穌降生的那一年，這一年是公元1年【樓上錯了，沒有公元0年】，之前是公元前1年。
也就是說，公元前1年之後就是公元1年。
公元前的年代數字越大越早，公元後的不用說是數字越大越晚。
公元前幾世紀的演算法與公元後一樣，如：公元19世紀就是1800——1900。
這樣明白嘛？

② 最早的演算法是什麼，他的背景及來源

歐幾里得演算法被人們認為是史上第一個演算法。

歐幾里得演算法又稱輾轉相除法，用於計算兩個正整數a，b的最大公約數。

歐幾里得演算法產生的背景：
我們知道，約公元前300年，古希臘著名數學家歐幾里得在前人基礎上寫成的不配名著《幾何原本》，幾乎包括了中小學所學習的平面幾何、立體幾何的全部內容。如此古老的幾何內容，自然成了歷次數學課程改革關注的焦點。其中最為激進的，如法國布爾巴基學派主要人物狄奧東尼甚至喊出了「歐幾里得滾出去」的口號。但改來改去，歐氏幾何的一些內容，仍然構成了多數國家中小學數學幾何部分的主要內容。有人稱之為「不倒翁現象」。

③ 求排序演算法的發展史

對於今天排序技術的探索可以追溯到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月的刊物上，這些論文是當時技術發展水平的很好代表。

④ MPS演算法的發展歷史

1968年,聯合國公布SNA體系,並於1970年起在全世界推廣。
到上世紀八十年代中期,我國一直用的是MPS體系。 而日本的GDP演算法與中國不同,日本採用SNA演算法。

⑤ K平均演算法的發明歷史

k平均聚類發明於1956年， 該演算法最常見的形式是採用被稱為勞埃德演算法(Lloyd algorithm)的迭代式改進探索法。勞埃德演算法首先把輸入點分成k個初始化分組，可以是隨機的或者使用一些啟發式數據。然後計算每組的中心點，根據中心點的位置把對象分到離它最近的中心，重新確定分組。繼續重復不斷地計算中心並重新分組，直到收斂，即對象不再改變分組（中心點位置不再改變）。
勞埃德演算法和k平均通常是緊密聯系的，但是在實際應用中，勞埃德演算法是解決k平均問題的啟發式法則，對於某些起始點和重心的組合，勞埃德演算法可能實際上收斂於錯誤的結果。（上面函數中存在的不同的最優解）
雖然存在變異，但是勞埃德演算法仍舊保持流行，因為它在實際中收斂非常快。實際上，觀察發現迭代次數遠遠少於點的數量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的點集使得k平均演算法花費超多項式時間達到收斂。
近似的k平均演算法已經被設計用於原始數據子集的計算。
從演算法的表現上來說，它並不保證一定得到全局最優解，最終解的質量很大程度上取決於初始化的分組。由於該演算法的速度很快，因此常用的一種方法是多次運行k平均演算法，選擇最優解。
k平均演算法的一個缺點是，分組的數目k是一個輸入參數，不合適的k可能返回較差的結果。另外，演算法還假設均方誤差是計算群組分散度的最佳參數。

⑥ 輾轉相除法、更相減損法和秦九韶演算法的歷史

輾轉相除法,
又名歐幾里德演算法（Euclidean
algorithm），是已知最古老的演算法,
其可追溯至前300年。它首次出現於歐幾里德的《幾何原本》（第VII卷，命題i和ii）中
更相減損術,又稱"等值演算法"
，<九章算術>中介紹了這個方法,叫做」更相減損術」,數學家劉徽對此法進行了明確的註解和說明，成書時間在漢朝，先秦就開始編纂。
秦九韶是南宋數學家，所以是南宋。

⑦ 演算法的歷史

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

⑧ 誰能詳細說說Monte Carlo演算法的歷史

權權的《Monte Carlo方法》系列預告出來時我已注意到，但由於近來時間有限而直到今晚才有時間細讀了第一篇《積分方法》。總體而言寫得非常清楚，希望能夠堅持繼續下去。由於整個Bayesian統計學的根基就在Monte Carlo計演算法，我對這個領域一向很感興趣。但由於在研究工作中尚沒有機會使用Bayesian統計學，因此有關的知識都還屬間接經驗，能夠在本論壇探討這個話題肯定會受益。

在點評之前先推薦幾本參考資料，我相信下面這個書單是相當不錯的，可惜本人尚無時間深入鑽研：

* 對英文著作尚有心理障礙者可以參考一本出色的中文教科書：馮康先生所著《數
值計算方法》的第七章《蒙特卡洛方法》（國防工業出版社，1978）；

* 一本可讀性極強的英文專著，美國哈佛大學教授Jun Liu所著"Monte Carlo
Strategies in Scientific Computing" (Springer 2002);

* 對Monte Carlo方法在Bayesian統計學中的廣泛應用有興趣者可以適當參考
Andrew Gelman等人所著的"Bayesian Data Analysis" (Second Edition,
2003)之第三部分。

權權將貼子發在物理論壇的目的顯然是強調該方法在物理上的運用，我選擇在數學論壇加以點評是更看重其統計學背景，著重點各有不同。

>> 蒙特卡洛（Monte Carlo）是摩納哥公國一個城鎮，位於地中海沿岸，以其賭場和豪華
>> 酒店而聞名，所以就有了以隨機方法應用於數值計算的一類方法，被稱為Monte Carlo

有關Monte Carlo方法歷史背景的最精確描述來自Jun Liu的專著，他指出一批物理學家在二戰期間為估算薛定諤方程的本徵值而發明了一種基於統計抽樣的數值計演算法，其最初想法歸功於Ulam。後來Ulam的同事Metropolis將該方法命名為Monte Carlo。1950年代Metropolis和幾名統計物理學同事發表了一篇經典論文，提出了Markov Chain Monte Carlo(MCMC)演算法。而MCMC法後來是Bayesian統計學能夠不斷前進的主要動力。

>> I = ∫ f(x)p(x)dx

這里可以強調一下x是個矢量。而這個積分是概率統計中數學期望的基本定義，可以寫成E(f(x))。對於初學者而言，不要忘記概率密度函數p(x)的取值是可以大於1的，歸一化條件是對累積密度函數而言。

>> 上述變換就是Monte Carlo積分的基本精神，因為需要用到隨機抽樣，必然伴隨統計誤差。

需要用到隨機抽樣，其動機是想用數值模擬實驗中的頻率來直接估計一個概率值，而這個概率值是計算許多復雜高維積分的關鍵。而數值模擬需要產生一個序列的隨機數來保證抽樣過程的隨機性。

>> 因為x_i是按照概率密度p(x)分布的隨機變數，f(x_i)也是隨機變數

為了論述的清晰，應該說x_i是一個隨機矢量，那麼f(x_i)就是隨機變數（標量）。

>> 而中心極限定理告訴我們，一組獨立隨機變數之和的概率分布是高斯，其方差等於每一
>> 項隨機變數的方差之和

這里關於「中心極限定理」的表述不夠精確，容易引起讀者混淆，特將Kai-Lai Chung(鍾開萊，我國著名數理統計大師許寶祿先生的弟子)概率論教科書中的定義按我的理解方式用英文轉述一下：

[Central Limit Theorem] For mutually independent (or weakly correlated) random variables X_1, X_2, ..., X_n with mean mu and variance sigma^2,

√n ( Xbar - mu) / sigma --> N(0,1) in distribution,

where N(0,1) stands for standard Gaussian distribution. This means that the distribution shape of Xbar is more and more like a Gaussian random variable as n increases.

權權的中文表述中漏說了這組隨機變數必須來自同一個總體(population)這個重要條件，而且「是高斯」必須改成「在n不斷增大時趨向於高斯分布」。

>> 而計算高維積分時，Monte Carlo 方法是較優的選擇。

權權只從收斂速度的視角來說明Monte Carlo方法在高維情形下的優越性是不夠的，更關鍵的一點是---Monte Carlo模擬結果的精度和概型的維數D無關！結果的精度顯然比收斂速度更為重要，因此Monte Carlo方法特別適合求解高維問題。

另外要指出Monte Carlo方法以O(1/√N)的速度收斂，這在理論上已經無法改善。關鍵要在實際應用中通過巧妙設計模擬概型和改進抽樣方法來降低方差。降低方差的技巧是衡量各種Monte Carlo方法優劣的重要指標。

>> 不妨回顧一下布豐投針實驗來結束本篇，在分布著等距平行木紋的地板上投針，要求
>> 針的長度小於木紋之間的距離，幾何概形計算結果表明，針與一條木紋相交的概率可
>> 以用針的長度、木紋間距和圓周率π表示。而用幾何概形計算概率實質上歸結為面積的
>> 計算，也就是積分的計算，布豐投針實驗可以說是用隨機抽樣計算積分的始祖。

Buffon投針實驗看似簡單，其中蘊含的幾何概型思想值得細細品味。令針的長度為L，木紋間距為S，要求L < S。若針的中點到最近的一條平行線的距離為H，用a表示針與平行線的夾角。顯然有約束條件0 <= H <= S/2 和 0 <= a <= π。為了使針與平行線相交，必須滿足

H <= (L/2) sin(a)

這樣針與平行線相交的概率就是兩塊面積的比值：

p = ∫_0^π (L/2) sin(a) da / (π S/2 ) = 2L / (π S)

這就是權權所說「而用幾何概型計算概率實質上歸結為面積的計算，也就是積分的計算」。倘若上式分子中的積分是一個復雜的高維積分，我們就可以用Monte Carlo方法模擬出的p值來估算它。當然假如我們感興趣的是無理數π值的估算，那麼由上式可推出：

π_hat = lim 2L / (S p_n)

極限中的n趨向於正無窮。

希望權權在接下來的系列文章中能談到以下四種Monte Carlo抽樣方法：

* Crude Sampling
* Acceptance-Rejection Sampling
* Stratified Sampling
* Importance Sampling

若能談及MCMC類方法在統計物理學上的運用則更能引人入勝。

⑨ 公鑰演算法的歷史

密碼術有很長的歷史。古代人在沒有高速運算設備的條件下想盡了各種方法，也包含了許多巧妙的構思。早在公元前1900年，一個古埃及書寫員就在一個銘文中使用了非標準的象形文字，這是人類最早的有記錄的密碼術。其後，古代人使用的密碼術有如把字母表的順序顛倒過來、進行字母替代，或者用錯後一定數目的位置的字母替代前面的字母。其中有些密碼術的構思也是十分巧妙的。
現代密碼術的劃時代突破，是威特菲爾德;迪菲(Whitfield Diffie)和馬丁;海爾曼(Martin Hellman)有關公開密鑰加密系統的構想，這是在1976年發表的。但威特菲爾德;迪菲和馬丁;海爾曼提供的MH背包演算法於1984年被破譯，因而失去了實際意義。真正有生命力的公開密鑰加密系統演算法是由隆;里維斯特(Ronald L. Rivest)、阿迪;沙米爾(Adi Shamir)和雷奧納德;阿德爾曼(Leonard M.Adlemen)在威特菲爾德·迪菲和馬丁;海爾曼的論文的啟發下，在1977年發明的，這就是沿用至今的RSA演算法。它是第一個既能用於數據加密也能用於數字簽名的演算法。