![](/c49/99/10028130261336.jpg)
出版社:清華大學出版社 ISBN:9787302468813 商品編碼:10028130261336 包裝:平裝 出版時間:2017-10-01 代碼:59 作者:吳及,陳健生,白鉑
"基本信息 書名:數據與算法 定價 作者:吳及,陳健生,白鉑 出版社:清華大學出版社 出版日期:2017-10-01 ISBN:9787302468813 字數:565000 頁碼:346 版次:1 裝幀:平裝 開本:16開 商品重量: 編輯推薦
為了解決膨脹的知識量與有限的學制之間的矛盾,提高教學效率和質量,培養撥尖型創新人纔,清華大學電子工程繫進行了全面的教學改革。在梳理出電子信息科學與技術知識構架的基礎上,構建起了全新的課程體繫。本書是清華大學電子工程繫核心課繫列教材之一,由清華大學副校長王希勤教授作序推薦。隨著大數據和數據科學的興起和發展,如何看待、處理和利用數據,已經成為理論和應用價值巨大的科學領域。本書從數據與算法的相互作用出發,涵蓋數據結構、數學模型、數值分析和算法設計思想等相互關聯的重要內容,有利於從整體上學習和把握這個學科的基礎知識,培養基礎能力。書中,問題和算法兩個視角構成了縱橫交織的網絡,幫助讀者更清楚地看到數據和算法的相互關繫,更透徹地理解數值和非數值問題的差異和共性,幫助讀者更全面地提升利用計算機作為工具解決實際問題的能力。 內容提要
本書從數據與算法的相互關繫入手,內容涵蓋了傳統的數據結構和數值分析,並增加了數學模型和算法設計思想的介紹。 全書分四部分,靠前部分,介紹數據、數學模型和算法的基本概念,是全書的基礎;數據結構部分從數學模型和問題的角度介紹線性結構、樹結構、圖結構,以及查找和排序這兩種很常見的非數值問題;數值分析部分從問題的角度介紹誤差分析、實數的表示和運非線性方程、線性方程組、擬合與插值、很優化問題;第四部分,從算法設計思想的角度介紹蠻力法、分治法、貪心法、動態規劃、搜索算法和算法,以及求解具體問題時的應用實例。 目錄
目錄 第 1章數據、數學模型和算法 ................................................................................ 1 1.1數據時代 ................................................................................................... 1 1.1.1什麼是數據 ..................................................................................... 1 1.1.2大數據時代 ..................................................................................... 2 1.1.3數據的重要性 .................................................................................. 4 1.2數據的表示 ................................................................................................ 5 1.2關繫及其性質 ........................................................................... 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 目錄 IX4.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方程求解 ......................................................................................... 219 6.4方程 ..................................................................................... 219 6.4.2二分法 ......................................................................................... 220 6.4.3不動點法 ..................................................................................... 222 6.4.4牛頓法 ......................................................................................... 225 6.4.5迭代誤差分析 ............................................................................... 229 6.5線性方程組求解 ...................................................................................... 232 6.5.1線性方程組 .................................................................................. 232 目錄 XI6.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論文獎。 序言
" |