本書基于MIT 編程思維培訓講義寫成，主要目標在于幫助讀者掌握并熟練使用各種計算技術，具備用計算思維解決現(xiàn)實問題的能力。書中以Python 3 為例，介紹了對中等規(guī)模程序的系統(tǒng)性組織、編寫、調試，幫助讀者深入理解計算復雜度，還講解了有用的算法和問題簡化技術，并探討各類計算工具的使用。與本書* 1版相比，* 2版全面改寫了后半部分，且書中所有示例代碼都從Python 2 換成了Python 3。
本書適合對編程知之甚少但想要使用計算方法解決問題的讀者。
掌握多種不同的思維方式是每個人在大學時代的必修課。具備使用計算思維解決問題的能力是程序員入門的基本技能。本書基于作者開授的MIT熱門MOOC教程編寫，旨在培養(yǎng)讀者的計算思維，為其日后的IT生涯打下堅實的編程基礎。
- 以Python 3為示例，涵蓋Python大部分特性，重在介紹編程語言可以做什么
- 如何系統(tǒng)性地組織、編寫、調試中等規(guī)模的程序
- 理解計算復雜度
- 將模糊的問題描述轉化為明確的計算方法，以此解決問題，并深刻理解整個過程
- 掌握有用的算法以及問題簡化技術
- 使用隨機性和模擬技術清晰闡述很難得到封閉解的問題
- 使用計算工具（包括簡單的統(tǒng)計、可視化以及機器學習工具）對數(shù)據(jù)進行理解與建模
John V. Guttag
1999年~2004年任MIT電氣工程與計算機科學系主任，所授計算機科學系列導論課程深受學生歡迎。目前為計算機科學與人工智能實驗室網(wǎng)絡及移動系統(tǒng)組聯(lián)合負責人，還進行軟件工程、機器定理證明、硬件驗證等領域的研究以及培訓工作。獲美國布朗大學英語專業(yè)學士學位、應用數(shù)學碩士學位，多倫多大學計算機科學博士學位。
目 錄
* 1章 啟程 1
* 2章 Python簡介 6
2.1 Python基本元素 7
2.1.1 對象、表達式和數(shù)值類型 8
2.1.2 變量與賦值 9
2.1.3 Python IDE 11
2.2 程序分支 12
2.3 字符串和輸入 14
2.3.1 輸入 15
2.3.2 雜談字符編碼 16
2.4 迭代 17
第3章 一些簡單的數(shù)值程序 20
3.1 窮舉法 20
3.2 for循環(huán) 22
3.3 近似解和二分查找 24
3.4 關于浮點數(shù) 27
3.5 牛頓 拉弗森法 29
第4章 函數(shù)、作用域與抽象 31
4.1 函數(shù)與作用域 32
4.1.1 函數(shù)定義 32
4.1.2 關鍵字參數(shù)和默認值 33
4.1.3 作用域 34
4.2 規(guī)范 37
4.3 遞歸 39
4.3.1 斐波那契數(shù)列 40
4.3.2 回文 42
4.4 全局變量 45
4.5 模塊 46
4.6 文件 47
第5章 結構化類型、可變性與
高階函數(shù) 50
5.1 元組 50
5.2 范圍 52
5.3 列表與可變性 52
5.3.1 克隆 57
5.3.2 列表推導 57
5.4 函數(shù)對象 58
5.5 字符串、元組、范圍與列表 60
5.6 字典 61
第6章 測試與調試 65
6.1 測試 65
6.1.1 黑盒測試 66
6.1.2 白盒測試 68
6.1.3 執(zhí)行測試 69
6.2 調試 70
6.2.1 學習調試 72
6.2.2 設計實驗 72
6.2.3 遇到麻煩時 75
6.2.4 找到“目標”錯誤之后 76
第7章 異常與斷言 77
7.1 處理異常 77
7.2 將異常用作控制流 80
7.3 斷言 82
第8章 類與面向對象編程 83
8.1 抽象數(shù)據(jù)類型與類 83
8.1.1 使用抽象數(shù)據(jù)類型設計程序 87
8.1.2 使用類記錄學生與教師 87
8.2 繼承 90
8.2.1 多重繼承 92
8.2.2 替換原則 93
8.3 封裝與信息隱藏 94
8.4 進階示例：抵押貸款 99
第9章 算法復雜度簡介 103
9.1 思考計算復雜度 103
9.2 漸近表示法 106
9.3 一些重要的復雜度 107
9.3.1 常數(shù)復雜度 107
9.3.2 對數(shù)復雜度 108
9.3.3 線性復雜度 108
9.3.4 對數(shù)線性復雜度 109
9.3.5 多項式復雜度 109
9.3.6 指數(shù)復雜度 111
9.3.7 復雜度對比 112
* 10章 一些簡單算法和數(shù)據(jù)結構 114
10.1 搜索算法 115
10.1.1 線性搜索與間接引用元素 115
10.1.2 二分查找和利用假設 116
10.2 排序算法 119
10.2.1 歸并排序 120
10.2.2 將函數(shù)用作參數(shù) 122
10.2.3 Python中的排序 123
10.3 散列表 124
* 11章 繪圖以及類的進一步擴展 128
11.1 使用PyLab繪圖 128
11.2 進階示例：繪制抵押貸款 133
* 12章 背包與圖的* 優(yōu)化問題 139
12.1 背包問題 139
12.1.1 貪婪算法 140
12.1.2 0/1背包問題的* 優(yōu)解 143
12.2 圖的* 優(yōu)化問題 145
12.2.1 一些典型的圖論問題 149
12.2.2 * 短路徑：深度優(yōu)先搜索和
廣度優(yōu)先搜索 149
* 13章 動態(tài)規(guī)劃 155
13.1 又見斐波那契數(shù)列 155
13.2 動態(tài)規(guī)劃與0/1背包問題 157
13.3 動態(tài)規(guī)劃與分治算法 162
* 14章 隨機游走與數(shù)據(jù)可視化 163
14.1 隨機游走 163
14.2 醉漢游走 164
14.3 有偏隨機游走 170
14.4 變幻莫測的田地 175
* 15章 隨機程序、概率與分布 178
15.1 隨機程序 178
15.2 計算簡單概率 180
15.3 統(tǒng)計推斷 180
15.4 分布 192
15.4.1 概率分布 194
15.4.2 正態(tài)分布 195
15.4.3 連續(xù)型和離散型均勻分布 199
15.4.4 二項式分布與多項式分布 200
15.4.5 指數(shù)分布和幾何分布 200
15.4.6 本福德分布 203
15.5 散列與碰撞 204
15.6 強隊的獲勝概率 206
* 16章 蒙特卡羅模擬 208
16.1 帕斯卡的問題 209
16.2 過線還是不過線 210
16.3 使用查表法提高性能 213
16.4 求π的值 214
16.5 模擬模型結束語 218
第* 章 抽樣與置信區(qū)間 220
17.1 對波士頓馬拉松比賽進行抽樣 220
17.2 中心極限定理 225
17.3 均值的標準誤差 228
第* 章 理解實驗數(shù)據(jù) 231
18.1 彈簧的行為 231
18.2 彈丸的行為 238
18.2.1 可決系數(shù) 240
18.2.2 使用計算模型 241
18.3 擬合指數(shù)分布數(shù)據(jù) 242
18.4 當理論缺失時 245
第* 章 隨機試驗與假設檢驗 247
19.1 檢驗顯著性 248
19.2 當心P-值 252
19.3 單尾單樣本檢驗 254
19.4 是否顯著 255
19.5 哪個N 257
19.6 多重假設 258
第* 章 條件概率與貝葉斯統(tǒng)計 261
20.1 條件概率 262
20.2 貝葉斯定理 263
20.3 貝葉斯更新 264
第* 章 謊言、該死的謊言與統(tǒng)計學 267
21.1 垃圾輸入，垃圾輸出 267
21.2 檢驗是有缺陷的 268
21.3 圖形會騙人 268
21.4 Cum Hoc Ergo Propter Hoc 270
21.5 統(tǒng)計測量不能說明所有問題 271
21.6 抽樣偏差 272
21.7 上下文很重要 273
21.8 慎用外推法 273
21.9 得克薩斯神槍手謬誤 274
21.10 莫名其妙的百分比 276
21.11 不顯著的顯著統(tǒng)計差別 276
21.12 回歸假象 277
21.13 小心為上 278
第* 章 機器學習簡介 279
22.1 特征向量 281
22.2 距離度量 283
第* 章 聚類 288
23.1 Cluster類 289
23.2 K-均值聚類 291
23.3 虛構示例 292
23.4 更真實的示例 297
第* 章 分類方法 303
24.1 分類器評價 303
24.2 預測跑步者的性別 306
24.3 K-* 鄰近方法 308
24.4 基于回歸的分類器 312
24.5 從“泰坦尼克”號生還 320
24.6 總結 325
Python 3.5速查表 326
書單推薦
