出版時間:2010-2 出版社:機械工業(yè)出版社 作者:鄒恒明 頁數(shù):292
Tag標簽:無
前言
起初神創(chuàng)造天地。地是空虛混沌,淵面黑暗;神的靈運行在水面上。神說:“要有光”。就有了光。神看光是好的,就把光與暗分開了。神稱光為晝,暗為夜。有晚上,有早晨,這是頭一日。 ……神就照著自己的形象造人, ……神說:“看哪!我將遍地上一切結(jié)種子的菜蔬,和一切樹上所結(jié)有核的果子,全賜給你們作食物。至于地上的走獸和空中的飛鳥,以及各樣爬在地上有生命的物,我將青草賜給它們作食物”。事就這樣成了。 神看著一切所造的都甚好。有晚上,有早晨,是第6日。天地萬物都造齊了。 圖1 米開朗基羅創(chuàng)作的西斯廷教堂穹頂畫《創(chuàng)世紀》。這幅畫里隱含著算法 6天 圣經(jīng)上寫著:神6天創(chuàng)造天地萬有,第7日安歇。 對于神創(chuàng)論者來說,這是不可懷疑的事實。但對于進化論者來說,6天創(chuàng)造一切根本就不可能。 作為一本算法書,我們當然不打算加入到神創(chuàng)論者和進化論者的永無休止的爭論當中去。我們關(guān)心的是這么一個問題:圣經(jīng)上為什么給出的是6天,而不是其他的時間長度。不管是神創(chuàng)論者還是進化論者,弄清楚6這個數(shù)字的來歷很可能會對己方的觀點有所幫助。在這6天里,神將他的創(chuàng)作方程式重復(fù)了6次,每天1次。對于全能的神來說,他完全可以在1天、1秒或者任何他所愿意的時間長度里創(chuàng)造天地萬物,但卻為什么是不多不少的6天呢?而不管圣經(jīng)上的 “1天”是多長,這個問題都是值得討論的。 我們知道,任何一個自然數(shù)的約數(shù)中都有1和它本身,而所有小于它本身的因數(shù)叫做這個自然數(shù)的真約數(shù)。例如,6的所有真約數(shù)是1、2、3;8的真約數(shù)是1、2、4。如果一個數(shù)的真約數(shù)之和等于這個自然數(shù)本身,則這個自然數(shù)就稱為完全數(shù),或者完美數(shù)。例如,6 = 1+2+3,因此6是完美數(shù);而8 ( 1+2+4,因此8不是完美數(shù)。因此,神6天創(chuàng)造世界,暗示著該創(chuàng)造是完美的! 以完美數(shù)來昭示創(chuàng)造的完美,似乎合情合理。但問題是,完美數(shù)只有6這一個數(shù)嗎?如果不是,為什么不使用其他的完美數(shù)呢?答案是,完美數(shù)雖然不止有6這一個,但確實數(shù)量稀少。一直到現(xiàn)在(2009年6月),數(shù)學家們探索了2600年,并且現(xiàn)代數(shù)學家們還借助了超級計算機,但也僅僅找到了47個完美數(shù)。其中第1個完美數(shù)是6,接下來的4個完美數(shù)分別是: 28、496、8128、33 550 336。而第47個完美數(shù)有25 956 377個數(shù)位,(注意,是數(shù)位,不是數(shù)值?。┧臄?shù)值為:243 112 608 × (243 112 609 ? 1)。 完美數(shù)的稀少昭示著達到完美的難度,而神選擇6天來創(chuàng)造天地萬有也許是因為6是最小的完美數(shù),即創(chuàng)造天地萬有對于神來說是輕而易舉的一件事情…… 完美與算法 完美數(shù)由于其各種神秘屬性(真約數(shù)之和等于自身只是其中的一個性質(zhì))而受到了特殊的關(guān)注。但到底哪些數(shù)是完美數(shù)則不是一件容易判斷的事情。顯然,按照完美數(shù)的定義,判斷一個數(shù)是否是完美數(shù)的不二法則是找出它的所有真約數(shù),然后求和看看其是否等于自身。然而這種方法效率太過低下,因為這意味著因式分解,而這是十分困難的(本書后面將會討論到這個問題)。 如果判斷一個數(shù)是否是完美數(shù)就已經(jīng)非常困難,那么要找出所有的完美數(shù)則更是一個難上加難的任務(wù)。因為這就意味著將所有的數(shù)進行上面描述的判斷驗證:因式分解。這似乎是人類不可能完成的任務(wù)。即使用世界上超大的計算機來進行計算,情況也不會有任何數(shù)量級的改善。 顯然,我們需要新的解決方案,而不是發(fā)明或使用新的計算工具!研究這樣的問題就可以歸結(jié)到算法的范疇里,因為如何高效地解決問題正是算法要研究的核心課題。 有意思的是,判斷和搜索完美數(shù)是算法的研究范疇,而算法本身的追求卻也是“完美”(見圖2)。 圖2 算法所追求的理想就是完美 算法無處不在 如果你覺得算法只是用來研究解決找出完美數(shù)之類的“漫無邊際的問題”,那就大錯特錯了。 也許算法這個名詞聽上去很抽象,讓人聯(lián)想不到任何具體的物體。也許你會覺得算法與自己的生活并無太多關(guān)系,它只不過存在于那些閑得無聊的數(shù)學家或計算機專業(yè)人士的腦海中。 但事實真是這樣嗎?當然不是。如果我們告訴你算法就是解決各種問題的方法,你就不會覺得它太抽象,與生活無關(guān)了吧。事實是,算法無處不在。每個人每天都在使用不同的算法來活出自己的人生,比如你去食堂買飯會選擇一個較短的隊列,而有人則可能選擇一個推進速度更快的隊列。每天起床后,你可能先讀一會兒書,再去吃早飯;另外一個人則可能先去吃早飯,然后讀書。所有這些行為都是算法或算法一部分的體現(xiàn)。也許運行這些算法并不在你的思想意識里,也許你并不知道算法在幫助著自己的生活,但它確實是存在的。這些算法也許沒有經(jīng)過精心設(shè)計,沒有經(jīng)過仔細分析,但它還是算法! 2009年7月23日下午,我在游覽云南省大理市的蝴蝶泉時由于泉水邊的石頭很滑,在用泉水洗手時(導游金花說用該泉水洗手會帶來好運)不慎滑落到蝴蝶泉水(見圖 3)里面,全身濕透。(據(jù)說一天至多只會有一個人滑落到泉里,可見本人運氣不錯!看來“蝴蝶泉邊好梳妝”的歌詞也許應(yīng)該改為“蝴蝶泉里好沖涼”。)泉水冰冷透涼,而大理的氣溫又低。這樣,我就面臨一個是否更換全身衣服的決定。問題是,旅游團需要馬上趕去登游船游覽洱海風光,而若找地方或者回旅店換衣服就將趕不上游船。 如何處理這件事情就是一個算法問題:是先上游船再在船上找地方換衣服,還是找個地方換衣服而放棄游覽蒼山洱海。顯然不同的算法有著不同的收益和代價。如果能夠在游船上找到合適的地方更換衣服,則采用先上游船再換衣服的算法為佳;否則就是放棄游覽的算法更好,因為如果凍病了顯然就不劃算了。最后,我選擇了在游船上更換衣服的算法:在游船上找到了一個貴賓室更衣。 圖3 在蝴蝶泉水下洗個手也會涉及算法 算法由問題驅(qū)動 算法的發(fā)現(xiàn)總是由相關(guān)的問題驅(qū)動的。拿排序來說,因為生活中到處都充滿次序,每個人都要接受自己在某個次序里的位置。比如,各種排名、評優(yōu)、民意調(diào)查等,最后的結(jié)果都體現(xiàn)為一個次序!看來,“沒有次序無以成方圓”并不是空穴來風!而談到排序用的方法,人們很自然地想到插入法,因為這種樸素的算法和人的思維方式非常類似:它就是人們打牌時整理手中撲克牌的算法。 但是隨著數(shù)據(jù)量的增大,插入排序的效率缺陷迅速變?yōu)槿藗儫o法容忍的缺點。于是人們發(fā)明了歸并排序、堆排序、快速排序等,這些排序的方法大大改善了速度,但是人們卻并不滿足于此。因此又發(fā)明了效率更高的線性排序。表1給出的是各種排序算法平均情況下的效率比較:最上面一行的數(shù)字代表輸入的規(guī)模,如10表示一共有10個數(shù)據(jù)項,1M表示一共有100萬個數(shù)據(jù)項。其他格子里面的數(shù)據(jù)為相應(yīng)算法在相應(yīng)輸入規(guī)模下完成排序所需要的時間,單位為毫秒。所有輸入數(shù)據(jù)為隨機產(chǎn)生。
內(nèi)容概要
本書追求的目標是算法背后的邏輯,是一本啟示書,而不是一本包羅萬象的算法大全。因此,本書甄選了那些最能夠展現(xiàn)算法思想、戰(zhàn)略和精華,并能夠有效訓練算法思維的內(nèi)容。本書將算法的討論分為五大部分:算法基礎(chǔ)篇、算法設(shè)計篇、算法分析篇、經(jīng)典算法篇、難解與無解篇。每一個部分分別討論算法的一大方面:基礎(chǔ)、設(shè)計、分析、經(jīng)典和難解問題。 本書既可以作為大學本科或研究生的算法教材或參考書,也可以作為對算法有興趣的讀者提升認知深度的讀物。
書籍目錄
前言第一篇 算法基礎(chǔ)篇 第1章 從無有到無窮 1.1 意念與現(xiàn)實 1.2 什么是算法 1.3 算法的表示 1.4 算法之魂 1.5 如何比較速度 1.6 算法與計算機的關(guān)系 1.7 算法的范疇 1.8 為什么學習算法 思考題 第2章 計數(shù)與漸近 2.1 算法的分析 2.2 計數(shù):算法分析的核心 2.3 算法設(shè)計 2.4 算法效率表示 2.5 漸近分析 2.6 O表示 2.7 最好、最壞、平均 2.8 O的另一類定義 2.9 O的性質(zhì) 2.10 要更快的計算機還是要更快的算法 思考題 第3章 分治與遞歸 3.1 分而治之為上策 3.2 分治策略 3.3 遞歸表達式求解 3.4 分治策略舉例1:乘方運算 3.5 生命不能承受之重:矩陣乘法 3.6 魔鬼序列:斐波那契序列 3.7 VLSI 布線 3.8 多項式乘法 3.9 分治就在潛意識深處 思考題 第二篇 算法設(shè)計篇 第4章 動態(tài)規(guī)劃思想 4.1 什么是動態(tài)規(guī)劃 4.2 流水裝配線問題 4.3 最長公共子序列 4.4 最長公共子序列變種 4.5 記憶遞歸法 4.6 空間效率改善 4.7 最優(yōu)二叉搜索樹 4.8 最優(yōu)子結(jié)構(gòu)與重疊子問題 4.9 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系 4.10 動態(tài)規(guī)劃與靜態(tài)規(guī)劃的相互轉(zhuǎn)換 思考題 第5章 貪婪選擇思想 5.1 僅有動態(tài)規(guī)劃是不夠的 5.2 什么是貪婪 5.3 背包問題 5.4 貪婪選擇屬性 5.5 教室規(guī)劃問題 5.6 最小生成樹 5.7 Prim算法 5.8 霍夫曼樹和霍夫曼編碼 5.9 貪婪選擇屬性 5.10 標準分治、動態(tài)規(guī)劃和貪婪選擇的比較 思考題 第6章 隨機化思想第三篇 算法分析篇 第7章 概率分析 第8章 攤銷分析 第9章 競爭分析第四篇 經(jīng)典算法篇 第10章 排序和次序 第11章 搜索與哈希 第12章 最短路徑第五篇 難解與無解篇 第13章 可解與不可解 第14章 NP完全問題 第15章 無解與近似結(jié)語 算法之道附錄 算法隨想?yún)⒖嘉墨I
章節(jié)摘錄
插圖:到目前為止,我們簡要論述了什么是算法、算法之魂、算法和計算機的關(guān)系及算法思維,讀者應(yīng)該體會到算法的重要性。但僅僅是因為算法重要就要學習它嗎?世界上有很多重要的東西,難道我們都要學嗎?即使是計算機專業(yè)的學生,不學算法也照樣可以編程寫軟件。那么,我們?yōu)槭裁匆獙W習算法呢?當然,我們有成千個理由要學,但這里僅給出幾個。首先,算法是計算機的靈魂。前面已經(jīng)說過,計算機不能獨立于算法而存在,或者說獨立于算法的計算機其存在價值要大打折扣。一個程序要完成一個任務(wù),其背后肯定要涉及算法的設(shè)計。實際上,程序就是算法的實現(xiàn),或者說程序是算法的外在體現(xiàn)。學好了算法,就能夠設(shè)計出更加有效的軟件,以最有效的方式完成更為復(fù)雜的功能。其次,算法是數(shù)學機械化的一部分,能夠幫助我們解決復(fù)雜的計算問題,其中有的問題就存在于我們的日常生活中。前面講過,算法無處不在。實際上,人是躲避不了算法的,每天的日常生活都會涉及算法。例如,如何分配自己的時間才能最有效地完成學習或工作任務(wù)就會涉及算法。不具備算法知識的人,分配的時候多半會源于自發(fā)、非科學的處理方法,難以達到高效。再次,算法作為一種思想,能鍛煉我們的思維,使思維變得更清晰、更有邏輯。算法是對事物本質(zhì)的數(shù)學抽象,看似深奧,卻體現(xiàn)著點點滴滴的樸素思想。雖然真理未必只有一個,但是只要你掌握了其中的一個,你就掌握了全部,這就像是NP完全問題一樣。因此,學會算法的思想,其意義不僅僅在算法本身,對日后的學習生活也會產(chǎn)生深遠的影響。
編輯推薦
《算法之道》:揭橥算法之道,求開智慧之門邏輯演繹、生活歸納、趣味交織、入木三分地揭示算法的奧妙。新的角度、新的分析、新的境界、耳目一新地闡述算法的精華?!端惴ㄖ馈芬匀碌慕嵌冉沂舅惴ǖ膴W秘,內(nèi)容囊括了所有重要的算法戰(zhàn)略和有獨特代表性的算法問題?!端惴ㄖ馈穼λ惴ǖ幕驹O(shè)計與分析戰(zhàn)略、高級設(shè)計戰(zhàn)略、高級分析戰(zhàn)略、經(jīng)典算法問題、難解與近似算法問題進行了深入的討論。書中選取的每個算法都在某個方面具有獨特性,能夠彰顯算法的精髓?!端惴ㄖ馈冯[含7個悖論和7個奧秘。如果能夠發(fā)現(xiàn)一二,你將獲得奇妙的感受?!端惴ㄖ馈酚腥缦聨讉€特點:啟示:深入探討算法背后的邏輯,對算法的剖析達到前所未有的境界。獨特:同樣的算法、相似的問題,選取不同的角度,幫助讀者理解到新的高度。簡潔:擯棄臃腫繁瑣的內(nèi)容堆砌,精選代表性的算法問題來彰顯算法的普遍邏輯。新穎:不同一般的章節(jié)組織使條理更為清晰,在內(nèi)容上引入部分清新的概念和定義。幽默:以講故事的形式將算法的精華娓娓道來,易于理解和消化。
圖書封面
圖書標簽Tags
無
評論、評分、閱讀與下載