函數式算法設計的藝術
萬琳 顧琳
- 出版商: 機械工業
- 出版日期: 2025-04-01
- 定價: $834
- 售價: 8.5 折 $709
- 語言: 簡體中文
- 頁數: 363
- ISBN: 7111775104
- ISBN-13: 9787111775102
- 此書翻譯自: Algorithm Design with Haskell
下單後立即進貨 (約4週~6週)
商品描述
本書專門介紹了算法設計的五項主要原則：分而治之、貪心算法、減而治之、動態規劃和窮舉搜索。這些原則是用Haskell這種純函數式語言來闡述的，與使用命令式語言相比，解釋更簡單，程序更短。書中還配有精心挑選的例子（既有新示例，也有標準示例），展示了算法之間的共性和差異。算法開發在適用的情況下使用等式推理，闡明適用性條件和正確性論證。每章最後都附有習題（共近300道），每道習題都有完整的答案，便於讀者鞏固理解，並將這些技術應用於一系列問題。 本書適用於計算機科學與技術及軟件工程相關專業學生（包括本科生和研究生）、研究人員、教師和專業人士，可以幫助他們進一步瞭解如何設計和實現優秀的算法，以及如何用純函數術語來表達這些算法。
作者簡介
理乍得·伯德(Richard Bird)牛津大學計算機實驗室的榮譽退休教授，牛津大學林肯學院的研究員。他的著述頗豐，包括《Algebra of Programming》(Prentice Hall，1996)和《Pearls Of Functional ALgorithm Design》(Cambridge University Press，2010）。
目錄大綱
譯者序
前言
第一部分 基礎知識
第1章 函數式編程
1.1 基本類型與函數
1.2 處理列表
1.3 歸納與遞歸的定義
1.4 融合
1.5 累積與串聯
章節註釋
參考文獻
練習
第2章 時間
2.1 漸近表示法
2.2 估計運行時間
2.3 上下文中的運行時間
2.4 均攤運行時間
章節註釋
參考文獻
練習
第3章 實用的數據結構
3.1 對稱列表
3.2 隨機訪問列表
3.3 數組
章節註釋
參考文獻
練習
第二部分 分而治之
第4章 二分查找
4.1 一維查找
4.2 二維查找
4.3 二叉搜索樹
4.4 動態集
章節註釋
參考文獻
練習
第5章 排序
5.1 快速排序
5.2 歸並排序
5.3 堆排序
5.4 桶排序及基數排序
5.5 排序總和
章節註釋
參考文獻
練習
第6章 選擇
6.1 最大和最小
6.2 單集合中的選擇
6.3 雙集合中的選擇
6.4 從補集中選擇
章節註釋
參考文獻
練習
第三部分 貪心算法
第7章 列表的貪心算法
7.1 通用貪心算法
7.2 貪心排序算法
7.3 硬幣兌換問題
7.4 TEX中的十進制小數
7.5 不確定性函數和精化
7.6 總結
章節註釋
參考文獻
練習
第8章 樹的貪心算法
8.1 最小高度樹
8.2 哈夫曼編碼樹
8.3 優先隊列
章節註釋
參考文獻
練習
第9章 圖的貪心算法
9.1 圖和生成樹
9.2 Kruskal算法
9.3 不相交集和聯合查找算法
9.4 Prim算法
9.5 單源最短路徑
9.6 Dijkstra算法
9.7 慢跑者問題
章節註釋
參考文獻
練習
第四部分 減而治之
第10章 簡化算法介紹
10.1 基本理論
10.2 分層網絡中的路徑
10.3 再論硬幣兌換
10.4 背包問題
10.5 一種通用的簡化算法
章節註釋
參考文獻
練習
第11章 片段和子序列
11.1 最長上升子序列
11.2 最長公共子序列
11.3 和最大子段
章節註釋
參考文獻
練習
第12章 劃分
12.1 劃分的生成方法
12.2 管理兩個銀行賬戶
12.3 段落問題
章節註釋
參考文獻
練習
第五部分 動態規劃
第13章 高效遞歸
13.1 兩個數字的例子
13.2 再論背包問題
13.3 最小代價編輯序列
13.4 再論最長公共子序列
13.5 穿梭巴士問題
章節註釋
參考文獻
練習
第14章 最佳劃分
14.1 立方時間覆雜度的算法
14.2 平方時間覆雜度的算法
14.3 覆雜度算法示例
14.4 單調性證明
14.5 最佳二叉搜索樹
14.6 GarsiaWachs算法
章節註釋
參考文獻
練習
第六部分 窮舉搜索
第15章 搜索方法
15.1 隱式搜索和n皇後問題
15.2 給定和的表達式
15.3 深度優先搜索與廣度優先搜索
15.4 登月問題
15.5 預先規劃
15.6 高峰時間問題
章節註釋
參考文獻
練習
第16章 啟發式搜索
16.1 樂觀啟發式搜索
16.2 單調啟發式搜索
16.3 倉庫導航
16.48 數碼問題
章節註釋
參考文獻
練習
附錄 練習答案
