數據與算法/清華大學電子工程係核心課係列教材 pdf epub mobi txt 电子书 下载 2025

☆☆☆☆☆

吳及，陳健生，白鉑 著

圖書標籤:

• 數據結構
• 算法
• 清華大學
• 電子工程
• 計算機科學
• 核心教材
• 教材
• 數據與算法
• 編程
• 計算機基礎

出版社： 清华大学出版社

ISBN：9787302468813

版次：1

商品编码：12184595

包装：平装

丛书名： 清华大学电子工程系核心课系列教材

开本：16开

出版时间：2017-09-01

用纸：胶版纸

页数：346

字数：565000

正文语种：中文

編輯推薦

　　

為瞭解決膨脹的知識量與有限的學製之間的矛盾，提高教學效率和質量，培養拔尖型創新人纔，清華大學電子工程係進行瞭全麵的教學改革。在梳理齣電子信息科學與技術知識構架的基礎上，構建起瞭全新的課程體係。本書是清華大學電子工程係核心課係列教材之一，由清華大學副校長王希勤教授作序推薦。
　　隨著大數據和數據科學的興起和發展，如何看待、處理和利用數據，已經成為理論和應用價值巨大的科學領域。本書從數據與算法的相互作用齣發，涵蓋數據結構、數學模型、數值分析和算法設計思想等相互關聯的重要內容，有利於從整體上學習和把握這個學科的基礎知識，培養基礎能力。
　　書中，問題和算法兩個視角構成瞭縱橫交織的網絡，幫助讀者更清楚地看到數據和算法的相互關係，更透徹地理解數值和非數值問題的差異和共性，幫助讀者更全麵地提升利用計算機作為工具解決實際問題的能力。
　　
　　

內容簡介

　　

本書從數據與算法的相互關係入手，內容涵蓋瞭傳統的數據結構和數值分析，並增加瞭數學模型和算法設計思想的介紹。
　　全書分四部分，第一部分，介紹數據、數學模型和算法的基本概念，是全書的基礎；數據結構部分從數學模型和問題的角度介紹綫性結構、樹結構、圖結構，以及查找和排序這兩種*常見的非數值問題；數值分析部分從問題的角度介紹誤差分析、實數的錶示和運算、一元非綫性方程、綫性方程組、擬閤與插值、*優化問題；第四部分，從算法設計思想的角度介紹蠻力法、分治法、貪心法、動態規劃、搜索算法和隨機算法，以及求解具體問題時的應用實例。
　　
　　

作者簡介

吳及，清華大學電子工程係副係主任，長聘副教授，博士生導師。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*佳論文奬。

目錄

第 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

精彩書摘

　　第 1章數據、數學模型和算法
　　1.1數據時代
　　大數據 (big data)是當今學術界和産業界最炙手可熱的名詞之一，其重要性和價值已經得到廣泛的認同。數據科學，也繼實驗科學、理論科學、計算機仿真之後，被稱為科學研究的第四範式。為什麼數據處理技術會得到如此普遍的重視？為什麼人類會對數據中的價值寄予如此巨大的期望？又為什麼人類社會發展到今天，數據的重要性會特彆地凸顯齣來呢？我們從什麼是數據談起。
　　1.1.1什麼是數據
　　“數”是人們用來錶示事物的量的基本數學概念。在人類發展的曆史上，這種抽象的“數”的概念是從具體事物中逐步獲得和建立起來的。例如“一個蘋果”“二個橘子”“三個香蕉”描述的是具體的事物，而“一”“二”“三”則是與具體事物無關的抽象的“數”。另一個相關的概念是“數字”，數字是人們用來計數的符號，如現在人們常用的阿拉伯數字“1”“2”“3”，又如中文的數字“一”“二”“三”和羅馬數字“Ⅰ”“Ⅱ”“Ⅲ”。而我們在這裏要討論的“數據”，則是一個範圍大得多的概念。
　　數據是客觀事物的符號錶示，往往是通過對客觀事物的觀察得到的未經加工的原始素材，是包含知識和信息的原始材料。在今天的信息社會中，數據可以說無處不在，其錶現形式也是多種多樣，例如：
　　文字和符號 :不僅普遍存在於書籍、報紙等傳統的紙質媒介上，也廣泛存在於計算機、手機、平闆電腦等電子設備上；既包括今天人們使用的各種文字符號，也包括從遠古時代遺存下來的象形文字和甲骨文等。
　　多媒體數據：計算機的圖形界麵、廣播電視電影、數碼相機 (DC)和數碼攝像機 (DV)，使得我們身處於豐富多彩的多媒體時代。多媒體數據的采集、保存和播放已經非常方便；圖像、音頻、視頻等各種媒體數據在我們的日常生活中隨處可見。
　　通信信號：電信號和電磁波已經成為人類社會信息最方便快捷的傳輸方式，這些用於通信和控製的電話信號、導航信號、手機信號、廣播信號，無論是在發送端還是在接收端都是數據。
　　傳感器采集的數據：通過各種各樣的溫度傳感器、壓力傳感器，以及 CT、B超、聲呐等，人們可以采集到各種各樣能夠描述客觀事物的數據。
　　社會性數據：人類社會生活的方方麵麵同樣需要大量數據來描述，如社會普查數據、人口統計數據和民意調查數據等，著名的如美國總統大選期間蓋洛普所做的候選人支持率的民意測驗；也包括緊密聯係我們日常生活的經濟運行數據，如物價、收入等。隨著社交網絡的發展和普及，人們之間通過互聯網和移動互聯網的交互行為也成為重要的海量數據來源。
　　可以很清楚地看到對數據的掌握和處理是當今社會的一個基本問題，在科研活動、經濟活動、文化活動和政治活動中，我們隨時都會麵對各種各樣的數據。數據和對數據的處理與我們每個人都息息相關。
　　我們在這裏討論的數據，進一步被特指為能夠輸入到計算機並被計算機處理的。
　　1.1.2大數據時代
　　數據處理技術包括瞭數據的獲取、數據的存儲、數據的傳輸，以及針對數據的計算等。
　　數據是客觀事物的錶示和描述，人具有很強的獲取數據的能力，如人對客觀事物的觀察，社會普查等；數據獲取也可以通過多種多樣的設備，如溫度和壓力等各種傳感器，萬用錶和光譜儀等各種測量儀器，照相機和攝像機等圖像視頻采集設備，麥剋風和錄音機等聲音采集設備，雷達接收機和衛星接收機等信號接收設備等。
　　傳統的數據存儲主要依靠紙質媒介，如書籍、報錶和紙質文件等，典型的模擬存儲介質有膠片和磁帶。隨著數字技術的發展，數字存儲介質已經成為主流。從大型的磁盤存儲係統，到容量越來越大的計算機硬盤，再到便攜的移動硬盤、 U盤、光盤和閃存卡，存儲容量不斷增大，而且價格越來越便宜。
　　語言交流和書信曾是人類曆史上數據傳輸和信息交互的主要手段。電磁波和電信號的發現和利用，造就瞭電話、電報等快捷的數據傳輸方式。互聯網、移動通信，以及 USB和 IEEE 1394等高速率數據傳輸技術的發展，使數據傳輸的快速、高效和方便達到瞭前所未有的程度。
　　麵嚮數據的計算涵蓋瞭對數據的分析、管理和利用。其中既包括瞭以處理器性能為代錶的計算能力，又包括瞭對數據進行處理以實現信息抽取和知識發現的技術方法。
　　隨著信息技術的飛速發展，人類在數據采集、數據存儲和數據傳輸方麵的能力得到瞭長足的發展。我們都知道，二進製是數字計算機的基礎，計算機存儲容量的基本單位是字節 (Byte)，每個字節包含 8個二進製位。為瞭描述不同規模的數據，人們定義瞭一係列的數據計量單位：
　　Bytes → Kilobyte(210 Bytes) → Megabyte(220 Bytes) → Gigabyte(230 Bytes) → Terabyte(240 Bytes) →Petabyte(250 Bytes)→Exabyte(260 Bytes)→Zettabyte(270 Bytes)→ Yottabyte(280 Bytes)
　　其中我們比較熟悉的有韆字節 (KB)、兆字節 (MB)和吉字節 (GB)。我們甚至難以想象更大的數據量單位意味著什麼？美國國會圖書館所有藏書的數據約為 10TB。按照 2001年的數據估算，美國國傢航空航天局地球觀測係統 (Earth Observing System)三年的數據總和約為 1PB[1]。據稱 1個 ZB大概相當於全世界所有海灘上的沙子總和，而 1個 YB大概相當於 7000人體內的原子數總和 [2]。如果以每分鍾 1MB的速度不間斷播放 MP3格式的歌麯，1ZB存儲的歌麯可以讓人聽上 19億年。
　　根據 IDC的統計和預測， 2007年全球數據量約為 161EB；2008年激增到 487EB；金融危機的 2009年，全球數據量達到 0.8ZB，增長 62％； 2010年進一步增長到 1.2ZB，約為 2007年的 8倍；而到 2020年，這一數字將達到 35ZB。人類所擁有的數據量還在以更快的速度增長， 2010年 3月，視頻網站 YouTube宣布每分鍾就會有 24小時的視頻被上傳，而到瞭 2010年 11月，每分鍾上傳至 YouTube的視頻長度已達 35小時。根據 YouTube産品管理負責人的計算：“如果美國三大電視網每天播放 24小時，一周 7天，一年 365天不間斷播放 60年，那麼這些視頻內容纔與 YouTube每 30天增加的內容一樣多。 ”而到瞭 2012年 5月，每分鍾上傳的視頻長度已經超過 72小時，YouTube上已經有超過一萬億個視頻。
　　2012年初，Royal Pingdom網站給齣 2011年與互聯網相關的一些統計數據：
　　.全世界有 31.46億個電子郵件賬戶；
　　.全世界有 5.55億個網站，其中有 3億個是在 2011年創建的；
　　.全世界有 21億互聯網用戶；
　　. 3.5億用戶使用移動設備登錄互聯網；
　　.全世界有超過 24億個社交媒體賬戶；
　　.全球有 26億個即時通信賬戶；
　　.截至 2011年 10月，互聯網用戶每月在綫瀏覽視頻量達到 2014億個；
　　.截至 2011年中期，Facebook上有 1000億張照片；
　　. Flickr上有 5100萬注冊用戶，這些用戶每天上傳 450萬張照片。 Flickr上一共有 60億張照片。
　　很顯然，人類獲取和生産數據的能力已經十分驚人，當今的時代已經是一個“數據爆炸”的時代。為瞭應對數據爆炸性的增長，最近二十年以來，人類在數據存儲能力上的進步極為迅速。二十年前，我們使用的個人計算機往往隻有 40MB的硬盤，數據交換依靠 720KB的 5英寸軟盤和 1.44MB的 3.5英寸軟盤。對於今天的個人計算機而言， 500GB硬盤幾乎成瞭標準配置，用於數據交換的移動存儲設備多為 250GB以上移動硬盤和 2GB以上的 U盤。個人數據存儲産品的容量在二十年間增大瞭成韆上萬倍。在二十年間，數據中心更是從萌芽走嚮成熟，當今的數據中心的存儲規模往往能達到 PB量級，並且在能效、安全、接入和管理等方麵有瞭越來越完善的考慮和設計。
　　數據傳輸技術的發展同樣迅猛。一方麵是依賴於移動存儲介質的數據交換，除瞭存儲量的增大以外，傳輸速率也飛速增長。傳統的 1.44MB軟盤的傳輸速率為 62.5KB/s，計算機串口的傳輸速率為 14.4KB/s。CD光盤的讀取速度為 7.5MB/s，DVD光盤的讀取速度為 16.6MB/s。現在得到廣泛應用的 USB 2.0理論傳輸速率為 60MB/s，實際傳輸速率能達到 20～30MB/s；2008年底發布的 USB 3.0標準理論傳輸速率已經達到瞭 600MB/s。因此基於移動存儲介質的傳輸速率在十多年間也得到數百倍乃至數韆倍的提升。互聯網的發展使得數據傳輸不再受到地理位置的約束。早期的 Modem撥號上網的速率為 7KB/s；現在 ADSL上網的下行速率可以達到 1MB/s，目前傢庭常用的速率為 512KB/s～2MB/s。而局域網的傳輸速率可以達到 10MB/s甚至 100MB/s。而基於無綫傳輸的移動互聯網也可以提供 50～150KB/s的下行速率。隨著互聯網，特彆是移動互聯網的發展，人們將繼續嚮隨時隨地快速傳輸數據的目標前進。
　　數據的計算需要強大的處理能力，其中處理器和隨機存儲器起著至關重要的作用。二十年前的個人計算機，Intel 80386的典型配置是 33MHz主頻和 1MB內存；而今天的 Intel Core2的典型配置是主頻 3GHz、64KB的一級緩存 (L1 cache)和 6MB的二級緩存 (L2 cache)；而 Intel Core-i係列進一步引入瞭三級緩存，並實現瞭 CPU與圖形處理單元 GPU的整閤封裝。因此今天的處理器，其計算能力已經不可同日而語。然而單處理器計算能力的提高仍然遠遠不能滿足數據處理的需要，因此各種並行計算技術風起雲湧，從多核處理器、圖形加速器 GPU，並行程序設計技術如 OpenMP、MPI，到分布式計算、網格計算和今天聲名顯赫的雲計算，給數據計算提供瞭前所未有的強大能力。
　　然而數據的計算除瞭計算能力之外，同樣甚至更為重要的是計算方法，因此近年來以機器學習、數據挖掘為代錶的海量數據處理技術都得到瞭普遍的重視和迅速的發展。
　　……

前言/序言

　　近年來，信息科學技術呈現快速發展的態勢，雲計算、移動互聯網、大數據、人工智能，給我們所處的時代和社會帶來瞭一波又一波的衝擊。人們日常生活中的信息獲取方式、社會交往方式、生産工作方式都已經發生瞭很大的變化，而且更為巨大的變化似乎就在並不遙遠的未來。我們的教學和人纔培養模式如何能夠適應這樣的變化，對於高等教育的從業者來說是一個嚴峻的挑戰。
　　為瞭解決膨脹的知識量與有限的學製之間的矛盾，提高教學效率和質量，培養拔尖型創新人纔，清華大學電子工程係進行瞭全麵的教學改革。在梳理齣電子信息科學知識構架的基礎上，構建起瞭全新的課程體係，數據與算法就是其中的一門核心課程。數據是客觀世界的描述，是信息的載體，也是算法的處理對象；算法是解決問題的方法和步驟，是處理數據的係統。因此數據與算法的關係，本質上是信息載體與係統的相互作用。同時，數據的特性是算法設計中不可忽視的關鍵性因素，對數據特性利用得越充分，算法的性能和效率就越高，但與此同時，算法的針對性越強，適用麵也就越窄。
　　傳統上數據結構和數值分析是兩門課程，前者主要研究非數值問題，後者主要研究數值問題。但是，當我們上升到更宏觀的視角，也就是數據與算法相互關係的視角，我們就能夠更清楚地認識到兩者之間的共性和差異。從共性上來講，它們都把現實世界的問題簡化成為數學模型上的問題，並利用計算機作為工具加以求解，因此有很多算法思想不僅能用於處理非數值問題，也能有效地處理數值問題。例如，二分法既可以用於實現有序綫性錶的高效查找，又可以用於求解非綫性方程；尋找圖的最小生成樹的Prim算法、Kruskal算法和求解多維函數極值的最速下降法都是基於貪心算法的思想。數值和非數值問題的差異也很顯著，數值問題中變量取值是連續的，符閤一定精度要求的近似解可能有無窮多個，隻需要得到符閤精度要求的近似解就足夠瞭，因此誤差分析在數值分析中處於基礎性的地位；而非數值問題的解空間是離散的，不需要考慮誤差。在實際應用中，數值問題和非數值問題還經常交織在一起，例如搜索引擎已經成為人們獲取信息的主要方式，在其實現過程中就既有非數值問題，也有數值問題。
　　數據和算法的覆蓋範圍包括瞭傳統上的數據結構、數值分析兩門課程，同時還特彆加入瞭數學模型和算法設計思想的部分，並從總體上對內容上進行瞭取捨。我們希望這門新設計的課程，能夠讓同學在學習過程中更清楚地看到數據和算法的相互關係，更透徹地理解數值和非數值問題的差異和共性，更全麵地提升利用計算機作為工具解決實際問題的能力，為今後的學習和未來的發展打下紮實的基礎。
　　全書共有9章，分為四個部分。第一部分是第1章，介紹瞭數據，算法和數學模型的基本概念，是全書的基礎。第二部分是第2～5章，包括綫性結構、樹結構和圖結構，以及查找、排序兩種最常用的非數值問題及其求解，是傳統數據結構的內容。第三部分是第6、7章，包括數值問題和最優化的初步介紹，討論的是數值問題。第四部分是第8、9章，介紹瞭隨機算法和算法設計思想。
　　本書第1、2、4、5章由吳及負責撰寫；第6、7、8章由陳健生負責撰寫；白鉑撰寫瞭第3和第9章，並參與瞭第4和第7章的部分工作。
　　由於編者水平有限，疏誤之處在所難免，敬請同行及各界讀者批評指正。作為突破傳統教學模式和內容組織方式的一次嘗試，我們也希望這樣的努力能夠成為電子信息學科教學改革的有益探索。
　　編者
　　2017年8月

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆

评分☆☆☆☆☆