xxxfreesexmoves-haodiaocao这里只有精品视频-欧美性受黑人性爽-欧美性受xxxxxx黑人xyx性爽|www.jsyyzsb.com

　　為了解決膨脹的知識量與有限的學制之間的矛盾，提高教學效率和質量，培養拔尖型創新人才，清華大學電子工程系進行了全面的教學改革。在梳理出電子信息科學與技術知識構架的基礎上，構建起了全新的課程體系。本書是清華大學電子工程系核心課系列教材之一，由清華大學副校長王希勤教授作序推薦。

　　隨著大數據和數據科學的興起和發展，如何看待、處理和利用數據，已經成為理論和應用價值巨大的科學領域。本書從數據與算法的相互作用出發，涵蓋數據結構、數學模型、數值分析和算法設計思想等相互關聯的重要內容，有利于從整體上學習和把握這個學科的基礎知識，培養基礎能力。

　　書中，問題和算法兩個視角構成了縱橫交織的網絡，幫助讀者更清楚地看到數據和算法的相互關系，更透徹地理解數值和非數值問題的差異和共性，幫助讀者更全面地提升利用計算機作為工具解決實際問題的能力。

　　近年來，信息科學技術呈現快速發展的態勢，云計算、移動互聯網、大數據、人工智能，給我們所處的時代和社會帶來了一波又一波的沖擊。人們日常生活中的信息獲取方式、社會交往方式、生產工作方式都已經發生了很大的變化，而且更為巨大的變化似乎就在并不遙遠的未來。我們的教學和人才培養模式如何能夠適應這樣的變化，對于高等教育的從業者來說是一個嚴峻的挑戰。 

　　為了解決膨脹的知識量與有限的學制之間的矛盾，提高教學效率和質量，培養拔尖型創新人才，清華大學電子工程系進行了全面的教學改革。在梳理出電子信息科學知識構架的基礎上，構建起了全新的課程體系，數據與算法就是其中的一門核心課程。數據是客觀世界的描述，是信息的載體，也是算法的處理對象；算法是解決問題的方法和步驟，是處理數據的系統。因此數據與算法的關系，本質上是信息載體與系統的相互作用。同時，數據的特性是算法設計中不可忽視的關鍵性因素，對數據特性利用得越充分，算法的性能和效率就越高，但與此同時，算法的針對性越強，適用面也就越窄。 

　　傳統上數據結構和數值分析是兩門課程，前者主要研究非數值問題，后者主要研究數值問題。但是，當我們上升到更宏觀的視角，也就是數據與算法相互關系的視角，我們就能夠更清楚地認識到兩者之間的共性和差異。從共性上來講，它們都把現實世界的問題簡化成為數學模型上的問題，并利用計算機作為工具加以求解，因此有很多算法思想不僅能用于處理非數值問題，也能有效地處理數值問題。例如，二分法既可以用于實現有序線性表的高效查找，又可以用于求解非線性方程；尋找圖的最小生成樹的Prim算法、Kruskal算法和求解多維函數極值的最速下降法都是基于貪心算法的思想。數值和非數值問題的差異也很顯著，數值問題中變量取值是連續的，符合一定精度要求的近似解可能有無窮多個，只需要得到符合精度要求的近似解就足夠了，因此誤差分析在數值分析中處于基礎性的地位；而非數值問題的解空間是離散的，不需要考慮誤差。在實際應用中，數值問題和非數值問題還經常交織在一起，例如搜索引擎已經成為人們獲取信息的主要方式，在其實現過程中就既有非數值問題，也有數值問題。 

　　數據和算法的覆蓋范圍包括了傳統上的數據結構、數值分析兩門課程，同時還特別加入了數學模型和算法設計思想的部分，并從總體上對內容上進行了取舍。我們希望這門新設計的課程，能夠讓同學在學習過程中更清楚地看到數據和算法的相互關系，更透徹地理解數值和非數值問題的差異和共性，更全面地提升利用計算機作為工具解決實際問題的能力，為今后的學習和未來的發展打下扎實的基礎。 

　　全書共有9章，分為四個部分。第一部分是第1章，介紹了數據，算法和數學模型的基本概念，是全書的基礎。第二部分是第2～5章，包括線性結構、樹結構和圖結構，以及查找、排序兩種最常用的非數值問題及其求解，是傳統數據結構的內容。第三部分是第6、7章，包括數值問題和最優化的初步介紹，討論的是數值問題。第四部分是第8、9章，介紹了隨機算法和算法設計思想。 

　　本書第1、2、4、5章由吳及負責撰寫；第6、7、8章由陳健生負責撰寫；白鉑撰寫了第3和第9章，并參與了第4和第7章的部分工作。 

　　由于編者水平有限，疏誤之處在所難免，敬請同行及各界讀者批評指正。作為突破傳統教學模式和內容組織方式的一次嘗試，我們也希望這樣的努力能夠成為電子信息學科教學改革的有益探索。 

　　編者 

　　2017年8月 

　　吳及，清華大學電子工程系副系主任，長聘副教授，博士生導師。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盤、光盤和閃存卡，存儲容量不斷增大，而且價格越來越便宜。 

　　語言交流和書信曾是人類歷史上數據傳輸和信息交互的主要手段。電磁波和電信號的發現和利用，造就了電話、電報等快捷的數據傳輸方式�；ヂ摼W、移動通信，以及 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�，F在得到廣泛應用的 USB 2.0理論傳輸速率為 60MB/s，實際傳輸速率能達到 20～30MB/s；2008年底發布的 USB 3.0標準理論傳輸速率已經達到了 600MB/s。因此基于移動存儲介質的傳輸速率在十多年間也得到數百倍乃至數千倍的提升�；ヂ摼W的發展使得數據傳輸不再受到地理位置的約束。早期的 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，到分布式計算、網格計算和今天聲名顯赫的云計算，給數據計算提供了前所未有的強大能力。 

　　然而數據的計算除了計算能力之外，同樣甚至更為重要的是計算方法，因此近年來以機器學習、數據挖掘為代表的海量數據處理技術都得到了普遍的重視和迅速的發展。 

　　……