《數據與算法》是2017年10月清華大學出版社出版的圖書，作者是吳及，陳健生，白鉑，本書從數據與算法的相互作用出發，涵蓋數據結構、數學模型、數值分析和算法設計思想等相互關聯的重要內容。
基本介紹
- 中文名：數據與算法
- 作者：吳及、陳健生、白鉑
- 出版社：清華大學出版社
- ISBN：9787302468813
內容簡介,圖書目錄,作者簡介,
內容簡介
本書從數據與算法的相互關係入手，內容涵蓋了傳統的數據結構和數值分析，並增加了數學模型和算法設計思想的介紹。 全書分四部分，第一部分，介紹數據、數學模型和算法的基本概念，是全書的基礎；數據結構部分從數學模型和問題的角度介紹線性結構、樹結構、圖結構，以及查找和排序這兩種常見的非數值問題；數值分析部分從問題的角度介紹誤差分析、實數的表示和運算、一元非線性方程、線性方程組、擬合與插值、化問題；第四部分，從算法設計思想的角度介紹蠻力法、分治法、貪心法、動態規劃、搜尋算法和*算法，以及求解具體問題時的套用實例。
圖書目錄
目錄
第 1章數據、數學模型和算法 ................................................................................ 1
1.1數據時代 ................................................................................................... 1
1.1.1什麼是數據 ..................................................................................... 1
1.1.2大數據時代 ..................................................................................... 2
1.1.3數據的重要性 .................................................................................. 4
1.2數據的表示 ................................................................................................ 5
1.2.1二元關係及其性質 ........................................................................... 5
1.2.2數據的邏輯結構 .............................................................................. 9
1.2.3數據的存儲結構 .............................................................................12
1.2.4抽象數據類型 .................................................................................12
1.3數學模型 ..................................................................................................13
1.3.1什麼是數學模型 .............................................................................13
1.3.2數學模型的種類 .............................................................................14
1.3.3數學模型與計算機 ..........................................................................15
1.3.4數據結構 .......................................................................................16
1.4算法及複雜度分析 .....................................................................................16
1.4.1什麼是算法 ....................................................................................16
1.4.2問題與解 .......................................................................................17
1.4.3算法的分析與評價 ..........................................................................18
1.5本章小結 ..................................................................................................22
第 2章線性結構...................................................................................................24
2.1線性表 .....................................................................................................24
2.1.1線性表的概念及其抽象數據類型 ......................................................24
2.1.2線性表的順序存儲——順序表 .........................................................27
2.1.3線性表的鏈式存儲——鍊表 .............................................................30
2.1.4線性表小結 ....................................................................................35
2.2棧 ............................................................................................................35
2.2.1棧的概念與實現 .............................................................................35
2.2.2棧的套用 .......................................................................................38
2.2.3遞歸 ..............................................................................................41
2.3佇列 .........................................................................................................48
2.3.1佇列的概念與實現 ..........................................................................48
2.3.2優先權佇列 ....................................................................................51
2.4字元串 .....................................................................................................55
2.4.1字元串的概念和 ADT ......................................................................55
2.4.2字元串的存儲表示 ..........................................................................56
2.4.3字元串的模式匹配和簡單匹配算法 ...................................................57
2.4.4 KMP算法 .....................................................................................58
2.5本章小結 ..................................................................................................61
第 3章樹與二叉樹 ...............................................................................................62
3.1樹的基本概念 ...........................................................................................62
3.1.1普遍存在的樹結構 ..........................................................................62
3.1.2樹的定義和性質 .............................................................................65
3.2二叉樹 .....................................................................................................67
3.2.1二叉樹的定義和性質 .......................................................................68
3.2.2二叉樹的表示和實現 .......................................................................70
3.2.3二叉樹的遍歷 .................................................................................76
3.2.4二叉樹運算 ....................................................................................81
3.2.5二叉樹的建立 .................................................................................83
3.3二叉樹的套用 ...........................................................................................84
3.3.1表達式求值 ....................................................................................84
3.3.2二叉搜尋樹 ....................................................................................85
3.3.3 Hu.man樹與編碼 ..........................................................................89
3.3.4堆 .................................................................................................95
3.4並查集 ................................................................................................... 102
3.5本章小結 ................................................................................................ 103
第 4章圖........................................................................................................... 105
4.1圖的基本概念 ......................................................................................... 105
4.1.1圖的定義和概念 ........................................................................... 105
4.1.2圖的抽象數據類型 ........................................................................ 110
4.1.3歐拉路徑 ..................................................................................... 110
4.2圖的存儲結構 ......................................................................................... 112
4.2.1圖的鄰接矩陣表示 ........................................................................ 112
4.2.2圖的鄰接表表示 ........................................................................... 115
4.2.3圖的其他表示方法 ........................................................................ 119
4.3圖的遍歷 ................................................................................................ 122
4.3.1圖的深度優先遍歷 ........................................................................ 123
目錄 IX 4.3.2圖的廣度優先遍歷 ........................................................................ 124
4.3.3圖遍歷的套用 ............................................................................... 125
4.3.4圖的連通性 .................................................................................. 128
4.4有向圖與有向無環圖 ............................................................................... 129
4.4.1有向圖的連通性和傳遞閉包 ........................................................... 129
4.4.2有向無環圖和拓撲排序 ................................................................. 132
4.4.3關鍵路徑 ..................................................................................... 135
4.5小生成樹 ............................................................................................. 137
4.5.1圖的生成樹與小生成樹 .............................................................. 137
4.5.2普里姆 (Prim)算法 ...................................................................... 139
4.5.3克魯斯卡爾 (Kruskal)算法 ............................................................ 142
4.6短路徑問題 ......................................................................................... 144
4.6.1單源短路徑 ............................................................................... 145
4.6.2全源短路徑 ............................................................................... 147
4.7流 ................................................................................................... 149
4.7.1網路流的基本概念 ........................................................................ 150
4.7.2 Ford-Fulkerson方法 ..................................................................... 151
4.8匹配 ....................................................................................................... 154
4.8.1二分圖和匹配的基本概念 .............................................................. 154
4.8.2匈牙利算法 .................................................................................. 155
4.8.3匹配與流 ........................................................................ 157
4.9本章小結 ................................................................................................ 157
第 5章查找和排序 ............................................................................................. 159
5.1線性查找表 ............................................................................................. 159
5.1.1順序查找 ..................................................................................... 160
5.1.2折半查找 ..................................................................................... 161
5.1.3斐波那契查找 ............................................................................... 162
5.1.4線性查找表的性能比較 ................................................................. 163
5.2靜態索引結構 ......................................................................................... 164
5.2.1索引查找 ..................................................................................... 164
5.2.2索引存儲方式 ............................................................................... 164
5.2.3索引檔案結構 ............................................................................... 167
5.3二叉搜尋樹查找性能 ............................................................................... 169
5.4散列方法 ................................................................................................ 172
5.4.1散列技術的基本思想 ..................................................................... 172
5.4.2散列函式 ..................................................................................... 173
5.4.3衝突處理 ..................................................................................... 175
5.4.4散列的刪除 .................................................................................. 178
5.4.5散列的性能 .................................................................................. 178
5.5排序的概念及算法性能分析 ..................................................................... 179
5.6基本排序方法 ......................................................................................... 180
5.6.1冒泡排序 ..................................................................................... 181
5.6.2插入排序 ..................................................................................... 182
5.6.3直接選擇排序 ............................................................................... 187
5.6.4基本排序方法的比較 ..................................................................... 188
5.7快速排序 ................................................................................................ 189
5.7.1快速排序的過程 ........................................................................... 189
5.7.2快速排序的性能分析 ..................................................................... 191
5.8歸併排序 ................................................................................................ 192
5.8.1二路歸併 ..................................................................................... 192
5.8.2自底向上的歸併排序 ..................................................................... 192
5.8.3自頂向下的歸併排序 ..................................................................... 194
5.9堆和堆排序 ............................................................................................. 195
5.9.1堆排序的思想 ............................................................................... 195
5.9.2堆排序的實現 ............................................................................... 197
5.10內排序方法分析 .................................................................................... 198
5.10.1排序方法的下界 ........................................................................ 198
5.10.2內排序方法的比較 ..................................................................... 199
5.11本章小結 .............................................................................................. 200
第 6章數值計算問題 .......................................................................................... 202
6.1引言 ....................................................................................................... 202
6.2近似與誤差 ............................................................................................. 204
6.2.1誤差的定義 .................................................................................. 204
6.2.2誤差的分類 .................................................................................. 209
6.2.3條件數與敏感性 ........................................................................... 212
6.3實數的表示與運算 ................................................................................... 214
6.3.1浮點數系統 .................................................................................. 214
6.3.2浮點運算 ..................................................................................... 217
6.4一元方程求解 ......................................................................................... 219
6.4.1一元方程 ..................................................................................... 219
6.4.2二分法 ......................................................................................... 220
6.4.3不動點法 ..................................................................................... 222
6.4.4牛頓法 ......................................................................................... 225
6.4.5疊代誤差分析 ............................................................................... 229
6.5線性方程組求解 ...................................................................................... 232
6.5.1線性方程組 .................................................................................. 232
目錄 XI 6.5.2向量與矩陣範數 ........................................................................... 234
6.5.3線性方程組敏感性 ........................................................................ 239
6.5.4線性方程組直接解法 ..................................................................... 242
6.5.5線性方程組疊代解法 ..................................................................... 252
6.6擬合與插值 ............................................................................................. 256
6.6.1線性小二乘 ............................................................................... 256
6.6.2多項式插值 .................................................................................. 264
6.7本章小結 ................................................................................................ 267
第 7章化初步 ............................................................................................. 268
7.1最佳化問題及其性質 ................................................................................... 268
7.2無約束最佳化問題 ...................................................................................... 271
7.2.1最佳化條件 ..................................................................................... 271
7.2.2一維最佳化 ..................................................................................... 272
7.2.3多維最佳化 ..................................................................................... 275
7.3約束最佳化問題 ......................................................................................... 279
7.3.1最佳化條件 ..................................................................................... 279
7.3.2序列二次規劃法 ........................................................................... 282
7.3.3障礙法 ......................................................................................... 284
7.4凸最佳化 ................................................................................................... 286
7.4.1凸集合 ......................................................................................... 286
7.4.2凸函式 ......................................................................................... 289
7.4.3凸最佳化問題 .................................................................................. 292
7.5組合最佳化的數值求解 ............................................................................... 294
7.5.1組合最佳化問題 ............................................................................... 294
7.5.2線性規劃初步 ............................................................................... 296
7.5.3頂點覆蓋的線性規劃求解 .............................................................. 297
7.6本章小結 ................................................................................................ 298
第 8章隨機算法................................................................................................. 299
8.1隨機性與隨機數 ...................................................................................... 299
8.2舍伍德與拉斯維加斯算法 ......................................................................... 301
8.3蒙特卡洛算法 ......................................................................................... 304
8.4模擬退火與遺傳算法 ............................................................................... 307
8.5本章小結 ................................................................................................ 310
第 9章算法設計思想 .......................................................................................... 311
9.1蠻力法 ................................................................................................... 311
9.2分治法 ................................................................................................... 313
9.2.1分治法的運行時間 ........................................................................ 314
9.2.2分治法套用舉例 ........................................................................... 316
9.2.3減治法 ......................................................................................... 319
9.2.4變治法 ......................................................................................... 321
9.3貪心法 ................................................................................................... 323
9.4動態規劃 ................................................................................................ 326
9.4.1動態規劃的基本原理 ..................................................................... 326
9.4.2算法設計舉例 ............................................................................... 328
9.5搜尋算法：回溯法與分支定界法 ............................................................... 334
9.5.1組合最佳化問題的解空間 ................................................................. 334
9.5.2回溯法 ......................................................................................... 338
9.5.3分支定界法 .................................................................................. 342
作者簡介
作者簡介：吳及，清華大學電子工程系副系主任，長聘副教授，博士生導師。1996年和2001年在清華大學電子工程系獲得學士和工學博士學位。2013—2015年在美國喬治亞理工學院擔任訪問學者。主要從事數據與算法方面的教學工作，以及人工智慧和大數據領域的研究工作。2006起擔任清華-訊飛語音技術聯合實驗室主任。目前是中國語音產業聯盟技術工作組組長。先後獲得2011年度國家科技進步二等獎和2014年度北京市科學技術獎一等獎。已在國內外刊物和學術會議上發表論文一百餘篇，現在為IEEE高級會員。陳健生，博士，出生於安徽省蕪湖市，畢業於清華大學計算機科學與技術系（學士、碩士）和香港中文大學計算機科學與工程系（博士）。目前在清華大學電子工程系任副教授，博士生導師。教學方面，擔任電子系本科生核心課“數據與算法”及限選課“視聽信息系統導論”的主講教師；曾獲清華大學第六屆青年教師教學大賽理工科一等獎。主要研究領域為計算機視覺與機器學習。在國際期刊及會議上發表有多篇論文，曾獲2013年度北京市科學技術獎一等獎。白鉑，男，1982年生於陝西西安，2004年畢業於西安電子科技大學，獲學士學位，陝西省優秀畢業生。2010畢業於清華大學，獲博士學位，電子系學術新秀。2010—2012年在香港科技大學做博士後研究。隨後，進入清華大學電子系任講師，碩士生導師。曾獲2016年清華大學青年教師教學基本功大賽一等獎（理工組）。2017年加入華為技術有限公司2012實驗室，任未來網路理論實驗室高級研究員。研究方向包括無線協作資源分配、Cloud/Fog-無線計算網路、網路資訊理論、網路大數據分析等。發表學術論文近80篇，其中SCI檢索論文近30篇，曾獲IEEE ICC 2016論文獎。
