數(shù)學算法能統(tǒng)治世界？
軟件正在統(tǒng)治世界，而軟件的核心是算法；互聯(lián)網(wǎng)即將統(tǒng)治世界，其管理、使用的核心也是算法；算法統(tǒng)治著軟件和互聯(lián)網(wǎng)，所以說“算法統(tǒng)治世界”這句話應是有一定道理的。
算法決定了你用Google搜索的結(jié)果，算法決定了新浪微博向你展示的話題，算法決定了Netflix向你推薦的電影，算法決定了你QQ對話窗彈出的橫幅廣告等等，這些都意味著“算法在統(tǒng)治世界”。
我們花費了大量時間、巨大的投資來研究新算法，調(diào)整、改善舊算法，尋找更好的算法以便集成到應用中去，但是有些現(xiàn)成的算法卻罕有人知曉，最后卻是“眾里尋她千百度，那人卻在燈火闌珊處”——往往答案就在眼前，但很多別人已經(jīng)研究多年的算法自己卻從未聽說過。這里，從千千萬萬算法中，整理出統(tǒng)治世界的十大算法的小型列表，排名不分先后，供參考。
哪個排序算法最好？這取決于需求，也是為什么要將歸并排序、快速排序和堆排序算法這三個使用頻率較高的排序算法置于一處的原因。你可能比較偏愛其中的一個，但它們都是同等重要的。
歸并排序算法是目前為止我們擁有的最重要的算法之一。它是一種基于比較的排序算法，使用分治法解決那些原本復雜度為O(N2)的問題。歸并排序是由數(shù)學家John von Neumann于1945年提出的。
快速排序是解決排序問題的另一種途徑，它使用就地分解算法，同時它也是一種分治算法。這個算法的問題在于它是不穩(wěn)定的排序算法，但它在基于內(nèi)存的數(shù)組排序上確實非常高效。
最后，堆排序算法使用一個優(yōu)先隊列降低數(shù)據(jù)的查找時間，它也是一種就地排序算法，同樣也是不穩(wěn)定的排序算法。
相較于曾經(jīng)使用的其他排序算法（如冒泡排序），上述算法帶來了顯著的改進。事實上，多虧了它們，今天我們才有了數(shù)據(jù)挖掘、人工智能、鏈接分析，以及世界上大部分的計算機工具，也包括網(wǎng)絡在內(nèi)。
整個數(shù)字世界都在使用這一簡單而又強大的算法，將信號從頻域轉(zhuǎn)換為時域，反之亦然。互聯(lián)網(wǎng)、你的WIFI、智能手機、電話、計算機、路由器、衛(wèi)星，幾乎所有內(nèi)置計算機的東西都會以各種方式使用這些算法實現(xiàn)各自的功能。
毫無夸張地說，如果沒有這個算法，當今互聯(lián)網(wǎng)將無法有效工作。這是一種圖搜索算法，它被廣泛應用在能夠建模為圖的問題中，用以找出兩個節(jié)點之間的最短路徑。
目前，即便我們已經(jīng)擁有了解決最短路徑問題的更好方法，Dijkstra算法依然在那些重視穩(wěn)定性的系統(tǒng)中得到應用。
如果沒有信息加密和網(wǎng)絡安全，互聯(lián)網(wǎng)不會像現(xiàn)在那么重要。在信息加密領(lǐng)域，有一個算法始終是世界上最重要的算法之一，它就是RSA算法。這個算法是由RSA公司的創(chuàng)始人建立，它使信息加密惠及千家萬戶，奠定了當今信息加密的運作基礎。RSA算法用來解決一個簡單而又復雜的問題：怎樣在不同平臺和終端用戶之間共享公鑰，繼而實現(xiàn)信息加密。其實，這個問題也沒完全解決，還需要做更多工作。
準確地說，它不能稱之為算法，它是美國國家標準暨技術(shù)學會定義的加密散列函數(shù)族中的一員，但是這族算法對整個世界的運作至關(guān)重要。從你的應用商店，你的郵件，你的殺毒軟件，到你的瀏覽器等等，所有這些都在使用安全哈希算法，它能判斷你是否下載了你想要的東西，也能判斷你是否是中間人攻擊或網(wǎng)絡釣魚攻擊的受害者。
這是在計算機領(lǐng)域被大量使用的數(shù)學算法，沒有這個算法，信息加密會更不安全。該算法定義了一系列步驟，得到將一合數(shù)分解為更小因子的質(zhì)數(shù)分解式。這被認為是一種FNP問題，它是NP分類問題的延伸，極其難以解決。
許多加密協(xié)議（如RSA算法）都基于這樣一個原理：對大的合數(shù)作因式分解是非常困難的。如果一個算法能夠快速地對任意整數(shù)進行因式分解，RSA的公鑰加密體系就會失去其安全性。
量子計算的誕生使我們能夠更容易地解決這類問題，同時它也打開了一個全新的領(lǐng)域，使得我們能夠利用量子世界中的特性來保證系統(tǒng)安全。
在互聯(lián)網(wǎng)時代，分析不同實體間的關(guān)系是相當重要的。從搜索引擎，社交網(wǎng)絡，到營銷分析工具，每個人都在不停尋找互聯(lián)網(wǎng)的真正結(jié)構(gòu)。
鏈接分析背后的理念非常簡單，以矩陣形式描繪出一張圖，將問題轉(zhuǎn)換為特征值問題。特征值是一種很好的渠道，它有助于展現(xiàn)圖的結(jié)構(gòu)以及每個節(jié)點的相對重要性。該算法是由Gabriel Pinski和Francis Narin于1976年建立的。
誰在使用這個算法？Google的Page Rank算法，F(xiàn)acebook向你展示的新聞提要（這就是為什么Facebook的新聞提要不是算法，只是使用算法的結(jié)果而已），Google 和Facebook的推薦，LinkedIn的工作和聯(lián)系人推薦，Netflix和Hulu的電影，YouTuBe的視頻，等等。雖然每個都有不同的目標和參數(shù)，但它們背后的數(shù)學理念是相同的。
你是否曾經(jīng)用過飛機、汽車、衛(wèi)星服務或手機網(wǎng)絡？你是否曾經(jīng)在工廠工作或是看見過機器人？如果回答是肯定的，那么你應該已經(jīng)見識過這個算法了。
大體上，這個算法使用一種控制回路反饋機制，將期望輸出信號和實際輸出信號之間的錯誤最小化。無論何處，只要你需要進行信號處理，或者你需要一套電子系統(tǒng)，用來自動化控制機械、液壓或熱力系統(tǒng)，這個算法都會有用武之地?？梢赃@樣說，如果沒有這個算法，現(xiàn)代文明將不復存在。
要判斷哪種數(shù)據(jù)壓縮算法最為重要是很困難的，因為它取決于不同的應用環(huán)境。它們可以應用在zip和mp3上，也可以應用在JPEG和MPEG-2上。但眾所周知，在所有結(jié)構(gòu)中這些算法都極其重要。
除了顯而易見的zip文件，在哪我們能夠找到這些算法？在電子游戲、視頻、音樂、數(shù)據(jù)存儲、云計算、數(shù)據(jù)庫等等地方都能找到這些算法?？梢哉f，數(shù)據(jù)壓縮算法處處可見，它們使系統(tǒng)成本更低、效率更高。
現(xiàn)在我們還沒有一個“真正的”隨機數(shù)生成器，但我們已經(jīng)有了一些偽隨機數(shù)生成器，這就夠用了。隨機數(shù)生成器的用途非常廣泛，從互聯(lián)聯(lián)絡、數(shù)據(jù)加密、安全哈希算法、電子游戲、人工智能、優(yōu)化分析，到問題的初始條件、金融等等，都有它們的身影。
最后再強調(diào)一下，上面這個列表僅供參考，它并不完整。因為在機器學習、矩陣乘法、分類化等領(lǐng)域也有一些算法，它們對我們的世界同樣重要，但在這里還沒有提到。
張建中，一個畢業(yè)于北京大學數(shù)學力學系，在中國科學院計算所、計算中心和網(wǎng)絡中心工作過，在澳大利亞科工組織DMS、香港浸會學院數(shù)學系和中國21世紀議程管理中心等處工作過，多次獲國家和中科院科技獎并享受政府特殊津貼的退休老頭。
另一篇：
影響計算機算法世界的十位大師
1、偉大的智者——Don E.Knuth，中文名：高德納
(1938-)算法和程序設計技術(shù)的先驅(qū)者。Oh,God！一些國外網(wǎng)站這樣評價他。一般說來，不知道此人的程序員是不可原諒的。其經(jīng)典著作《計算機程序設計藝術(shù)》更是被譽為算法中“真正”的圣經(jīng)，像KMP和LR(K)這樣令人不可思議的算法，在此書比比皆是。難怪連Bill Gates都說：“如果能做對書里所有的習題，就直接來微軟上班吧！”
對于Don E.Knuth本人，一生中獲得的獎項和榮譽不計其數(shù)，包括圖靈獎，美國國家科學金獎，美國數(shù)學學會斯蒂爾將（AMS Steel Prize），以及發(fā)明先進技術(shù)榮獲的極受尊重的京都獎（KyotoPrize）等等，寫過19部書和160余篇論文，每一篇著作都能用影響深遠來形容。 Don E.Knuth也被公認是美國最聰明的人之一。當年他上大學的時候，常寫些各種各樣的編譯器來掙外快，只要是他參加的編程比賽，總是第一名，同時也是世上 少有的編程達到40年以上的程序員之一。他除了是技術(shù)與科學上的泰斗外，更是無可非議的寫作高手，技術(shù)文章堪稱一絕，文風細膩，講解透徹，思路清晰而且沒 有學究氣，估計這也是《計算機程序設計藝術(shù)》被稱為圣經(jīng)的原因之一。
2、首席算法官Udi Manber
世界上還有如此奇怪的職位？但是對于Amazon乃至Google來說，這一點也不奇怪。Udi Manber，這位前Amazon的“首席算法官”，現(xiàn)在是Google負責工程事務的副總裁。他研究WWW的應用程序、搜索以及隱藏在這背后的算法設 計。在此期間，他與其他人共同開發(fā)了Agrep、Glimpse和Harvest等Unix上的搜索軟件。1998年，Udi成為了Yahoo!的首席科 學家。2002年，Amazon創(chuàng)造性地給了Udi“首席算法官”的職位，和Udi為Amazon的“SearchInside the Book”搜索項目所做的工作相得益彰。
Udi還因為他所著的Introduction to Algorithms——A Creative Approach而被大家稱道。
3、謙遜的長者——Edsger Wybe Dijkstra
1930年出生于荷蘭阿姆斯特丹，2002年逝世于荷蘭紐南。他在祖國荷蘭獲得數(shù)據(jù)和物理學學士，理論物理博士學位，2000年退休前一直是美國Texas大學的 計算機科學和數(shù)學教授。以發(fā)現(xiàn)了圖論中的最短路徑算法（Dijkstra算法）而聞名于世，1972年因為ALGOL第二代編程語言而獲得圖靈獎。“Go To StatementConsidered Harmful”(EWD215)也是被廣為傳頌的經(jīng)典之作。除了科學研究之外，他最喜歡做的事情就是教學，被人稱作“一天教學24小時”的教授。
且不說Dijkstra算法對計算科學，網(wǎng)絡科學發(fā)展的深遠影響，單從他在1972年獲得圖靈獎時的演講“The Humble Programmer”就不得不肅然起敬，在獲得計算機科學中至高無上的獎項時，Edgs Wybe Dijkstra仍然稱自己不過是一個謙遜普通的程序員，何等胸襟，舉世之中幾人可比。
4、運籌學大師——George Dantizig
可謂是由父親一手培養(yǎng)出的天才。George的父親是俄國人，曾在法國師從著名的科學家Henri Poincare。他曾經(jīng)這樣回憶自己的父親：“在我還是個中學生時，他就讓我做幾千道幾何題……解決這些問題的大腦訓練是父親給我的最好禮物。這些幾何 題，在發(fā)展我分析能力的過程中，起了最最重要的作用?！?/span>
在伯克利學習的時候，有一天George上課遲到，只看到黑板上寫著兩個問題，他只當是課堂作業(yè)，隨即將問題抄下來并做出解答。六個月后，這門課的老師——著名的統(tǒng)計學家Jerzy Neyman——幫助他把答案整理了一下，發(fā)表為論文，George這才發(fā)現(xiàn)自己解決了統(tǒng)計學領(lǐng)域中一直懸而未決的兩個難題。
George后來在運籌學建樹極高，獲得了包括“馮諾伊曼理論獎”在內(nèi)的諸多獎項。他在Linearprogramming and extensions一書中研究了線性編程模型，為計算機語言的發(fā)展做出了不可磨滅的貢獻。天妒英才，他于2005年5月13日去世。
5、推動時代前進的人——James Cooley
(1926-) 美國數(shù)學家，哥倫比亞大學的數(shù)學博士，以他所創(chuàng)造的快速傅立葉變換(FFT)而著名，不能不說是意義極其重大，F(xiàn)FT的數(shù)學意義不光在于使大家明白了傅立 葉(Fourier)變換計算起來是多么容易，而且使得數(shù)字信號處理技術(shù)取得了突破性的進展，對于現(xiàn)在的網(wǎng)絡通信，圖形圖像處理等等領(lǐng)域的發(fā)展與前進奠定 了基礎。Fourier變化的意義在于將電能變?yōu)榱斯I(yè)的命脈，而FFT的意義更是在于他推動了整個社會信息化的進程。在IBM研究中心中主要從事數(shù)字信 號處理的研究一直到1992年退休，同時他還是IEEE的數(shù)字信號處理委員會的成員。1980年獲得ASSP’s Meritorious Service Award,1984年獲得ASSP Society Award以及IEEE Centennial Medal。
6、FORTRAN 之父——John Backus
早年在Hill School學習的時候因為討厭學習，成績一踏糊涂而不得不在暑假補課。1943年他在父親的要求下到維吉尼亞大學學習化學，隨后參軍、照顧頭部受傷的傷 員、在醫(yī)學學校學習治療，可是最后又都放棄了。不過還好，戰(zhàn)后Backus進入紐約哥倫比亞大學學習數(shù)學，并于1949年畢業(yè)。在畢業(yè)前夕，他跑到了麥迪 遜大街的IBM計算機中心參觀。事情湊巧，和導游聊天的時候Backus談到自己正在找工作，在導游的鼓勵下，他和中心一位主管的面談，成為了一名 IBM?的程序員。
在IBM，Backus的才華得到了施展，發(fā)明了人類歷史上第一個高級語言——FORTRAN。接著，又提出了規(guī)范描述編程語言語法的BNF。這位當年的“差生”終于被整個計算機世界肯定——美國計算機協(xié)會于1977年授予John Backus圖靈獎。
7、實踐探索先鋒——Jon Bentley
1974年獲得了斯坦福大學的學士學位，1976年獲得北卡羅萊納大學的碩士和博士學位。畢業(yè)后在卡耐基梅隆大學教授了6年計算機科學課程，1982年進入貝爾實 驗室。2001年退休后加入了現(xiàn)在的Avaya實驗室，他還曾作為訪問學者在西點軍校和普林斯頓大學工作。他的研究領(lǐng)域包括編程技術(shù)、算法設計、軟件工具 和界面設計等等。
他寫作過三本編程書籍，其中最著名的就是涵蓋從算法理論到軟件工程各種主題的Programming Pearls(《編程珠璣》)，這其實是他發(fā)表過的文章的合集。在這些文章里，Jon從工程實現(xiàn)的角度出發(fā)，為程序員們提供了一個個艱難問題的解決方案， 猶如一顆顆閃閃發(fā)亮的珍珠。Bentley的珍珠超出了可靠工程學的范疇，利用他的洞察力和創(chuàng)造力為那些惱人的問題提供了獨特而巧妙的解決方案。
8、Pascal之父——Nicklaus Wirth
如果說有一個人因為一句話而得到了圖靈獎，那么這個人應該就是NicklausWirth，這句話就是他提出的著名公式“算法+數(shù)據(jù)結(jié)構(gòu)=程序”。這個公式對計算機科學的影響程度足以類似物理學中愛因斯坦的“E=MC^2”——一個公式展示出了程序的本質(zhì)。
Nicklaus Wirth，1934年出生于瑞士，1963年在加州大學伯克利分校取得博士學位。取得博士學位后直接被以高門檻著稱的斯坦福大學聘到剛成立的計算機科學 系工作。在斯坦福大學成功的開發(fā)出Algol W以及PL360后，愛國心極強的Nicklaus Wirth于1967年回到祖國瑞士，第二年在他的母校蘇黎世工學院他創(chuàng)建與實現(xiàn)了Pascal語言——當時世界上最受歡迎的語言之一。 后來他的學生Philipe Kahn畢業(yè)后和Anders Hejlsberg(Delphi之父)創(chuàng)辦了Borland公司靠Turbo Pascal起家，很快成為了將Borland發(fā)展成為全球最大的開發(fā)工作廠商，這一切都不得不說要歸工于PASCAL語言的魅力。PASCAL已經(jīng)影響 了整整幾代的程序員，Nicklaus Wirth的思想還將會繼續(xù)指引現(xiàn)在和以后的程序員前進的方向。
9、算法的講解者——Robert Sedgewick
是普林斯頓大學的計算機科學教授。他還是Adobe Systems的一名主管，也曾作為訪問學者在Xerox PARC、IDA和INRIA工作。他在斯坦福大學獲得博士學位。他的著作包括Algorithm in C、Algorithm in C++、Algorithm in Java等系列書籍，這些都再版多次。“沒有人能夠?qū)⑺惴ê蛿?shù)據(jù)結(jié)構(gòu)解釋得比Robert Sedgewick更清楚易懂了！”很多讀過他著作的程序員這樣說。
目前Robert正在研究算法設計、數(shù)據(jù)結(jié)構(gòu)、算法分析等方面的基礎理 論。他善于通過數(shù)學方法評估和預測算法性能，設法發(fā)現(xiàn)算法、數(shù)據(jù)結(jié)構(gòu)的通用機制，例如使用逼近方法尋找更快速更高效的算法。另外，他還將算法和圖形學結(jié)合 起來，例如使用可視化方法評估算法效率，算法的圖形化模擬，用于出版物的高質(zhì)量算法表現(xiàn)方法等等。
10、計算機領(lǐng)域的爵士——Tony Hoare
1934年出生于英國，1959年博士畢業(yè)于俄羅斯莫斯科國立大學，獲得語言機器翻譯專業(yè)學士學位。1960年發(fā)布了使他聞名于世的快速排序算法（Quick Sort），這個算法也是當前世界上使用最廣泛的算法之一。
Tony Hoare在取得博士學位后，就職于Elliott Brothers，領(lǐng)導了Algol 60第一個商用編譯器的設計與開發(fā)，由于其出色的成績，最終成為該公司首席科學家。從1977年開始，Tony Hoare博士任職于牛津大學，投身于計算系統(tǒng)的精確性的研究、設計及開發(fā)。因其對Algol 60程序設計語言理論、互動式系統(tǒng)及APL的貢獻，1980年被美國計算機協(xié)會授予“圖靈獎”。
1999年在牛津大學退學后，Tony Hoare博士被微軟劍橋研究院聘請擔任高級程序員，從事微軟劍橋研究院研究生成果的工業(yè)化應用的工作，以及協(xié)助其它研究人員進行服務于軟件產(chǎn)業(yè)及用戶的長期基礎研究項目。2000年因為其在計算機科學與教育上做出的貢獻被封為爵士。
