计算机科学概论 Python版

·美国知名的理工高校哈维玛德学院开发的“计算机科学通识”课程教材
·美国克莱蒙特学院联盟的众多名校采用
·用独特的方法介绍计算机科学，带领读者进入这一充满智慧和活力的知识领域
·随书附赠大量教学资源，包括完整的授课PPT、丰富的每周作业集、一些附带的软件和文档，下载方式请见前言部分的配套网站

本书是美国哈维玛德学院 “计算机科学通识”课程的配套教材，用独特的方法介绍计算机科学，带领读者进入这一充满智慧和活力的知识领域。
全书共7章。章介绍计算机科学的概念，引入了用于控制虚拟的“Picobot”机器人的一种简单的编程语言；第2章和第3章介绍Python编程语言，并且结合Python介绍了函数式编程的思想和概念；第4章深入计算机的内部工作原理，从数字逻辑到机器组织，再到用机器语言编程；第5章探讨计算中更复杂的思想，同时探讨诸如引用和可变性等概念，以及包括循环在内的构造、数组和字典；第6章探讨面向对象编程和设计中的一些关键思想；第7章针对问题解决，在计算复杂性和可计算性方面，提供了一些优雅的，但数学上很好合理的处理方法，很终证明了计算机上无法解决的许多计算问题。
本书适合想要通过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