計算機科學概論（微課版）

馮丹，教授，博士生導師，長江學者特聘教授，國家傑出青年基金獲得者。華中科技大學計算機科學與技術學院副校長，武漢光電國家研究中心信息存儲與光顯示功能實驗室主任，信息存儲系統教育部重點實驗室主任，數據存儲系統與技術教育部工程研究中心主任。主要從事計算機系統結構、大數據存儲系統、非易失存儲技術、存算融合技術等方面的研究。先後擔任兩個973項目首席科學家，863重大項目“海量存儲系統關鍵技術”總體專家組組長，擔任“信息存儲系統與技術”?教育部創新團隊學術帶頭人，“大數據存儲系統與技術”國家自然科學基金委創新研究群體項目負責人。在國內外重要學術刊物及學術會議上發表有關學術論文200余篇，著作2部。授權100余項發明專利，獲10余項軟件著作權。牽頭制定國家標準6項，中國電子行業標準3項。獲國家技術發明二等獎2項，省部一等獎3項，國際存儲競賽決賽獎1項。承擔《計算機系統結構》、《信息存儲理論與技術》等課程教學，負責建成計算機系統結構MOOC，已有2萬余人選修該課程。教學成果“聚焦計算機系統創新能力的“一基兩翼全鏈”研究生培養體系構建與實踐“獲湖北省教學成果特等獎。

第 1章 概述 1

1.1計算機學科　2

1.1.1計算機學科的形成與發展　2

1.1.2計算機學科的本質　3

1.1.3計算機學科的知識體系　3

1.1.4計算機學科的核心內容　4

1.2計算的起源　4

1.2.1計算歷史　5

1.2.2計算思維與算法　6

1.3計算工具　7

1.3.1手動計算　7

1.3.2機械式計算　7

1.3.3機電式計算　8

1.3.4電子計算機　9

1.3.5超級計算機　10

1.4計算機應用　11

1.5計算機社會影響　12

1.5.1計算機知識產權　13

1.5.2計算機網絡信息安全　13

1.6小結　14

1.7拓展知識　14

1.8習題　15

第　2章 計算機發展與概述　17

2.1圖靈模型　17

2.1.1誕生背景　17

2.1.2數據處理器　18

2.1.3可編程數據處理器　19

2.1.4通用圖靈機　19

2.2馮·諾伊曼架構概述　20

2.2.1誕生背景　20

2.2.2馮·諾伊曼架構　21

2.2.3存儲程序概念　22

2.2.4指令的順序執行　22

2.3計算機硬件　22

2.3.1中央處理器　(CPU)　23

2.3.2主存　(內存)　23

2.3.3輸入/輸出子系統　24

2.4計算機軟件　25

2.4.1系統軟件　25

2.4.2應用軟件　26

2.5計算機相關知識　26

2.5.1計算機的類型　26

2.5.2計算機的數據　27

2.5.3計算機的特點　28

2.5.4計算機的性能評估　29

2.5.5計算機的工作方式　30

2.6本章小結　30

2.7拓展知識——馮·諾依曼架構的趣味故事　31

2.8習題　31

第3章　數據表示與運算　32

3.1計算機中的數據表示　32

3.1.1數制及轉換　33

3.1.2機器數和碼制　35

3.1.3定點數和浮點數　36

3.1.4情景案例　37

3.2邏輯運算　38

3.2.1情景案例　38

3.2.2邏輯運算的定義　38

3.2.3位層次上的邏輯運算　39

3.2.4模式層次上的邏輯運算　40

3.3移位運算　41

3.3.1邏輯移位運算　42

3.3.2算數移位運算　42

3.4算術運算　43

3.4.1定點數加減運算　43

3.4.2浮點數加減運算　44

3.4.3乘除運算　45

3.4數據運算的硬件實現　45

3.4.1數字電路的基本知識　46

3.4.2加法器　47

3.5小結　50

3.6拓展知識　50

3.7習題　51

第4章　數據存儲　52

4.1數據存儲技術的發展　52

4.1.1打孔紙帶　53

4.1.2磁介質存儲器　54

4.1.3光盤存儲器　56

4.1.4半導體存儲器　57

4.2文本存儲　59

4.2.1位與字節　59

4.2.2英文編碼：ASCII　60

4.2.3漢字編碼：GB　2312和大五碼　60

4.2.4統一編碼：Unicode　60

4.3多媒體存儲　62

4.3.1音頻存儲　62

4.3.2圖像存儲　63

4.3.3視頻存儲　65

4.4數據壓縮　66

4.4.1Run-Length編碼　66

4.4.2Huffman編碼　67

4.5數據恢復　68

4.5.1數據副本　68

4.5.2糾刪碼　69

4.6小結　69

4.7拓展知識——MySQL數據庫　69

4.8習題　69

第5章　數據傳輸　71

5.1傳輸介質的發展　71

5.1.1導向型傳輸介質　72

5.1.2非導向型傳輸介質　74

5.2傳輸方式的發展　76

5.2.1現代通信技術的開端　77

5.2.2因特網　78

5.2.3未來通信技術　82

5.3網絡協議　82

5.3.1協議　82

5.3.2因特網協議棧　83

5.4傳輸層　85

5.4.1面向連接的傳輸：TCP　85

5.4.2無連接的傳輸：UDP　88

5.5網絡層　89

5.5.1網絡層尋址　89

5.5.2路由器　92

5.6數據鏈路層　94

5.6.1鏈路層尋址　94

5.6.2交換機　96

5.7小結　98

5.8拓展知識：5G　通信技術　98

5.9習題　100

第6章　數據結構　101

6.1數據表示及數據結構　101

6.1.1息世界層的數據表示　101

6.1.2數據結構及其分類　102

6.2數組　103

6.2.1數組的定義　103

6.2.2數組的操作　104

6.2.3多維數組　104

6.3鏈表　105

6.3.1數組與鏈表　105

6.3.2鏈表的操作　105

1.　訪問鏈表元素　105

2.　向鏈表插入節點　106

3.　刪除鏈表節點　106

5.3.3鏈表的類型　106

6.4結構體　107

6.4.1結構體的定義　107

6.4.2結構體的操作　107

6.4.3結構體數組　108

6.5抽象數據類型　108

6.5.1定義　109

6.5.2棧　109

6.5.3隊列　110

6.5.4樹　111

6.5.5圖　112

6.6小結　113

6.7拓展知識——數據結構的歷史　113

6.8習題　113

第7章　算法　114

7.1算法基礎　114

7.1.1算法的定義　115

7.1.2從實例看算法　115

7.1.3算法的復雜度分析　116

7.2遞歸與分治　117

7.2.1遞歸的基本思想　117

7.2.2斐波那契數列　117

7.2.3漢諾塔問題　118

7.2.4分治的基本思想　118

7.2.5二分查找　119

7.3動態規劃　119

7.3.1動態規劃的基本思想　120

7.3.2背包問題　120

7.3.3最長公共子序列（LCS）　121

7.3.4動態規劃的遞歸與疊代實現　122

7.3.5動態規劃的優化策略　123

7.4貪心　123

7.4.1貪心的基本思想　124

7.4.2錢幣找零問題　124

7.4.3區間調度問題　124

7.4.4Prim算法與Kruskal算法　124

7.5回溯與分支限界　125

7.5.1回溯算法的基本思想　125

7.5.2八皇後問題　126

7.5.3圖著色問題　127

7.5.4貨郎問題　127

7.6小結　127

7.7拓展知識—拓展算法介紹　128

7.8習題　129

第8章　大數據　131

8.1大數據概述　131

8.1.1從數據到大數據　131

8.1.2大數據核心技術　133

8.1.3大數據應用　135

8.2大數據采集　136

8.2.1數據源　136

8.2.2ETL　137

8.2.3網絡爬蟲　138

8.3大數據存儲　139

8.3.1分布式文件系統　139

8.3.2分布式數據庫　141

8.4大數據分析　144

8.4.1數據理解與預處理　144

8.4.2數據挖掘　145

8.4.3數據可視化　148

8.5大數據處理　150

8.5.1大數據計算框架　150

8.5.2MapReduce　151

8.6小結　154

8.7拓展知識——大數據在推薦系統的作用　154

8.8習題　155

第9章雲計算　156

9.1雲計算概述　156

9.1.1雲計算的產生與發展　157

9.1.2雲計算的原理與特點　157

9.1.3雲計算的服務類型　159

9.1.4雲計算的部署方式　160

9.2雲計算技術　161

9.2.1分布式計算技術　161

9.2.2分布式存儲技術　163

9.2.3虛擬化技術　165

9.3雲計算平臺　167

9.3.1Web技術　167

9.3.2多租戶技術　168

9.3.3容器技術　170

9.4雲計算安全　172

9.4.1安全威脅和挑戰　172

9.4.2雲計算安全參考架構　173

9.4.3雲計算安全機制　174

9.5小結　176

9.6拓展知識——華為雲　177

9.7習題　179

第　10章 人工智能　180

10.1人工智能概述　180

10.1.1什麼是人工智能　180

10.1.2人工智能簡史　181

10.1.3圖靈測試　182

10.1.4智能體　183

10.2知識表示及推理方法　184

10.2.1語義網　184

10.2.2框架　184

10.2.3謂詞邏輯　185

10.2.4經典推理技術　186

10.3搜索技術　187

10.3.1問題空間與狀態空間　187

10.3.2基本搜索策略　187

10.3.3高級搜索方法　188

10.4機器學習　189

10.4.1什麼是機器學習　189

10.4.2機器學習的歷史　189

10.4.3機器學習方法的類型　190

10.4.4樸素貝葉斯法及其應用　191

10.5自然語言處理　192

10.5.1發展歷史　192

10.5.2原理簡介　193

10.5.3典型應用場景　194

10.5.4未來發展趨勢　195

10.6計算機視覺　196

10.6.1計算機視覺為什麼重要　196

10.6.2什麼是計算機視覺　197

10.6.3計算機視覺的挑戰　198

10.6.4問題分類和應用　199

10.7本章小結　201

10.8拓展知識——ChatGPT的背景和應用　201

10.9習題　202