内容简介

John V. Guttag 于1999—2004年任MIT电气工程与计算机科学系主任，所授计算机科学系列导论课程深受学生欢迎。目前为计算机科学与人工智能实验室网络及移动系统组联合负责人，还进行软件工程、机器定理证明、硬件验证等领域的研究以及培训工作。获美国布朗大学英语专业学士学位、应用数学硕士学位，多伦多大学计算机科学博士学位。

作品目录

第1章　启程 1
第2章　Python简介 6
2.1　Python基本元素 7
2.1.1　对象、表达式和数值类型 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章　一些简单的数值程序 20
3.1　穷举法 20
3.2　for循环 22
3.3　近似解和二分查找 24
3.4　关于浮点数 27
3.5　牛顿 拉弗森法 29
第4章　函数、作用域与抽象 31
4.1　函数与作用域 32
4.1.1　函数定义 32
4.1.2　关键字参数和默认值 33
4.1.3　作用域 34
4.2　规范 37
4.3　递归 39
4.3.1　斐波那契数列 40
4.3.2　回文 42
4.4　全局变量 45
4.5　模块 46
4.6　文件 47
第5章　结构化类型、可变性与
高阶函数 50
5.1　元组 50
5.2　范围 52
5.3　列表与可变性 52
5.3.1　克隆 57
5.3.2　列表推导 57
5.4　函数对象 58
5.5　字符串、元组、范围与列表 60
5.6　字典 61
第6章　测试与调试 65
6.1　测试 65
6.1.1　黑盒测试 66
6.1.2　白盒测试 68
6.1.3　执行测试 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　抽象数据类型与类 83
8.1.1　使用抽象数据类型设计程序 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　常数复杂度 107
9.3.2　对数复杂度 108
9.3.3　线性复杂度 108
9.3.4　对数线性复杂度 109
9.3.5　多项式复杂度 109
9.3.6　指数复杂度 111
9.3.7　复杂度对比 112
第10章　一些简单算法和数据结构 114
10.1　搜索算法 115
10.1.1　线性搜索与间接引用元素 115
10.1.2　二分查找和利用假设 116
10.2　排序算法 119
10.2.1　归并排序 120
10.2.2　将函数用作参数 122
10.2.3　Python中的排序 123
10.3　散列表 124
第11章　绘图以及类的进一步扩展 128
11.1　使用PyLab绘图 128
11.2　进阶示例：绘制抵押贷款 133
第12章　背包与图的* 优化问题 139
12.1　背包问题 139
12.1.1　贪婪算法 140
12.1.2　0/1背包问题的* 优解 143
12.2　图的* 优化问题 145
12.2.1　一些典型的图论问题 149
12.2.2　* 短路径：深度优先搜索和
广度优先搜索 149
第13章　动态规划 155
13.1　又见斐波那契数列 155
13.2　动态规划与0/1背包问题 157
13.3　动态规划与分治算法 162
第14章　随机游走与数据可视化 163
14.1　随机游走 163
14.2　醉汉游走 164
14.3　有偏随机游走 170
14.4　变幻莫测的田地 175
第15章　随机程序、概率与分布 178
15.1　随机程序 178
15.2　计算简单概率 180
15.3　统计推断 180
15.4　分布 192
15.4.1　概率分布 194
15.4.2　正态分布 195
15.4.3　连续型和离散型均匀分布 199
15.4.4　二项式分布与多项式分布 200
15.4.5　指数分布和几何分布 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
第17章　抽样与置信区间 220
17.1　对波士顿马拉松比赛进行抽样 220
17.2　中心极限定理 225
17.3　均值的标准误差 228
第18章　理解实验数据 231
18.1　弹簧的行为 231
18.2　弹丸的行为 238
18.2.1　可决系数 240
18.2.2　使用计算模型 241
18.3　拟合指数分布数据 242
18.4　当理论缺失时 245
第19章　随机试验与假设检验 247
19.1　检验显著性 248
19.2　当心P-值 252
19.3　单尾单样本检验 254
19.4　是否显著 255
19.5　哪个N 257
19.6　多重假设 258
第20章　条件概率与贝叶斯统计 261
20.1　条件概率 262
20.2　贝叶斯定理 263
20.3　贝叶斯更新 264
第21章　谎言、该死的谎言与统计学 267
21.1　垃圾输入，垃圾输出 267
21.2　检验是有缺陷的 268
21.3　图形会骗人 268
21.4　Cum Hoc Ergo Propter Hoc 270
21.5　统计测量不能说明所有问题 271
21.6　抽样偏差 272
21.7　上下文很重要 273
21.8　慎用外推法 273
21.9　得克萨斯神枪手谬误 274
21.10　莫名其妙的百分比 276
21.11　不显著的显著统计差别 276
21.12　回归假象 277
21.13　小心为上 278
第22章　机器学习简介 279
22.1　特征向量 281
22.2　距离度量 283
第23章　聚类 288
23.1　Cluster类 289
23.2　K-均值聚类 291
23.3　虚构示例 292
23.4　更真实的示例 297
第24章　分类方法 303
24.1　分类器评价 303
24.2　预测跑步者的性别 306
24.3　K-* 邻近方法 308
24.4　基于回归的分类器 312
24.5　从“泰坦尼克”号生还 320
24.6　总结 325
Python 3.5速查表 326
· · · · · ·

作者简介

John V. Guttag 于1999—2004年任MIT电气工程与计算机科学系主任，所授计算机科学系列导论课程深受学生欢迎。目前为计算机科学与人工智能实验室网络及移动系统组联合负责人，还进行软件工程、机器定理证明、硬件验证等领域的研究以及培训工作。获美国布朗大学英语专业学士学位、应用数学硕士学位，多伦多大学计算机科学博士学位。

精彩摘录

务必记住，最高效的算法不一定是最合适的算法。通常来说，最高效的算法都很难理解。一种比较好的解决策略是：首先找到最简单直接的解决方法，然后通过找到它的计算瓶颈，接着想办法提高和瓶颈相关的代码的计算复杂度，从而提高性能。

——引自第112页

Itispossibletodeceivestudentsintothinkingthattheyhavelearnedhowtoprogrambyhavingthemcompleteaseriesofhighlyconstrained"fillintheblank"programmingproblems.However,thisdoesnotpreparestudentsforfiguringouthowtoharnesscomputationalthinkingtosolveproblems.

——引自章节：Preface