（1）深度教育与职业素质教育相结合，从计算思维角度深入讲解计算机科学的*基础的概念和入门知识，更多的实例与职业素养则通过创新故事体现。（2）课堂讲授与学生动手动脑相结合，提供了习题、编程练习与大作业系统地培养实践能力。（3）适应32学时至64学时的“大学计算机基础”课程安排，教师可通过不同的裁减和深入讨论，适应不同的学时计划。
【内容简介】
本书从计算思维角度讲解计算机科学*基础的概念和入门知识，讨论计算思维的四种具体表现形式： 计算逻辑思维、算法思维、网络思维、计算系统思维。为了足够精准地描述信息变换过程，必须用信息的方式定义并推导信息变换过程涉及的“对”与“错”，哪些能计算，哪些不能计算。这是计算逻辑思维，它往往需要精确地定义计算模型。我们还需要从信息的角度发现和发明解决各类问题的精确方法，并评价什么是有效的方法。这是算法思维。有很多问题不是由单个算法解决，而是由多个算法形成网络来描述和解决。研究有效的网络需要网络思维。信息变换过程往往通过具体的计算设备与系统得以体现。如何设计、评价并使用计算抽象和实用的计算系统涉及计算系统思维。
【目录】
目录Contents第1章计算机科学概貌1
1.1什么是计算机科学2
1.1.1计算思维4
1.1.2步骤、符号、操作与计算过程8
1.1.3能够自动执行的抽象16
1.2计算机科学的发展实例18
1.2.1巴贝奇问题——计算机系统实例19
1.2.2布什问题——计算机使用模式实例21
1.2.3图灵问题——智能应用实例24
1.2.4计算机科学的三个奇妙之处29
1.3计算机科学的创新故事36
1.3.1文王演周易36
1.3.2自由软件的故事41
1.3.3为什么未来不需要我们46
1.4编程练习49
1.5习题53
第2章计算模型与逻辑思维54
2.1从一个实例看逻辑思维54
2.2逻辑思维要点55
2.2.1布尔逻辑55
2.2.2图灵机模型62
2.2.3悖论与不完备定理66
2.2.4能够自动执行的精准逻辑67
2.3计算逻辑的创新故事69
2.3.1布尔的故事69
2.3.2图灵的故事72◆计算机科学导论目录2.3.3臭虫与病毒73
2.4习题79
第3章算法思维81
3.1从一个实例看算法81
3.2算法思维的要点与实例83
3.2.1分治算法83
3.2.2其他算法实例90
3.2.3算法复杂度浅介96
3.3算法的创新故事98
3.3.1平稳复杂度98
3.3.2红帽的故事101
3.3.3创业公司五步曲103
3.4编程练习111
3.5习题113
第4章网络思维116
4.1从一个实例看网络与协议117
4.2网络思维的要点119
4.2.1名字空间119
4.2.2网络拓扑122
4.2.3互联网协议栈124
4.2.4服务质量与用户体验126
4.2.5网络的规律举例127
4.3网络的创新故事130
4.3.1ARPANET131
4.3.2以太网、路由器和TCP/IP协议134
4.3.3万维网139
4.3.4社交网络143
4.4编程练习145
4.5习题147
第5章系统思维150
5.1从一个实例看计算系统151
5.2计算系统思维要点153
5.2.1抽象化154
5.2.2模块化159
5.2.3无缝衔接172
5.2.4抽象是应对系统复杂度的利器179
5.3计算系统创新故事180
5.3.1半导体集成电路180
5.3.2计算机硬件188
5.3.3计算机软件213
5.4编程练习227
5.5习题232
第6章课程实践234
6.1构造图灵机实验234
6.1.1实验目的和原理234
6.1.2实验内容、方法和步骤235
6.1.3实验注意事项236
6.1.4成绩评定方法236
6.1.5思考题236
6.2算法游戏实验236
6.2.1实验目的和原理236
6.2.2实验内容、方法和步骤237
6.2.3实验注意事项238
6.2.4成绩评定方法238
6.2.5思考题238
6.3网络路由实验238
6.3.1实验目的和原理238
6.3.2实验内容、方法和步骤239
6.3.3实验注意事项240
6.3.4成绩评定方法241
6.3.5思考题241
6.4淝水之战系统实验241
6.4.1实验目的和原理241
6.4.2实验内容、方法和步骤242
6.4.3实验注意事项244
6.4.4成绩评定方法245
6.4.5思考题245
6.5班级快速排序实验245
6.5.1实验目的和原理245
6.5.2实验内容、方法和步骤246
6.5.3实验注意事项246
6.5.4成绩评定方法247
6.5.5思考题247
6.6莱布尼茨问题实验247
6.6.1实验目的和原理247
6.6.2实验内容、方法和步骤247
6.6.3实验注意事项248
6.6.4成绩评定方法248
6.7信息隐藏编程实验248
6.7.1实验目的和原理248
6.7.2实验准备249
6.7.3实验内容、方法和步骤258
6.7.4实验注意事项273
6.7.5成绩评定方法274
附录A计算机科学技术中常用的倍数和分数275
附录B原文阅读列表277
参考文献279
【前言】
献给我的母亲： 教书育人四十余年的彭老师。
徐志伟
献给我爱人Tracy和女儿Lulu，感谢你们的支持！
孙晓明····························································
前言Foreword大学计算机基础课程，往往称为“计算机科学导论”，正在经历一场变革，主要体现在三个方面。*，课程的受众正在扩大。例如，美国著名大学的“计算机科学导论”课程每学期的学生数过去10年增长了50%，一门课程的学生数往往超过700人。第二，课程的内容正在从传统的讲历史发展、讲入门工具使用、讲初阶编程，过渡到讲计算思维。第三，课程的形式正在变得更加丰富，包括课堂讲授、动手动脑实践、慕课、翻转课堂等各种组合。
本书是为中国大学的“计算机科学导论”课程设计的，考虑了全球发展趋势与中国的实际情况，具备下述四个特点。
(1) 强调计算思维。本书试图突出计算机科学*本质的特征： 计算机科学是研究计算过程的科学，计算过程是通过操作数字符号变换信息的过程。*本质的解决问题方法是计算思维，包括逻辑思维、算法思维、网络思维和系统思维。
(2) 强调基础知识。本书并不追求覆盖众多的时髦名词或新概念，而是突出计算机科学不过时的*基础的知识点，并将它们组织成对计算思维的10个理解： 自动执行、正确性、通用性、构造性、复杂度、连通性、协议栈、抽象化、模块化、无缝衔接。
(3) 鼓励主动学习。本书的设计鼓励同学们自学，但教师讲解与课堂互动有利于揭示要点、提高学习效率。本书还提供了一些动手动脑的大作业和编程练习，对应于逻辑、算法、网络和系统四大内容。
(4) 鼓励扩展眼界。除了理论内容外，本书提供了较多的实例，涵盖计算机科学及其应用和社会影响。本书花了大约三分之一的篇幅讲解计算机领域的真实的创新故事，让同学们了解前人如何通过计算思维认识世界、提出问题、解决问题。这些创新故事对同学们形成计算机科学领域的学术道德和职业精神也有裨益。
本书的构思与写作持续了五年时间，主要的难点是如何体现计算思维。作者要感谢北京大学李晓明教授，他多年来一直鼓励和敦促我们写一本计算机科学导论教科书。感谢时任美国国家科学基金会副主任的周以真(Jeannette M. Wing)博士，她多次与我们讨论计算思维的要点。感谢中国科技大学陈国良教授与合肥工业大学李廉教授，以及他们领导的大学计算机基础课程教学指导委员会。这些老师花了很多精力在中国推动计算思维改革，为本书提供了很多经验。特别感谢中国科学院大学的同学们，他们是本书的*批读者，也是本书作为教科书的“计算机科学导论”课程的*批实践者。感谢中国科学院计算技术研究所的博士生朝鲁和李春典，他们担任了课程的助教并撰写了课程实践部分的内容。
本书引用了业界的大量素材，在此一并致谢。我们要感谢开源社区，尤其是LAMP(Linux、Apache、MySQL、Python)社区。感谢学术社区，尤其是ACM(Association for Computing Machinery)、IEEE Computer Society、CCF(中国计算机学会)。ACM与IEEE Computer Society是全球*的计算机科学技术领域的国际学术社区，分别有10万与6万多名会员。CCF有3万多名会员，是全球第三大计算机学会。
我们还要感谢众多的公司，本书合理使用了它们的素材(例如公司名称、技术和产品名称、logo标志)，这些名称和标志都是这些公司的知识产权。这些公司包括曙光、联想、龙芯、华为、腾讯、百度、IBM、英特尔、谷歌、脸谱网、领英、AT&T、思科、红帽、通用电气、微软、甲骨文、乐高等。免责声明： 除了已经公开发表的材料外，本书使用这些公司的例子都做了抽象加工，没有泄露这些公司的隐私。
孙晓明徐志伟
2017年夏于北京中关村
◆计算机科学导论
【免费在线读】
第3章chapter3
算 法 思 维第2章讲述了计算过程的正确性与图灵机的通用性。假设我们已知一个问题是可计算的，可能存在许多计算过程去解决该问题。算法思维的目的是找出求解该问题的巧妙的计算过程，使得计算时间短、使用的计算资源少。巧妙的计算过程所体现的方法称为算法。3.1从一个实例看算法我们从计算机领域内的一个经典问题——排序问题开始。排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列按照大小关系调整为“有序”的记录序列。为了简单起见，假设排序的记录都是正整数；这些正整数的个数是已知的；这些正整数各不相同；要把这些正整数从小到大排序。为了求解排序问题，人们发展了各种各样的算法，例如冒泡排序、选择排序、快速排序、归并排序、堆排序等。在这一节里以冒泡排序算法为例介绍算法是如何运行的，在后续的章节中还会介绍更复杂的快速排序算法。冒泡排序的原理是： 每次将相邻的数字进行比较，按照小的排在左边，大的排在右边进行交换。这样一趟过去后，*的数字被交换到了*后的位置，然后再从头开始进行两两比较交换，直到比较到倒数第二个数时结束，以此类推。举例如下。 假设原始待排序数组6, 2, 4, 1, 5, 9*趟排序(外循环)： *次比较，6>2交换交换前状态 6, 2, 4, 1, 5, 9→交换后状态2, 6, 4, 1, 5, 9第二次比较，6>4交换交换前状态 2, 6, 4, 1, 5, 9→交换后状态2, 4, 6, 1, 5, 9第三次比较，6>1交换交换前状态 2, 4, 6, 1, 5, 9→交换后状态2, 4, 1, 6, 5, 9第四次比较，6>5交换交换前状态 2, 4, 1, 6, 5, 9→交换后状态2, 4, 1, 5, 6, 9第五次比较，6<9不交换◆计算机科学导论第◆3章算法思维第二趟排序(外循环)： *次比较，2<4不交换第二次比较，4>1交换交换前状态 2, 4, 1, 5, 6, 9→交换后状态2, 1, 4, 5, 6, 9第三次比较，4<5不交换第四次比较，5<6不交换第三趟排序(外循环)： *次比较，2>1交换交换前状态 2, 1, 4, 5, 6, 9→交换后状态1, 2, 4, 5, 6, 9第二次比较，2<4不交换第三次比较，4<5不交换第四趟排序(外循环)无交换。第五趟排序(外循环)无交换。排序完毕，输出*终结果1 2 4 5 6 9。“冒泡排序”这个名字的由来是因为大的数字会经由交换慢慢“浮”到数列的*，就像气泡从水底冒上来一样。下面给出算法的形式化描述。冒泡排序算法输入： 待排序的数组A，数组A的长度n。输出： 排好序的数组A。算法描述： for i=1 to n-1for j=1 to n-iif A\[j\]>A\[j 1\]exchangeA\[j\] with A\[j 1\].一般地，可以采用如下来自高德纳教授的算法定义高德纳.计算机程序设计艺术： 第1卷 基本算法［M］.3版.苏运霖,译.北京： 国防工业出版社，2002.。高德纳的算法定义一个算法是一组有穷的规则，给出求解特定类型问题的运算序列，并具备下列五个特征。 （1） 有穷性： 一个算法在有限步骤之后必然要终止。（2） 确定性： 一个算法的每个步骤都必须精确地（严格地和无歧义地）定义。（3） 输入： 一个算法有零个或多个输入。（4） 输出： 一个算法有一个或多个输出。（5） 能行性： 一个算法的所有运算必须是充分基本的，原则上人们用笔和纸可以在有限时间内精确地完成它们。冒泡排序的算法描述定义了求解排序问题的一组有穷的规则，这组规则符合算法的五个特征。(1) 有穷性。分析可知，冒泡排序的外层循环需执行n-1次；对于确定的i，内层循环需执行n-i次。因此，算法在∑n-1i=1(n-i)=n(n-1)/2步内必然终止。
【书摘与插画】
