計算機科學概論（Python版）

Christine Alvarado

美國加州大學聖地亞哥分校教授，她曾經在哈維瑪德學院任教。

Zachary Dodds

美國哈維瑪德學院計算機科學教授。

Geoff Kuenning

美國哈維瑪德學院教授。

Ran Libesk

美國哈維瑪德學院教授。

目 錄
第 1章　引言 1
1.1　什麼是計算機科學 1
1.1.1　數據 2
1.1.2　算法 2
1.1.3　編程 4
1.1.4　抽象 5
1.1.5　解決問題和創造力 5
1.2　Picobot 5
1.2.1　Roomba問題 6
1.2.2　環境 6
1.2.3　狀態 8
1.2.4　局部思考，全局行動 9
1.2.5　不管怎樣 11
1.2.6　算法和規則 12
1.2.7　Picobot的挑戰 13
1.2.8　一個迷宮，朋友們 13
1.2.9　不可計算的環境 15
關鍵術語 15
練習 15
判斷題 15
討論題 15
編程題 16

第 2章　函數式編程（第 一部分） 17
2.1　人類、黑猩猩和拼寫檢查程序 17
2.2　Python入門 18
2.2.1　命名事物 19
2.2.2　名稱中有什麼 20
2.3　更多數據：從數字到字符串 20
2.3.1　關於長度的簡短說明 21
2.3.2　索引 21
2.3.3　切片 21
2.3.4　字符串算術 22
2.4　列表 23
一些好消息 23
2.5　在Python中使用函數 24
2.5.1　關於文檔字符串的簡短說明 25
2.5.2　關於註釋的同樣簡短的說明 26
2.5.3　函數可以有多行 26
2.5.4　函數可以有多個參數 26
2.5.5　為什麼要編寫函數 27
2.6　做出決策 27
2.6.1　*二個函數示例 29
2.6.2　縮進 31
2.6.3　多重條件 32
2.7　遞歸 33
2.7.1　第 一個遞歸示例：階乘 34
2.7.2　回到編輯距離函數 36
2.8　遞歸揭秘 37
2.8.1　調用函數的函數 37
2.8.2　遞歸，真正的揭秘 39
2.9　我們來使用遞歸吧 44
2.9.1　遞歸設計 44
2.9.2　基本情況 44
2.9.3　使用遞歸進行設計 44
2.9.4　遞歸模式 47
2.9.5　可視化工具 47
2.10　取之棄之 48
2.11　編輯距離 52
2.11.1　distance的基本情況 52
2.11.2　distance的遞歸情況 53
2.12　結論 54
關鍵術語 55
練習 56
判斷題 56
填空題 57
討論題 57
編程題 58

第3章　函數式編程（*二部分） 59
3.1　密碼學和素數 59
3.2　一等函數 61
3.3　生成素數 61
3.4　過濾 65
3.5　lambda 67
3.6　將Google放在map上 69
3.6.1　map 70
3.6.2　reduce 73
3.6.3　組合與mapReduce 74
3.7　函數作為結果 75
3.7.1　用Python做微積分 76
3.7.2　高階導數 77
3.8　再談RSA密碼學 78
3.9　結論 82
關鍵術語 82
練習 83
判斷題 83
填空題 83
討論題 84
編程題 84

第4章　計算機組織 86
4.1　計算機組織概論 86
4.2　表示信息 87
4.2.1　整數 87
4.2.2　算術 88
4.2.3　負數思維 89
4.2.4　分數：拼接在一起 90
4.2.5　字母和字符串 90
4.2.6　結構化信息 91
4.3　邏輯電路 92
4.3.1　布爾代數 92
4.3.2　產生其他布爾函數 93
4.3.3　使用電路的邏輯 95
4.3.4　邏輯計算 97
4.3.5　內存 99
4.4　構建完整的計算機 100馮 諾依曼架構 102
4.5　Hmmm 104
4.5.1　一個簡單的Hmmm程序 105
4.5.2　試用 106
4.5.3　循環 107
4.5.4　函數 109
4.5.5　使用棧來遞歸 111
4.5.6　保存“珍貴財產” 113
4.5.7　完整的Hmmm指令集 115
4.5.8　*後幾句話 116
4.6　結論 117
關鍵術語 117
練習 118
判斷題 118
選擇題和簡答題 119
討論題 120
邏輯設計與編程題 120

第5章　命令式編程 122
5.1　計算機了解你（比你更了解你
自己） 122
我們的目標：音樂推薦系統 124
5.2　從用戶那裡獲取輸入 125
類型轉換 125
5.3　重複任務：循環 126
5.3.1　底層的遞歸與迭代 127
5.3.2　有限迭代：for循環 128
5.3.3　如何使用循環控制變量 129
5.3.4　累積答案 130
5.3.5　處理非預期的輸入 134
5.3.6　不確定迭代：while循環 134
5.3.7　for循環與while循環 135
5.3.8　故意創建無限循環 137
5.3.9　迭代是高效的 137
5.4　引用以及可變和不可變數據 138
5.4.1　按引用賦值 138
5.4.2　可變數據類型能用其他名稱更改 142
5.5　可變數據+迭代：挑選藝人 143
5.5.1　為什麼要排序？因為運行時間很重要 143
5.5.2　一種簡單的排序算法：selectionSort 146
5.5.3　為什麼selectionSort有效 148
5.5.4　一種不同排序的swap 149
5.5.5　二維數組和嵌套循環 151
5.5.6　字典 153
5.6　讀寫文件 155
5.7　整合在一起：程序設計 156
5.8　結論 161
關鍵術語 161
練習 162
判斷題 162
選擇題和簡答題 163
討論題 164
編程題 165

第6章　面向對象的程序 167
6.1　簡介 167
6.2　對象式思考 167
6.3　有理數解決方案 169
6.4　重載 173
6.5　打印一個對象 175
6.6　關於對象主題的更多討論 176
6.7　用OOP實現圖形 178
6.8　*後，機器人大戰殭屍 181
6.9　結論 187
關鍵術語 188
練習 188
判斷題 188
填空題 189
討論題 189
編程題 190

第7章　問題有多難 192
7.1　永不結束的程序 192
7.2　3種問題：容易、困難和
不可能 193
7.2.1　容易的問題 193
7.2.2　困難的問題 194
7.2.3　不可能的問題 198
7.3　停機問題：不可計算的問題 205
7.4　結論 208
關鍵術語 208
練習 209
判斷題 209
填空題 209
簡答題和討論題 210