函數(shù)式算法設(shè)計的藝術(shù) [英] 理查德·伯德 [英]杰里米·吉本斯
定 價:139 元
叢書名:程序員書庫
當前圖書已被 3 所學校薦購過!
查看明細
- 作者:[英] 理查德·伯德 [英]杰里米·吉本斯
- 出版時間:2025/4/1
- ISBN:9787111775102
- 出 版 社:機械工業(yè)出版社
- 中圖法分類:TP312
- 頁碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
本書介紹了算法設(shè)計的五個主要原則:分治法、貪婪算法、稀疏、動態(tài)程序設(shè)計和窮舉搜索。讓學生、教師、研究人員和專業(yè)人員更好地了解一個好的算法是如何組成的,以及如何用純函數(shù)的形式表達這些算法。
本書專門介紹了算法設(shè)計的五項主要原則:分而治之、貪心算法、減而治之、動態(tài)規(guī)劃和窮舉搜索。這些原則是用Haskell這種純函數(shù)式語言來闡述的,與使用命令式語言相比,解釋更簡單,程序更短。書中還配有精心挑選的例子(既有新示例,也有標準示例),展示了算法之間的共性和差異。算法開發(fā)在適用的情況下使用等式推理,闡明適用性條件和正確性論證。每章最后都附有習題(共近300道),每道習題都有完整的答案,便于讀者鞏固理解,并將這些技術(shù)應(yīng)用于一系列問題。本書適用于計算機科學與技術(shù)及軟件工程相關(guān)專業(yè)學生(包括本科生和研究生)、研究人員、教師和專業(yè)人士,可以幫助他們進一步了解如何設(shè)計和實現(xiàn)優(yōu)秀的算法,以及如何用純函數(shù)術(shù)語來表達這些算法。
譯者序
如果真有一門絕世武功,“招式”和“內(nèi)功”孰輕孰重?如果說這個問題真有答案,那么在我講授C語言程序設(shè)計多年之后,開始與本書相遇相知時似乎逐漸找到了。
長久以來,函數(shù)式編程因為側(cè)重原理而被認為更接近于“內(nèi)功”。由于某些情況下的性能問題以及學習資料的缺乏,函數(shù)式編程一直沒有成為主導。近年來,計算機硬件性能的提升帶來了轉(zhuǎn)機,我們看到舊語言逐漸引入函數(shù)式的特性、新語言在構(gòu)建之初就考慮更多函數(shù)式的設(shè)計。
在這本書里,當分而治之、貪心算法、減而治之、動態(tài)規(guī)劃、窮舉搜索這些算法用Haskell純函數(shù)式語言來實現(xiàn)時,簡短的代碼體現(xiàn)出了科學思想與工程優(yōu)雅。外化于形、內(nèi)化于心的交相輝映令人沉醉!無論對于Haskell程序設(shè)計,還是對于C語言程序設(shè)計,“招式”和“內(nèi)功”的兼收并蓄都是一個更高的境界!
本書的作者是牛津大學的Richard Bird和Jeremy Gibbons教授。令人遺憾的是,Richard Bird教授在2022年4月4日離開了我們,他一生致力于推廣函數(shù)式編程,對算法和程序設(shè)計做出了偉大貢獻。在翻譯這本書的過程中,我深感他文字之魅力和思想之深邃。大家在閱讀此書時產(chǎn)生不同編程思維碰撞的電光火石是對Richard最好的緬懷。
萬琳
前言
本書的目的是使用純函數(shù)方法來介紹算法設(shè)計的原理。我們選擇的語言是Haskell,所以我們設(shè)計的所有算法都將用Haskell函數(shù)來表示。Haskell有很多結(jié)構(gòu)化函數(shù)定義的特性,但是我們只會使用其中的一小部分。
使用函數(shù)代替循環(huán)和賦值語句來表達算法會改變一切。首先,以函數(shù)形式表達的算法會由其他更基本的函數(shù)組成,而這些基本函數(shù)可以被單獨研究并重用在其他算法中。例如,排序算法可以通過構(gòu)建并使用某種樹的結(jié)構(gòu)來實現(xiàn),而我們可以將構(gòu)建樹的函數(shù)與使用樹的函數(shù)分開研究。此外,可以使用簡單的等式屬性來捕獲這些基本函數(shù)中每個函數(shù)的特性以及它們與其他函數(shù)的關(guān)系。在此基礎(chǔ)上,人們可以用一種命令式代碼不容易實現(xiàn)的方式來探討和推理算法的“深度”結(jié)構(gòu)�?梢钥隙ǖ氖�,我們可以通過在謂詞演算中形式化命令程序的規(guī)范并使用循環(huán)不變式來證明它們是正確的,從而對命令程序進行形式化推理。但這同時也是函數(shù)式編程的關(guān)鍵所在,即不能輕松地直接根據(jù)命令代碼的語言來推斷命令式程序的屬性。因此,關(guān)于形式化程序設(shè)計的書與關(guān)于算法設(shè)計的書有很大的不同:它們要求人們精通謂詞演算和必要的命令性術(shù)語。相比之下,許多關(guān)于算法設(shè)計的書通常都會對算法進行逐步介紹,并使用非形式化陳述的循環(huán)不變式來幫助人們理解為什么算法是正確的。
函數(shù)式編程使得我們不再需要考慮兩種獨立的語言,可以通過簡單的等式推理過程愉快地計算出更好的算法版本,或算法的一部分,而這也許就是本書的主要貢獻。盡管本書包含了相當多的等式推理,但我們會盡量簡化以保證閱讀體驗。實際情況往往是,計算做起來很有趣,但大量的公式讀起來會很無聊。盡管命令式算法是用C、Java還是偽代碼來表示并不是很重要,但如果用函數(shù)式來表示算法,那情況就完全不同了。
本書討論的許多問題,特別是在后面的部分中,都會從任務(wù)的規(guī)范開始,表示為標準函數(shù)的組合,如映射、過濾器和折疊,以及其他函數(shù),如用于計算列表所有排列的perms、用于計算所有分區(qū)的parts和用于構(gòu)建特定種類的樹的mktrees。然后以各種方式將這些組件函數(shù)進行組合或融合,以構(gòu)建具有所需時間復(fù)雜性的最終算法。最終排序算法可能不會涉及底層樹,但是樹仍然存在于算法的結(jié)構(gòu)中。融合的概念主導了設(shè)計過程的技術(shù)和數(shù)學方面,同時也是這本書真正的驅(qū)動力。
對于任何采用函數(shù)式方法的作者來說,像Haskell這樣的函數(shù)式語言的缺點是,它們不像主流的過程式語言那樣廣為人知,所以必須花時間來解釋它們。這也會大大增加本書的篇幅。這個問題的簡單解決辦法就是假設(shè)讀者已經(jīng)掌握了必要的知識。關(guān)于Haskell等語言的教材越來越多,包括我們自己的Thinking Functionally with Haskell(劍橋大學出版社,2014),我們假設(shè)讀者已經(jīng)讀過相關(guān)內(nèi)容。事實上,這本書是作為前一本書的姊妹篇設(shè)計的。在第1章中,我們會簡要概述我們的假設(shè),并簡要回顧一些基本思想,但是你可能無法從第1章了解到足夠的Haskell知識來理解本書其余部分的內(nèi)容。即使你對函數(shù)式編程有所了解,但并不了解等式推理是如何進入這一領(lǐng)域的(一些關(guān)于函數(shù)式編程的書籍根本就沒有提到等式推理),你可能仍然需要參考我們的前一本書。在任何情況下,等式推理所涉及的數(shù)學既不新鮮,也不算困難。
關(guān)于算法設(shè)計的書籍傳統(tǒng)上涵蓋3個廣泛的領(lǐng)域:設(shè)計原則的集合、有用數(shù)據(jù)結(jié)構(gòu)的研究,以及幾個世紀以來發(fā)現(xiàn)的一些有趣的算法。有時這些書的內(nèi)容是按照原則組織的,有時是按照主題(如圖算法,或文本算法)組織的,有時是混合使用兩種方式。本書主要采用第一種方法,專注于許多有效算法背后的五大主要設(shè)計策略:分而治之、貪心算法、減而治之、動態(tài)規(guī)劃和窮舉搜索。這些是每個認真的程序員都應(yīng)該知道的設(shè)計策略。其中減而治之這一策略較為新穎,并在許多問題中被視為動態(tài)規(guī)劃的替代方案。
在本書中,每種設(shè)計策略都有專門一部分與之對應(yīng),每部分都涵蓋相關(guān)策略的各種已知算法和新算法。本書沒有過多介紹數(shù)據(jù)結(jié)構(gòu)方面的內(nèi)容,雖然在本書的第一部分中,我們會討論一些基本的數(shù)據(jù)結(jié)構(gòu),但我們將結(jié)合一些實用的Haskell數(shù)據(jù)結(jié)構(gòu)庫進行介紹。這樣做的一個原因是我們希望控制這本書的篇幅,另一個原因是Chris Okasaki的著作Purely Functional Data Structures(劍橋大學出版社,1998)已涵蓋大量相關(guān)內(nèi)容。自我們開始寫這本書以來,其他關(guān)于函數(shù)式數(shù)據(jù)結(jié)構(gòu)的書籍已經(jīng)相繼出版,更多的相關(guān)書籍也在籌備之中。
本書的另一個特點是,不僅描述了一些受歡迎的算法,還描述了一些通常不會出現(xiàn)在算法設(shè)計類書籍中的算法。其中一些算法改編自Pearls of Functional Algorithm Design(2010)。引入這些新穎的算法是為了讓這本書更加有趣,同時也更有教育意義。一般來說,有三種人會閱讀算法設(shè)計方面的書籍:需要參考資料的學者、正在學門課程的本科生或研究生,以及對算法感興趣的專業(yè)程序員。大多數(shù)專業(yè)程序員并不設(shè)計算法,而只是從庫中獲取它們。盡管如此,他們也是本書的目標讀者,因為有時專業(yè)程序員會想了解更多關(guān)于構(gòu)建優(yōu)秀算法的方法和思路。
現(xiàn)實生活中的算法要比這本書中介紹的復(fù)雜得多。衛(wèi)星導航系統(tǒng)中的最短路徑算法也比算法設(shè)計教材中的最短路徑算法復(fù)雜得多�,F(xiàn)實生活中的算法必須處理規(guī)模問題,有效地使用計算機硬件、用戶界面,并考慮許多其他與設(shè)計良好且實用的產(chǎn)品相關(guān)的因素。本書不會涉及這些方面的內(nèi)容,實際上,大多數(shù)專門討論算法設(shè)計原則的書也不會涉及這些方面的內(nèi)容。
本書還有一個值得一提的特點:所有的練習都附有答案,即使有的答案比較簡短。練習是本書的重要組成部分,即使不做練習,也要閱讀問題和答案。本書沒有在全書的最后提供完整的參考書目,而是在每一章的結(jié)尾列出與該章相關(guān)的一些書籍和文章等參考文獻。
本書的大部分主要程序都可以在網(wǎng)站www.cs.ox.ac.uk/publications/books/adwh上找到。你還可以通過這個網(wǎng)站查看勘誤表,并報告新的錯誤。我們也歡迎讀者提出改進建議,包括有關(guān)新練習的想法。
致謝
本書的編寫得益于Sue Gibbons、HsiangShang Ko與 Nicolas Wu的仔細審閱。手稿是使用Ralf Hinze和Andres Lh的lhs2TEX系統(tǒng)編寫的,該系統(tǒng)完美地呈現(xiàn)了Haskell代碼,并允許進行提取和類型檢查。然后我們使用Koen Claessen和John Hughes開發(fā)的QuickCheck工具對提取的代碼進行測試。代碼的類型檢查和快速檢查幫我們減少了許多錯誤,當然,限于作者水平,書中疏漏在所難免,任何遺留的錯誤都是我們自己的責任。
我們也要感謝劍橋大學出版社的David Tranah和他的團隊,他們的建議和辛勤工作促成了本書的最終出版。
Richard BirdJeremy Gibbons
理查德·伯德(Richard Bird)牛津大學名譽教授,著有多部廣受好評的Haskell相關(guān)書籍,包括《Haskell函數(shù)式程序設(shè)計》和《函數(shù)式算法設(shè)計珠璣》。
杰里米·吉本斯(Jeremy Gibbons)牛津大學計算機科學教授,在該校教授軟件工程非全日制專業(yè)碩士課程。他是Journal of Functional Programming的聯(lián)合主編、IFIP Working Group 2.1 on Algorithmic Languages and Calculi的前任主席以及ACM SIGPLAN的前任副主席。
譯者序
前言
第一部分基礎(chǔ)知識
第1章函數(shù)式編程
11基本類型與函數(shù)
12處理列表
13歸納與遞歸的定義
14融合
15累積與串聯(lián)
章節(jié)注釋
參考文獻
練習第2章時間
21漸近表示法
22估計運行時間
23上下文中的運行時間
24均攤運行時間
章節(jié)注釋
參考文獻
練習第3章實用的數(shù)據(jù)結(jié)構(gòu)
31對稱列表
32隨機訪問列表
33數(shù)組
章節(jié)注釋
參考文獻
練習第二部分分而治之
第4章二分查找
41一維查找
42二維查找
43二叉搜索樹
44動態(tài)集
章節(jié)注釋
參考文獻
練習第5章排序
51快速排序
52歸并排序
53堆排序
54桶排序及基數(shù)排序
55排序總和
章節(jié)注釋
參考文獻
練習第6章選擇
61最大和最小
62單集合中的選擇
63雙集合中的選擇
64從補集中選擇
章節(jié)注釋
參考文獻
練習
第三部分貪心算法
第7章列表的貪心算法
71通用貪心算法
72貪心排序算法
73硬幣兌換問題
74TEX中的十進制小數(shù)
75不確定性函數(shù)和精化
76總結(jié)
章節(jié)注釋
參考文獻
練習第8章樹的貪心算法
81最小高度樹
82哈夫曼編碼樹
83優(yōu)先隊列
章節(jié)注釋
參考文獻
練習第9章圖的貪心算法
91圖和生成樹
92Kruskal算法
93不相交集和聯(lián)合查找算法
94Prim算法
95單源最短路徑
96Dijkstra算法
97慢跑者問題
章節(jié)注釋
參考文獻
練習
第四部分減而治之
第10章簡化算法介紹
101基本理論
102分層網(wǎng)絡(luò)中的路徑
103再論硬幣兌換
104背包問題
105一種通用的簡化算法
章節(jié)注釋
參考文獻
練習第11章片段和子序列
111最長上升子序列
112最長公共子序列
113和最大子段
章節(jié)注釋
參考文獻
練習第12章劃分
121劃分的生成方法
122管理兩個銀行賬戶
123段落問題
章節(jié)注釋
參考文獻
練習
第五部分動態(tài)規(guī)劃
第13章高效遞歸
131兩個數(shù)字的例子
132再論背包問題
133最小代價編輯序列
134再論最長公共子序列
135穿梭巴士問題
章節(jié)注釋
參考文獻
練習第14章最佳劃分
141立方時間復(fù)雜度的算法
142平方時間復(fù)雜度的算法
143復(fù)雜度算法示例
144單調(diào)性證明
145最佳二叉搜索樹
146GarsiaWachs算法
章節(jié)注釋
參考文獻
練習第六部分窮舉搜索
第15章搜索方法
151隱式搜索和n皇后問題
152給定和的表達式
153深度優(yōu)先搜索與廣度優(yōu)先搜索
154登月問題
155預(yù)先規(guī)劃
156高峰時間問題
章節(jié)注釋
參考文獻
練習第16章啟發(fā)式搜索
161樂觀啟發(fā)式搜索
162單調(diào)啟發(fā)式搜索
163倉庫導航
1648數(shù)碼問題
章節(jié)注釋
參考文獻
練習附錄練習答案