計算機排序演算法是誰發明

Ⅰ 求計算機專業中的十大演算法。。。qq827316329.。。。

不得不說，演算法沒有「十大」之類的東西的，不過的確有人對此進行過評選

《來自聖經的證明》收集了數十個簡潔而優雅的數學證明，迅速贏得了大批數學愛好者的追捧。如果還有一本《來自聖經的演算法》，哪些演算法會列入其中呢？最近，有人在 StackExchange 上發起了提問，向網友們徵集那些來自聖經的演算法。眾人在一大堆入圍演算法中進行投票，最終得出了呼聲最高的五個演算法：

第五名： BFPRT 演算法
1973 年， Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集體出動，合寫了一篇題為 「Time bounds for selection」 的論文，給出了一種在數組中選出第 k 大元素的演算法，俗稱"中位數之中位數演算法"。依靠一種精心設計的 pivot 選取方法，該演算法從理論上保證了最壞情形下的線性時間復雜度，打敗了平均線性、最壞 O(n^2) 復雜度的傳統演算法。一群大牛把遞歸演算法的復雜度分析玩弄於骨掌股掌之間，構造出了一個當之無愧的來自聖經的演算法。

第四名：快速排序
快速排序演算法是 1960 年由英國計算機科學家 C.A.R. Hoare 發明的，是一種既高效又簡潔的排序方法，現在已是學習演算法的必修內容之一。快速排序的思想並不復雜，妙就妙在那個線性的數據分割過程，而真正最牛 B 的則是對整個演算法的時間復雜度分析。我曾寫過一個快速排序平均 O(n log n) 的證明，分析過程絕對值得欣賞。

第三名：並查集
嚴格地說，並查集是一種數據結構，它專門用來處理集合的合並操作和查詢操作。並查集巧妙地借用了樹結構，使得編程復雜度降低到了令人難以置信的地步；用上一些遞歸技巧後，各種操作幾乎都能用兩行代碼搞定。而路徑壓縮的好主意，更是整個數據結構的畫龍點睛之筆。並查集的效率極高，單次操作的時間復雜度幾乎可以看作是常數級別；但由於數據結構的實際行為難以預測，精確的時間復雜度分析需要用到不少高深的技巧。

第二名： KMP 演算法
KMP 演算法是一種非常有效的字元串匹配演算法，它告訴了人們一個有些反直覺的事實：字元串匹配竟然能在線性時間里完成！整個演算法寫成代碼不足 10 行，但其中蘊含的天才般的奇妙思想讓演算法初學者們望而卻步，而它的復雜度分析則更是堪稱經典。

第一名：輾轉相除法
輾轉相除法是 Euclid 的《幾何原本》中提到的一種尋找兩個數的最大公因數的演算法。無論是簡潔的演算法過程，還是深刻的演算法原理，抑或是巧妙的復雜度分析，都稱得上是來自聖經的演算法。而擴展的輾轉相除法則構造性地證明了，對任意整數 a 和 b ，存在一對 x 、 y 使得 ax + by = gcd(a, b) 。這一結論的普遍性和實用性讓它成為了數論中的基本定理之一，在很多數學問題中都能看到它的身影。

Ⅱ 求排序演算法的發展史

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

Ⅲ 是的 計算機演算法

計算機演算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，演算法是對計算機上執行的計算過程的具體描述。
編輯本段演算法性質一個演算法必須具備以下性質： （1）演算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個演算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那麼它就不是正確的。 （2）演算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。 （3）每個步驟都有確定的執行順序，即上一步在哪裡，下一步是什麼，都必須明確，無二義性。 （4）無論演算法有多麼復雜，都必須在有限步之後結束並終止運行，即演算法的步驟必須是有限的。在任何情況下，演算法都不能陷入無限循環中。 一個問題的解決方案可以有多種表達方式，但只有滿足以上4個條件的解才能稱之為演算法。編輯本段重要演算法A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。
Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法，他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。
二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。
Branch and bound
分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。
數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。
Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。
Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。
動態規劃
動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。
歐幾里得演算法
在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
最大期望（EM）演算法
在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。
快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。
哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。
堆排序
Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。
歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。
RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。
並查集Union-find
並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。
Viterbi algorithm
尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。編輯本段演算法特點1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他是為有效演算法。 2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。 3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。 4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。 5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。編輯本段演算法與程序雖然演算法與計算機程序密切相關，但二者也存在區別：計算機程序是演算法的一個實例，是將演算法通過某種計算機語言表達出來的具體形式；同一個演算法可以用任何一種計算機語言來表達。 演算法列表 圖論 路徑問題 0/1邊權最短路徑 BFS 非負邊權最短路徑（Dijkstra） 可以用Dijkstra解決問題的特徵 負邊權最短路徑 Bellman-Ford Bellman-Ford的Yen-氏優化 差分約束系統 Floyd 廣義路徑問題 傳遞閉包 極小極大距離 / 極大極小距離 Euler Path / Tour 圈套圈演算法 混合圖的 Euler Path / Tour Hamilton Path / Tour 特殊圖的Hamilton Path / Tour 構造 生成樹問題 最小生成樹 第k小生成樹 最優比率生成樹 0/1分數規劃 度限制生成樹 連通性問題 強大的DFS演算法 無向圖連通性 割點 割邊 二連通分支 有向圖連通性 強連通分支 2-SAT 最小點基 有向無環圖 拓撲排序 有向無環圖與動態規劃的關系 二分圖匹配問題 一般圖問題與二分圖問題的轉換思路 最大匹配 有向圖的最小路徑覆蓋 0 / 1矩陣的最小覆蓋 完備匹配 最優匹配 穩定婚姻 網路流問題 網路流模型的簡單特徵和與線性規劃的關系 最大流最小割定理 最大流問題 有上下界的最大流問題 循環流 最小費用最大流 / 最大費用最大流 弦圖的性質和判定 組合數學 解決組合數學問題時常用的思想 逼近 遞推 / 動態規劃 概率問題 Polya定理 計算幾何 / 解析幾何 計算幾何的核心：叉積 / 面積 解析幾何的主力：復數 基本形 點 直線，線段 多邊形 凸多邊形 / 凸包 凸包演算法的引進，卷包裹法 Graham掃描法 水平序的引進，共線凸包的補丁 完美凸包演算法 相關判定 兩直線相交 兩線段相交 點在任意多邊形內的判定 點在凸多邊形內的判定 經典問題 最小外接圓 近似O(n)的最小外接圓演算法 點集直徑 旋轉卡殼，對踵點 多邊形的三角剖分 數學 / 數論 最大公約數 Euclid演算法 擴展的Euclid演算法 同餘方程 / 二元一次不定方程 同餘方程組 線性方程組 高斯消元法 解mod 2域上的線性方程組 整系數方程組的精確解法 矩陣 行列式的計算 利用矩陣乘法快速計算遞推關系 分數 分數樹 連分數逼近 數論計算 求N的約數個數 求phi(N) 求約數和 快速數論變換 …… 素數問題 概率判素演算法 概率因子分解 數據結構 組織結構 二叉堆 左偏樹 二項樹 勝者樹 跳躍表 樣式圖標 斜堆 reap 統計結構 樹狀數組 虛二叉樹 線段樹 矩形面積並 圓形面積並 關系結構 Hash表 並查集 路徑壓縮思想的應用 STL中的數據結構 vector deque set / map 動態規劃 / 記憶化搜索 動態規劃和記憶化搜索在思考方式上的區別 最長子序列系列問題 最長不下降子序列 最長公共子序列 一類NP問題的動態規劃解法 樹型動態規劃 背包問題 動態規劃的優化 四邊形不等式 函數的凸凹性 狀態設計 規劃方向 線性規劃 常用思想 二分 最小表示法 串 KMP Trie結構 後綴樹/後綴數組 LCA/RMQ 有限狀態自動機理論 排序 選擇/冒泡 快速排序 堆排序 歸並排序 基數排序 拓撲排序 排序網路
擴展閱讀：
1
《計算機演算法設計與分析導論》朱清新等編著人民郵電出版社
開放分類：
計算機，演算法

Ⅳ 計算機的演算法具有哪些特性

計算機的演算法具有可行性，有窮性、輸入輸出、確定性。

計算機演算法特點

1.有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效演算法。

2. 確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。

3. 有零個或多個輸入、所謂輸入是指在執行演算法是需要從外界取得必要的信息。

4. 有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。

5.有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。

拓展資料：

重要演算法

A*搜尋演算法

俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的NPC的移動計算，或線上游戲的BOT的移動計算上。該演算法像Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search

束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於人工智慧領域,1976 年Lowerre在其稱為HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法

一種在有序數組中查找某一特定元素的搜索演算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound

分支定界(branch and bound)演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮

數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商

Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法

迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹（Edsger Wybe Dijkstra）發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃

動態規劃是一種在數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法

在數學中，輾轉相除法，又稱歐幾里得演算法，是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

最大期望（EM）演算法

在統計計算中，最大期望（EM）演算法是在概率（probabilistic）模型中尋找參數最大似然估計的演算法，其中概率模型依賴於無法觀測的隱藏變數（Latent Variable）。最大期望經常用在機器學習和計算機視覺的數據聚類（Data Clustering）領域。最大期望演算法經過兩個步驟交替進行計算，第一步是計算期望（E），利用對隱藏變數的現有估計值，計算其最大似然估計值；第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。M 步上找到的參數估計值被用於下一個 E 步計算中，這個過程不斷交替進行。

快速傅里葉變換(FFT)

快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數

HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序

Heapsort是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序

Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法

RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法

這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經專利失效，其被廣泛地用於電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find

並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm

尋找最可能的隱藏狀態序列(Finding most probable sequence of hidden states)。

參考資料：計算機演算法

Ⅳ 羅伯特·弗洛伊德的人物簡介

（1936－2001）Robert W．Floyd
歷屆圖靈獎得主基本上都有高學歷、高學位，絕大多數有博士頭銜。這是可以理解的，因為創新型人才需要有很好的文化素養，豐富的知識底蘊，因而必須接受良好的教育。但事情總有例外，1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德就是一位「自學成才的計算機科學家」（a Self-Taught Computer Scientist）。
弗洛伊德1936年6月8日生於紐約。說他「自學成才」並不是說他沒有接受過高等教育，他是芝加哥大學的畢業生，但學的不是數學或電氣工程等與計算機密切相關的專業，而是文學，1953年獲得文學士學位。
20世紀50年代初期美國經濟不太景氣，找工作比較困難，因學習文學而沒有任何專門技能的弗洛伊德在就業上遇到很大麻煩，無奈之中到西屋電氣公司當了二年計算機操作員，在IBM650機房值夜班。我們知道，早期的計算機都是以批處理方式工作的，計算機操作員的任務就是把程序員編寫好的程序在卡片穿孔機（這是離線的輔助外部設備）上穿成卡片，然後把卡片疊放在讀卡機上輸入計算機，以便運行程序。因此，操作員的工作比較簡單，同打字員類似，不需要懂計算機，也不需要懂程序設計。但弗洛伊德畢竟是一個受過高等教育的人，又是一個有心人，幹了一段時間的操作員，很快對計算機產生了興趣，決心弄懂它，掌握它，於是他借了有關書籍資料在值班空閑時間刻苦學習鑽研，有問題就虛心向程序員請教。白天不值班，他又回母校去聽講有關課程。這樣，他不但在1958年又獲得了理科學士學位，而且逐漸從計算機的門外漢變成計算機的行家裡手。
1956年他離開西屋電氣公司，到芝加哥的裝甲研究基金會（Armour Research Foundation），開始還是當操作員，後來就當了程序員。1962年他被馬薩諸塞州的Computer Associates公司聘為分析員。此時與Warsall合作發布Floyd-Warshall演算法。1965年他應聘成為卡內基—梅隆大學的副教授，3年後轉至斯坦福大學。1970年被聘任為教授。
之所以能這樣快地步步高升，關鍵就在於弗洛伊德通過勤奮學習和深入研究，在計算機科學的諸多領域：演算法，程序設計語言的邏輯和語義，自動程序綜合，自動程序驗證，編譯器的理論和實現等方面都作出創造性的貢獻。其中包括：1962年，弗洛伊德完成了Algol 60編譯器的開發，成功投入使用，這是世界上最早的Algol 60編譯器之一，而且弗洛伊德在這個編譯器的開發中率先融入了優化的思想，使編譯所生成的目標代碼佔用空間少，運行時間短。弗洛伊德優化編譯的思想對編譯器技術的發展產生了深刻的影響。隨後，他又對語法分析進行了系統研究，優先文法（precedence grammar），限界上下文文法（bounded context grammar）等都是弗洛伊德在首先提出來的。優先文法解決了自底向上的語法分析中的首要任務：如何找到「句柄」，也就是當前需要進行歸約的符號串。弗洛伊德通過對不同的符號定義不同的優先順序，解決了這個問題。限界上下文文法則通過對上下文無關文法G中的兩個推導：
*
S→βArβαγ
+
S→δαε
進行比較以確定α是否是δαε的句柄，以及產生方式A→α是否是唯一可進行歸約的產生式。弗洛伊德經過研究，給出其充分必要條件為：β和δ的最後m個符號相同，丁和o/的最初n個終結符相同。這樣一個上下文無關文法G就稱為（m，n）限界上下文文法。
在演算法方面，弗洛伊德和威廉姆斯（J．Williams）在1964年共同發明了著名的堆排序演算法HEAPSORT，這是與英國學者霍爾 (C.A.R.Hoare，1980年圖靈獎獲得者）發明的QUICKSORT齊名的高效排序演算法之一。此外還有直接以弗洛伊德命名的求最短路的演算法，這是弗洛伊德利用動態規劃（dynamic programming）的原理設計的一個高效演算法。
在程序設計方面，計算機科學家非常關心的一個重要問題是如何表達和描述程序的邏輯，如何驗證程序的正確性。1967年，在美國數學會AMS舉行的應用數學討論會上，弗洛伊德發表了那篇引起轟動並產生了深遠影響的論文，即「如何確定程序的意義」（Assigning Meanings to Programs）。這篇論文在程序邏輯研究的歷史上，是繼麥卡錫（J．McCarthy，1971年圖靈獎獲得者）在1963年提出用遞歸函數作為程序的模型這一方法以後最重大的一個進展。
麥卡錫倡導的方法對於一般程序，包括大型軟體確實是行之有效的，但它有一個不足，即對於許多以命令方式編寫的軟體，其中包括賦值語句，條件語句，用While實現循環的語句……對這樣的程序用遞歸定義的函數去證明其正確性就很不方便了。正是為了解決這個問題，弗洛伊德在上述論文中提出了一種基於流程圖的表達程序邏輯的方法。這個方法的主要特點就是在流程圖的每一弧線上放置一個「標記」（tag），也就是一個邏輯斷言，並且保證只要當控制經過這個弧線時該斷言一定成立。弗洛伊德的主要貢獻在於解決了基於這種標記的形式系統的細節，證明了這種系統的完備性，解決了如何證明程序終結的問題。弗洛伊德還引入了驗證條件的概念，包括流程圖的一個組成部分（方框、圓框等）及其人口和出口處的標記。為了證明帶標記的流程圖的正確性，只要證明其中每一組成部分的驗證條件成立就行了。弗洛伊德提出的方法被叫做「歸納斷言法」（inctive assertion method），或前後斷言法（pre·and post-assertion method）。在框圖每個斷點i上所加的邏輯斷言即標記就叫i點的歸納斷言，說明程序執行經過此點時在各輸入變數x和各程序變數丁之間應存在的關系，以謂詞Pi(x,y）的形式表示。若程序從斷點i經過路段。到下一斷點j的驗證條件以Ra(x，y）表示，丁的值在。上的變化以ha(x，y）表示，則只要能證明下式恆真：
（∨x）（∨y）[pi(x,y）∧Ra(x,y) Pj(x,ha(x,y))]
程序從i到j的部分正確性也就證明了。
雖然用歸納斷言法不能證明程序的完全正確性，因為它必須以程序能夠終結為前提，但由於弗洛伊德在論文中同時也考慮了如何證明程序終結的問題，因此弗洛伊德的歸納斷言法也就有了普遍的意義。

Ⅵ 世界上最快的排序演算法

Timsort是一個自適應的、混合的、穩定的排序演算法，融合了歸並演算法和二分插入排序演算法的精髓，在現實世界的數據中有著特別優秀的表現。它是由Tim Peter於2002年發明的，用在Python這個編程語言裡面。這個演算法之所以快，是因為它充分利用了現實世界的待排序數據裡面，有很多子串是已經排好序的不需要再重新排序，利用這個特性並且加上合適的合並規則可以更加高效的排序剩下的待排序序列。

Ⅶ 堆排序的起源

1991年的計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發明了著名的堆排序演算法（ Heap Sort )