AI及機器學習的經脈：演算法新解 pdf epub mobi txt 電子書 下載 2025

簡體網頁||繁體網頁

☆☆☆☆☆

圖書標籤:

• 人工智能
• 機器學習
• 算法
• 深度學習
• 數據科學
• 神經網絡
• 模式識彆
• 理論基礎
• 技術創新
• 算法解讀

演算法不僅可用來解決現實世界中的種種實際問題，如透過關鍵字尋找網上最有用的資訊，尋找最短的旅遊路綫來遊曆所有的景點，再比如無綫通訊中的通道編碼和解碼；很多美妙的演算法源於人類對一些挑戰自身智力的謎題的思考，比如經典的華容道問題，尋找數獨的解法，再比如用程式戰勝九段圍棋高手等。書中的這些謎題深刻卻不枯燥，它適閤也值得任何學術背景的人花時間閱讀和思考。使用和發現演算法是快樂的，這也是本書特彆美好之處。畢竟人類的最高階段就是認識宇宙，瞭解生命起源，而更高階段是創造和優雅地解決那些有趣的謎題！

　　本書同時用函數式方法和傳統方法介紹主要的基本演算法和資料結構，資料結構部分包括二元樹、紅黑樹、AVL樹、Trie、Patricia、後綴樹、B樹、二元堆積、二項式堆積、斐波那契堆、Pairing堆、佇列、序列等；基本演算法部分包括各種排序演算法、序列搜索演算法，字串匹配演算法（KMP等），深度優先、廣度有限搜索演算法、貪心演算法及動態規劃。
 

作者簡介

劉新宇

　　1999年和2001年分彆獲得清華大學自動化係學士和碩士學位，之後長期從事軟體研發工作。關注基本演算法和資料結構，尤其是函數式演算法，目前任職於亞馬遜中國倉儲和物流技術團隊。
 

前言

第一部分  樹
01 二元搜尋樹：資料結構中的「hello world」
1.1 定義.
1.2 資料組織
1.3 插入
1.4 檢查.
1.5 搜索
1.6 刪除.
1.7 隨機建置二元搜尋樹
02 插入排序的進化.
2.1 簡介
2.2 插入
2.3 改進一：二分尋找
2.4 改進二：使用鏈結串列
2.5 使用二元搜尋樹的最後改進
2.6 小結
03 並不復雜的紅黑樹
3.1 紅黑樹的定義
3.2 插入
3.3 刪除
3.4 指令式的紅黑樹演算法
3.5 小結
04 AVL 樹
4.1 AVL樹的定義
4.2 插入
4.3 刪除
4.4 AVL樹的指令式演算法
4.5 小結.
05 基數樹： Trie 和Patricia
5.1 整數Trie
5.2 整數Patricia
5.3 字元Trie
5.4 字元Patricia
5.5 Trie 和Patricia 的應用
5.6 小結
06 後綴樹
6.1 後綴Trie
6.2 後綴樹
6.3 後綴樹的應用
6.4 小結
07 B樹.
7.1 插入
7.2 刪除
7.3 搜索
7.4 小結

第二部分 堆積
08 二元堆積
8.1 用陣列實現隱式二元堆積
8.2 左偏堆積和skew 堆積：顯性的二元堆積
8.3 延伸堆積
8.4 小結
09 從吃葡萄到世界盃：選擇排序的進化
9.1 尋找最小元素
9.2 細微改進.
9.3 本質改進
9.4 小結
10 二項式堆積、費氏堆積和配對堆積
10.1 二項式堆積
10.2 費氏堆積
10.3 配對堆積
10.4 小結

第三部分 佇列和序列
11 並不簡單的佇列
11.1 單嚮鏈結串列和循環緩衝區實現的佇列
11.2 純函數式實現.
11.3 小改進：平衡佇列.
11.4 進一步改進：即時佇列
11.5 惰性即時佇列
11.6 小結
12 序列：最後一塊磚
12.1 二元隨機存取列錶
12.2 二元隨機存取列錶的數值錶示
12.3 指令式雙陣列清單
12.4 可連接列錶
12.5 手指樹
12.6 小結

第四部分 排序和搜索
13 分而治之：快速排序和歸併排序
13.1 快速排序
13.2 快速排序的效能分析
13.3 工程實作中的改進
13.4 針對最差情況的工程實作
13.5 其他工程實作
13.6 其他
13.7 歸併排序
13.8 原地歸併排序
13.9 自然歸併排序
13.10 自底嚮上歸併排序.
13.11 平行處理
13.12 小結
14 搜索
14.1 序列搜索
14.2 解的搜索.
14.3 小結

A 列錶
B 參考文獻
 

前言

　　✤ 演算法有用嗎

　　「演算法有用嗎？」經常有人問我這個問題。很多人在工作中根本不用演算法。偶爾碰到的時候，也不過是使用一些實現好的函數庫。舉例來說，C++ 標準範本函數庫（STL）中有現成的排序、尋找函數；常用的資料結構，如嚮量（vector）、佇列（queue）、集閤（set）也都實現好瞭。日常工作中瞭解如何使用這些函數庫似乎就足夠瞭。

　　但是，演算法在解決一些「有趣」的問題時會造成關鍵作用。不過，這些問題本身的價值卻是見仁見智。

　　讓我們用實例來說話吧。接下來的兩道題目，即使是初學程式設計的人，應該也很容易解決。

　　✤ 最小可用ID，演算法的威力

　　這道題目來自Richard Bird 所著書中的第1章[1]。現代社會中，有很多服務依賴一種稱為ID的概念。例如身份證就是一種ID，銀行帳戶也是，電話號碼本質上也是一種ID。假設我們使用非負整數作為某個係統的ID，所有使用者都由一個ID唯一確定。任何時間，這個係統中的有些ID處於使用中的狀態，有些ID則可以分配給新使用者。現在的問題是，怎樣纔能找到最小的可分配ID呢？例如下麵是目前正在使用的ID：

　　[18, 4, 8, 9, 16, 1, 14, 7, 19, 3, 0, 5, 2, 11, 6]

　　最小的可分配ID，也就是不在這個清單中的最小非負整數，即10。

　　有些程式語言內建瞭這一綫性尋找的實現，例如Python。我們可以直接將這一解法翻譯成下麵的程式：

　　def brute_force(lst):
　　i = 0
　　while True:
　　　if  i not in lst:
　　　return i
　　　i = i + 1

　　但是這道題目僅是看上去簡單。在儲存瞭幾百萬個ID的大型係統中，這個方法的效能很差。對於一個長度為n的ID清單，它需要O(n2 )的時間纔能找到最小的可分配ID。在我的電腦上（雙核心2.10 GHz處理器，2 GB憶體），使用這一方法的C語言程式平均要5.4 s纔能在10萬個ID 找到答案。當ID的數量上升到100萬時，平均用時則長達8min。

　　改進一

　　改進這一解法的關鍵基於這一事實：對於任何n個非負整數x1 , x2 , •••, xn，如果存在小於n的可用整數，必然存在某個xi不在[0, n) 範圍內。否則這些整數一定是0, 1, •••, n −1 的某個排列，這種情況下，最小的可用整數是n。於是我們有以下結論：

　　minf ree(x1 , x2 , •••, xn) 至n     (1)

　　✤ 小結

　　迴顧前麵兩個有趣的例題，暴力解法都捉襟見肘。對於第一題，暴力解法尚能解決較短的列錶，而在第二題中暴力解法根本行不通。

　　第一個實例展示瞭演算法的力量，第二個實例展示瞭資料結構的重要性。有很多有趣的題目在電腦發明之前很難解決，但是透過程式設計和電腦，可以用和傳統方式完全不同的方法找到答案。相對於中小學數學課上所學的方法，這樣的方法並沒有被普遍教授。

　　雖然優秀的演算法、資料結構和數學書汗牛充棟，但是對程序式解法和函數式解法進行對比的卻寥寥無幾。從上麵的實例中可以看到，有時函數式解法十分簡潔，並且很接近我們在數學課上所熟悉的思考方式。

　　本書力圖同時介紹指令式和函數式的演算法和資料結構。（Okasaki 的著作[3]中有很多函數式資料結構可供進一步參考，關於指令式的內容可以參考一些經典書[4] 以及維基百科。）本書的範例程式使用瞭多種程式語言，包含C、C++、Python、Haskell 和Lisp 方言Scheme， 讀者可以從https://github.com/liuxinyu95/AlgoXY 上下載本書的全部範例程式。為瞭讓具有不同背景的讀者都容易閱讀，所有演算法都提供虛擬程式碼和數學函數描述。

　　由於時間倉促，書中難免存在錯誤，歡迎讀者們和專傢批評指正，提供意見和迴饋。

　　本書作者電子電子郵件：liuxinyu95@gmail.com。

　　✤ 內容組織

　　在接下來的章節中，我們將先介紹基本的資料結構，此後的一些演算法都會用到它們。第一部分首先介紹資料結構中的"hello world"--二元搜尋樹，接下來說明如何解決二元樹的平衡問題。然後我們將介紹更多有趣的樹，其中Trie、Patricia 和後綴樹可以用於文字處理，而B樹則廣泛應用於檔案係統和資料庫。

　　第二部分介紹堆積的相關內容。我們列齣一個抽象堆積的定義，然後介紹如何使用陣列和各種二元樹實現二元堆積（binary heap），接著擴充到其他的堆積，包含二項式堆積、費氏堆積和配對堆積（pairing heap）。

　　陣列和佇列通常被認為是簡單的資料結構，但我們將在第三部分看到，它們實現起來並不容易。

　　作為基本的排序演算法，我們將介紹指令式和函數式的插入排序、快速排序和歸併排序等演算法。第四部分介紹尋找和搜索的相關內容，除瞭基本演算法，還會介紹諸如KMP這樣的文字比對演算法。

　　附錄介紹關於鏈結串列的基本內容。