图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 内 容 提 要 本书基于 MIT 编程思维培训讲义写成，主要目标在于帮助读者掌握并熟练使用各种计算技术，具备用 计算思维解决现实问题的能力。书中以 Python 3 为例，介绍了对中等规模程序的系统性组织、编写、调试， 帮助读者深入理解计算复杂度，还讲解了有用的算法和问题简化技术，并探讨各类计算工具的使用。与本 书第 1 版相比，第 2 版全面改写了后半部分，且书中所有示例代码都从 Python 2 换成了 Python 3。 本书适合对编程知之甚少但想要使用计算方法解决问题的读者。 ◆ 著　　　　[美] John V. Guttag 译　　　　陈光欣 责任编辑　陈　曦 责任印制　周昇亮 ◆ 人民邮电出版社出版发行　　北京市丰台区成寿寺路11号 邮编　100164　　电子邮件　315@ptpress.com.cn 网址　http://www.ptpress.com.cn 北京　　　　　　印刷 ◆ 开本：800×1000　1/16 印张：21.25 字数：502千字 印数：1 — 3 500册 著作权合同登记号 2018年 2 月第 1 版 2018年 2 月北京第 1 次印刷 图字：01-2017-1465号 定价：69.00元 读者服务热线：(010)51095186转600　印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广登字 20170147 号 版权声明 Copyright © 2016 Massachusetts Institute of Technology. Published in the English language under the title Introduction to computation and programming using Python : with application to understanding data. Simplified Chinese-language edition copyright © 2018 by Posts & Telecom Press. All rights reserved. 本书中文简体字版由The MIT Press授权人民邮电出版社独家出版。未经出版者书面许可，不 得以任何方式复制或抄袭本书内容。 版权所有，侵权必究。 9 前 言 1 1 前 言 本书基于MIT的一门课程写成，这门课程始于2006年，自2012年起，成为edX和MITx上的一 门“大规模在线开放课程” （Massive Online Open Courses，MOOC）。本书第1版基于一个学期的 课程，但随着时间的推移，我不得不添加更多内容，再用一学期来讲述课程已经不合适了。现在 的这个版本适合于两学期的计算机科学系列导论课程。 当我开始编写第2版时，本以为只要加上几章内容就可以了，但结果远超预料。我重新组织 了本书的后半部分，并将整本书中的代码从Python 2换成了Python 3。 本书面向的是那些没有或只有很少编程经验，但希望掌握计算方法来解决问题的学生。书中 的内容是一些学生学习更高级计算机科学课程的跳板，但对更多学生来说，则是正式学习计算机 科学的一门课程。 正因如此，所以我们更强调课程的广度，而不是深度。课程的目标是为学生简述更多的主题， 使他们在想用计算机完成目标时知道自己能做什么。尽管如此，这并不是一门“计算机鉴赏”课 程，要求比较严格，而且有一定难度。读者需要花费大量时间和精力才能真正掌握书中内容，使 计算机服从自己的调遣。 本书的主要目标是帮助学生掌握并熟练使用各种计算技术，以得到有价值的成果。他们应该 学会使用计算思维表述问题，并掌握如何从数据中提取信息。学生从本书中获得的最重要的能力 是，使用计算思维解决问题的艺术。 这本书很难纳入传统的计算机科学课程。第1~11章是典型的针对没有或只有很少编程经验的 学生的计算机科学课程；第12~14章稍微高级一些，如果想学习进阶技术，可以从这几章挑选些 内容，作为导论课程的补充；第15~24章介绍如何使用计算技术来理解数据，我们认为其中的内 容应该成为计算机科学课程体系中的第二门课程（代替传统的数据结构课程）。 第1~11章主要包含五个方面的内容：  编程基础  Python 3编程语言  计算问题的解决技术  计算复杂度  使用图形表示信息 我们会介绍Python语言的大部分特性，但重点在于可以使用编程语言做什么，而不是语言本 身。比如，第3章结束时虽然只介绍了Python语言的一小部分，但已经引入穷举的概念、猜测与 2 3 4 5 6 7 8 9 10 11 2 前 言 验证算法、二分查找和高效近似算法。纵贯本书，我们都会介绍Python的特性。同样地，本书从 头至尾也会介绍编程方法。我们的理念是帮助学生们掌握Python，并成为一个优秀的程序员，能 够使用计算技术解决自己感兴趣的问题。 书中示例都使用Python 3.5进行了测试。Python 3修正了Python 2各种发布版本（通常称为 Python 2.x）在设计上的很多不一致性，但它不是向后兼容的，这意味着大多数使用Python 2编 写的程序不能在Python 3中正常运行。因为这个原因，Python 2.x还在被广泛使用。第一次使用 Python 3中不同于Python 2的特性时，我们都会明确指出如何在Python 2中完成相同功能。书中 所有示例都有Python 3.5和Python 2.7的在线版本。 第12~13章介绍了优化，这是一个虽然重要但很少包含在导论课程中的主题。第14~16章介绍 了随机规划，这也是一个虽然重要但很少包含在导论课程中的主题。我们在MIT授课的经验是， 在一个学期的导论课程中，或者可以讲述第12~13章的内容，或者可以讲述第14~16章的内容，但 不能二者兼顾。 第15~24章在设计上是独立成篇的，内容涉及如何使用计算技术来理解数据。其中使用的数学 知识不超出高中代数的范围，但要求读者具有严谨的思维能力，且不会被数学概念吓倒。这一部 分包括多数导论课程中没有的内容：数据可视化、模拟模型、概率与统计思维，以及机器学习。 我们相信对大多数学生来说，这部分内容远比那些典型的第二门计算机科学课程的内容更有意义。 我们没有在每章末尾设置习题，而是在每章的适当部分插入了“实际练习” 。有些练习非常 简短，目的是使读者确认自己确实明白了刚刚学过的内容。有些练习增加了一点挑战性，适合在 考试时使用。其余练习的难度比较大，可以作为课后作业。 本书有三个普适性主题：系统的问题解决方式、抽象能力，以及将计算思维作为思考世界的 一种方式。学完本书后，你应该：  学会使用Python语言进行编程和计算；  学会系统性地组织、编写、调试中等规模的程序；  理解计算复杂度；  将模糊的问题描述转化为明确的计算方法，以此解决问题，并对这个过程有深刻的理解；  掌握一些有用的算法以及问题简化技术；  对于那些很难得到封闭解的问题，知道如何使用随机性和模拟技术进行清晰阐述；  学会使用计算工具（包括简单的统计、可视化以及机器学习工具）对数据进行理解与建模。 编程本身就是一项非常困难的活动。正如那句名言所说：“在几何中，没有专为国王铺设的 大道。 ”①对于编程来说，也没有捷径可走。如果你想真正掌握书中的内容，光阅读是不够的，还 应该亲自运行书中的代码。2008年以来，本书基于的各种课程都放在MIT的开放课程网站 （OpenCourseWare，OCW）上。这里有授课过程的视频录像，以及一系列习题和考题。从2012年 秋季开始，我们在edX和MITx上提供了在线课程，其中包括本书的大部分内容。我们强烈推荐你 做做OCW和edX上提供的习题。 —————————— ① 据传，公元前300年左右，托勒密国王希望有学习数学的捷径。对于这个要求，欧几里得给出了这样的回答。 前 电子书 言 3 1 如需购买本书电子版，请扫描以下二维码。 2 3 4 5 6 7 8 9 10 11 图灵社区会员 ChenyangGao(2339083510@qq.com) 专享 尊重版权 8 前 言 致 谢 本书第1版基于我在MIT教授的本科生课程讲义，这门课程——当然也包括这本书——得益 于我的教师同事（尤其是Ana Bell、Eric Grimson、Srinivas Devadas、Fredo Durand、Ron Rivest 和Chris Terman）、助教以及学习该课程的学生。David Guttag克服了他对计算机科学的厌恶，对 本书的多个章节进行了校对。 和所有成功的教授一样，我要向我的研究生表示万分感激。Guha Balakrishnan、David Blalock、 Joel Brooks、Ganeshapillai Gartheeban、Jen Gong、Yun Liu、Anima Singh、Jenna Wiens和Amy Zhao 这些学生不但进行了非常出色的研究工作（我也由此获得了一些好评），还都对本书的草稿提出 了非常宝贵的意见。 我要向Julie Sussman表示由衷的感谢。我开始和她接触后，才知道一个优秀的编辑竟然会如 此出色。以前出书时，与我合作的文字编辑也非常能干，因而我觉得这本书有文字编辑也就够了， 但我错了。我需要合作者可以从学生视角审视本书，并且告诉我需要做什么、应该做什么和能够 做什么——如果我有时间和精力的话。Julie给我的好建议数不胜数，而且都切中要害，不可忽视。 不论是在语言方面还是在编程方面，Julie都有极为深厚的造诣。 最后，感谢我的妻子Olga，她一直督促我完成这本书。感谢她帮助我承担了很多家庭义务， 这样我才能专心于此。 目 录 1 2 目 录 3 4 第1章 启程 ..................................................... 1 第2章 Python 简介 ....................................... 6 2.1 2.2 2.3 2.4 第3章 3.1 3.