本课程是“计算机科学导论”国家级精品课程的MOOC版本，本课程将课程的结构建立在计算学科认知模型的基础上，并以计算机科学的内容为背景，在学科思想与方法层面上对学生认知计算学科进行导引，借助大量案例，着力提高学生在复杂问题的分析和求解，系统设计，以及人类行为理解方面的计算思维能力。
—— 课程团队
课程概述
本课程是计算机类专业学生入学学习的第一门计算机基础必修课，它构建在计算学科认知模型的基础上，并以计算机科学的内容为背景，从学科思想与方法层面对计算学科进行导引，着力提高学生的计算思维能力。本课程来源于ACM教育委员会对“整个计算学科综述性导引”课程构建的要求，即用严密的方式将学生引入计算学科各个富有挑战性的领域之中。本课程为学生正确认知计算学科提供方法，为今后深入学习计算机课程作铺垫。
授课目标
本课程要求学生了解计算学科的认知模型；学科的基本问题；学科抽象、理论和设计三个形态；学科中的核心概念、数学方法、系统科学方法，以及社会和职业问题等内容。“复杂”这个词贯穿本课程的始终，要求学生通过大量案例的训练，初步掌握运用计算机科学的基础概念控制和降低复杂工程问题的思想与方法。
课程大纲
一、绪论
1.主要内容
（1）计算学科的定义；
（2）计算学科的根本问题；
（3）“计算机科学导论”课程的构建问题；
（4）计算学科认知模型——计算学科二维定义矩阵；
（5）计算思维与计算机科学导论。
2.基本要求
（1）了解计算学科的定义；
（2）了解计算学科的根本问题，即“能行性”问题；
（3）了解“计算机科学导论”课程构建问题提出的背景和意义；
（4）了解计算学科认知模型——计算学科二维定义矩阵提出的背景和意义；
（5）了解计算思维与计算机科学导论的关系。
3.重点、难点
重点：计算学科的根本问题，计算学科二维定义矩阵，计算思维与计算机科学导论。
难点：计算学科二维定义矩阵。
二、计算学科的基本问题
1.主要内容
（1）对问题进行抽象的典型实例——哥尼斯堡七桥问题；
（2）汉诺塔问题；
（3）停机问题；
（4）证比求易算法；
（5）P＝NP？；
（6）RSA公开密钥密码系统；
（7）旅行商问题与组合爆炸问题；
（8）找零问题、背包问题与贪婪算法；
（9）GOTO语句与程序设计中的结构问题；
（10）哲学家共餐问题与计算机系统中的软硬件资源的管理；
（11）两军问题与计算机网络；
（12）图灵测试与“中文屋子”；
（13）计算机中的博弈问题。
2.基本要求
（1）能够将一般的回路问题抽象成欧拉回路或者哈密尔顿回路问题，并对是否存在回路进行判定；
（2）初步掌握递归算法的构造，能够分析求解汉诺塔问题的时间复杂度（
）；
（3）通过停机问题理解不可计算问题；
（4）理解顺序算法和并行算法，并获得 “证比求易（verifying is easier than finding solutions）”这个元认知知识；
（5）区分P类问题和NP类问题，了解计算机技术发展中“P=NP?”问题提出的背景和意义；
（6）构建一个简单的RSA公开密钥密码系统，在该密码系统下进行信息的加密和解密；
（7）通过旅行商问题了解组合爆炸问题；
（8）理解简单的启发式算法，应用启发式的贪婪算法求解背包问题；
（9）理解程序结构设计的重要性，了解计算机技术发展中“GOTO语句有害”这一观点提出的背景和意义；
（10）能够对计算机资源管理的互斥问题进行简单分析；
（11）通过案例可以对网络协议的复杂性和微妙性进行简单分析，认知处理复杂系统所采用的分层抽象策略，了解使用该策略控制和降低系统复杂程度的重要作用；
（12）了解图灵对“机器思维”的定义，了解计算机技术发展中图灵测试提出的背景和意义，了解强人工智能与弱人工智能的不同，了解计算机技术发展中西尔勒中文屋子提出的背景和意义；
（13）通过计算机博弈问题初步了解人工智能领域研究工作的进展。
3.重点、难点
重点：汉诺塔问题，证比求易算法，P=NP?问题，RSA公开密钥密码系统，停机问题，找零问题、背包问题与贪婪算法，分支和循环结构的简单程序。
难点：汉诺塔问题的算法设计。
三、计算学科中的3个学科形态
1.主要内容
（1）一个关于“学生选课”的例子；
（2）抽象、理论和设计3个学科形态；
（3）自然语言与形式语言；
（4）图灵机的特征及其工作原理；
（5）冯·诺依曼计算机及基于冯·诺依曼计算机的Vcomputer实例；
（6）机器指令与汇编语言及基于Vcomputer机器的简单程序设计；
（7）虚拟机的层次结构及其意义和作用；
（8）高级语言、应用语言和自然语言的形式化问题。
2.基本要求
（1）初步掌握简单数据库系统的建模方法，实现客观世界到信息世界的抽象，了解建模在控制和降低软件复杂性方面的重要作用；将模型与实现绑定在一起，构建简单的关系数据库系统，对系统复杂性随实体和属性数量的增加而呈非线性增加有一个初步的了解；
（2）理解学科内容划分的背景和意义；
（3）通过实例加深对自然语言和形式语言的理解；
（4）理解提出通用计算机“图灵机”的背景与意义；
（5）理解计算机技术发展中冯·诺依曼计算机产生的背景与意义；加深对存储程序式计算机结构的理解，理解“程序与数据同样看待”这一思想的背景和重要意义；
（6）能够对计算机指令系统的两种设计思路进行简单评价；能够使用Vcomputer进行简单的机器指令和汇编指令的程序设计；
（7）理解控制复杂系统和降低其复杂程度的分层抽象策略，将该策略与虚拟机绑定在一起，理解虚拟机的重要作用；
（8）了解高级语言中有关抽象、理论和设计形态的主要内容，进一步理解这种划分的重要作用；应用语言及第四代语言的概念，教学目标-将第四代语言与软件生产效率绑定在一起，理解第四代语言的重要作用；了解计算机技术发展中语法形式化的背景和意义。
3.重点、难点
重点：E-R图的简单绘制，计算学科的三个学科形态（抽象，理论和设计）的区别，基于Vcomputer机器的程序设计；
难点：计算学科的三个学科形态（抽象，理论和设计）的区别，基于Vcomputer机器的程序设计。
四、计算学科中的核心概念
1.主要内容
（1）算法的基本知识；
（2）算法的四种表示方法；
（3）算法的分析；
（4）常见的两类算法：搜索与排序；
（5）数据结构及基于Vcomputer机器的数据结构；
（6）程序、软件和硬件的定义；
（7）数据的存储及表示；
（8）CC1991报告提取的12个核心概念。
2.基本要求
（1）了解算法的历史和简单的算法实例；了解算法的非形式化定义和算法的重要特性；了解算法的形式化定义；
（2）使用自然语言、流程图和伪代码描述算法，了解计算机程序设计语言对算法的描述方法；
（3）初步掌握大O记号估算简单算法时间复杂度的方法；
（4）能够应用折半搜索算法和归并排序算法求解实际问题；通过排序网络加深对并行计算的理解；了解计算机技术发展中Google与云计算产生的背景和影响；了解DARPA网络挑战赛的背景和影响；
（5）将数据结构的表示与Vcomputer机器绑定在一起，理解数据结构与机器的关系；了解线性表、栈和队列的定义、表示方法和基本操作；了解数组的定义、表示方法和基本操作，将数组存储和机器绑定在一起，进一步理解程序与机器的关系；了解树、二叉树和图的定义、表示方法和基本操作；了解线性表的存储结构及其表示方式；了解广义表的链式存储结构及其表示方式；了解二叉树的存储结构及其表示方式；了解图的存储结构及其表示方式；
（6）了解程序、软件和硬件的基本概念；
（7）加深学生对于进制转换的理解；了解“模”系统中，负数的表示方法及其运算；了解字符和字符串的表示方法；了解汉字在计算机内部的表示方法；了解计算机内表示图像的两种方法（位图和矢量图）；了解正弦音波的产生过程；
（8）记忆12个核心概念。
3.重点、难点
重点：算法的历史（含欧几里得算法教学实验），求解1+2+3+…+100的算法，求解调和级数的算法（含教学实验），求解斐波那契数列的算法，汉诺塔算法的时间复杂度分析，常见的两类算法：搜索与排序，基于排序网络对一组数进行排序，Vcomputer机器的数据结构，补码与模运算；
难点：求解斐波那契数列的算法，汉诺塔算法的时间复杂度分析，Vcomputer机器的数据结构，补码与模运算。
五、计算学科中的数学方法
1.主要内容
（1）数学的基本特征及数学方法的作用；
（2）计算学科中常用的数学概念和术语（集合，函数和关系，代数系统（含群、环、格、布尔代数，布尔代数与数字逻辑电路）；定义、定理和证明，必要条件和充分条件）；
（3）证明方法（直接证明和间接证明、反证法、归纳法、构造性证明）；
（4）递归和迭代；
（5）随机数和蒙特卡罗方法；
（6）公理化方法简介；
（7）形式化方法简介。
2.基本要求
（1）通过求解2的平方根的海伦算法，了解数学与计算机科学学科的区别；了解数学的基本特征及数学方法的作用；
（2）理解集合的概念、描述方法和基本运算；在认知等价类这个概念本质的基础上，理解网络的层次结构、冯·诺依曼计算机、虚拟机、分割、政企分开、传染病人隔离等类似的各种控制和降低非良好结构系统（问题）复杂程度的划分策略；解代数系统中的环、格和布尔代数之间的关系；了解定义、定理和证明的不同之处；能够在集合论的基础上采用必要条件和充分条件分析实际问题，了解分层抽象对控制软件系统复杂性的必要性；
（3）了解直接证明法和间接证明法；通过海伦算法求解2的平方根，用数学归纳法证明2的平方根是无理数，进一步理解数学与计算机科学的不同；
（4）将递归与数学归纳法绑定在一起，了解它们的区别和联系；通过实例进一步加深对递归概念的理解；
（5）了解产生伪随机数的方法；通过蒙特卡罗方法求解无序数列的现实问题；
（6）了解公理化方法的重要作用；了解公理化方法的基本要素；掌握构建公理化体系的基本方法；
（7）了解形式系统的局限性。
3.重点、难点
重点：等价类，必要条件和充分条件，蒙特卡洛方法的应用
难点：等价类，蒙特卡洛方法的应用
六、计算学科中的系统科学方法
1.主要内容
（1）系统科学与系统科学方法；
（2）人固有能力的局限性以及使用工具后产生力量的案例；
（3）复杂性的可操作性定义（含实例）及软件系统的复杂性；
（4）软件开发的系统化方法需要遵循的基本原则；
（5）使用系统方法的思考。
2.基本要求
（1）将布尔代数与数字逻辑电路绑定在一起，理解系统同构的性质和作用；通过5个小实例理解计算学科处理复杂系统采用的分层抽象策略，能够将该策略与等价类绑定在一起，知晓采用该策略控制和降低复杂系统的数学思想；了解系统科学尊遵循的一般原则及常见的几种系统科学方法；
（2）认知人固有能力的局限性，知晓采用系统科学方法控制和降低复杂性的重要作用；
（3）通过实例从程序员的角度认知复杂性；认知软件系统开发的难点在于对其概念结构（概念模型）的规格、设计和测试；
（4）认知软件开发这类特殊工程设计的复杂性；
（5）要求学生能将系统方法和软件研制的复杂性，以及抽象层次和人类分工的概念绑定在一起，能用系统方法中的结构和层次两个概念理解引入系统方法的目的之所在（降低和控制软件系统的复杂性）。
3.重点、难点
重点：系统同构，理解系统基本概念的5个实例，人固有能力的局限性以及使用工具后产生力量的案例，复杂性的可操作性定义，《人月神话》对软件复杂性的分析，使用系统方法的目的。
难点：系统同构，复杂性的可操作性定义，使用系统方法的目的。
七、社会和职业的问题
1.主要内容
（1）道德分析的方法（Kitchener的5条道德原则）；
（2）职业和道德责任（基于协议的职业化本质；有效的检举行为）；
（3）基于计算机系统的风险和责任；
（4）团队工作；
（5）知识产权；
（6）隐私和公民自由（基于Web的隐私保护技术）。
2.基本要求
（1）了解道德选择的一般步骤（算法），培养学生道德分析的职业习惯；
（2）能够从协议（模型）的角度理解职业化的本质，培养学生未来工作之后的职业精神；要求学生从过程的角度，区分什么是有效检举，什么不是，要求学生了解检举泛滥的危害，掌握有效检举的步骤（算法），培养学生进行有效检举的职业观念；
（3）要求学生在系统的设计过程中能够充分考虑经济、环境、法律、安全、健康、伦理等影响因素，培养学生未来从事专业工作的伦理规范；通过“Therac-25”事件案例分析计算机系统的风险，在设计安全至上的应用系统的时候，要充分考虑系统出现故障时，危害如何降至最低；
（4）了解团队最重要的特征（运作机制），了解提高团队业绩的两种常用方法（团队制和单一领导制），了解团队合作的困难。补充“小团队的敏捷开发案例”，了解这种实际使用并受到支持的特定软件开发方法，将经常交付、反思改进、渗透式交流、个人安全、焦点、与专家用户建立方便的联系、配有自动测试的技术环境等7个属性与小团队绑定在一起，了解卓越小团队成功的特征，为未来从事专业工作进行团队合作打下基础；
（5）了解知识产权的定义和重要作用；
（6）了解信息安全与隐私保护的相关技术。
3.重点、难点
重点：Kitchener的5条道德原则，基于“协议”的职业化本质，软件工程师的伦理规范，有效的检举行为，“Therac-25”事件，团队合作（含沟通）。
难点：软件工程师的伦理规范，有效的检举行为，团队合作（含沟通）。
八、探讨与展望
1.主要内容
（1）计算本质的认识历史；
（2）程序设计在计算学科中的地位；
（3）难度、复杂度与能力；
（4）SOLO分类法与浅层学习和深度学习；
（5）注意力。
2.基本要求
（1）了解计算本质的认识历史；
（2）了解程序设计在计算学科中的地位；
（3）掌握难度、复杂度与能力的关系；
（4）掌握SOLO分类法与浅层学习和深度学习的关系；
（5）了解注意力对学习和工作的重要作用。
3.重点、难点
重点： Bloom分类法，SOLO分类法，难度、复杂度与能力。
难点：难度、复杂度与能力。
预备知识
无
证书要求
设置“合格”（达到60分）、“优秀”（达到80分）两档课程标准。
参考资料
推荐教材：
1.董荣胜.计算机科学导论—思想与方法（第3版）.高等教育出版社,2015.07
2.董荣胜.计算思维的结构. 人民邮电出版社, 2017.08
参考教材：
1.董荣胜，古天龙.计算机科学与技术方法论.人民邮电出版社,2002
2.陈国良.大学计算机—计算思维视角（第2版）.高等教育出版社,2014
3.李廉.大学计算机教程—从计算到计算思维.高等教育出版社,2016
4.J.Glenn Brookshear著，刘艺等译.计算机科学概论（第11版）,人民邮电出版社,2011
5.赵致琢.计算科学导论（第三版）.科学出版社,2004
国家精品课程“计算机科学导论”网站：https://jpkc.guet.edu.cn/jsjkxdl/index.asp
常见问题
Q1：“计算机科学导论”课程是否比一门常见的计算机专业课程更为重要？
A1: 美国国家科学基金会的“重建多样性（Rebuilding the Mosaic）”报告认为，在处理几乎所有领域出现的新问题时，均需要使用和管理大规模的数据集。解决这些新问题，需要创造性地设计以数据为中心的问题解决方案，以及应用计算和计算机工具进行跨学科的研究。
为了应对以上需求，“计算机科学导论”课程的作用已逐步超出一门常见的计算机专业课程。这门课程越来越大的作用包括：
（1）它不仅需要为未来的计算机科学家和从业人员打下基础，而且还要激发学生对计算机科学的兴趣、动员和吸引新的学生加入计算机科学；
（2）此外，它还要为其他专业的学生提供计算思维的方法和计算机科学方面的技能；
（3）它甚至还要为未来讲授计算机科学的K-12教员提供培训。
摘自：Soh L K, Shell D F, Ingraham E, et al. Learning through computational creativity[J]. Communications of the ACM, 2015, 58(8):33-35
Q2：Bloom分类法和SOLO分类法降低了课程评估的复杂程度，为课程的开发提供了基本的依据。老师能用两个本课程的案例来佐证一下吗？
A2：Bloom分类法将人类思维的复杂程度划分为6个水平层次（记忆、理解、应用、分析、评估、创造），并认为这6个层次不是累积层次，即前一个层次不是后一个层次的基础，这一结论动摇了只有扎实的基础才能进行较高层次思维的论断，使人们可以在较短的时间内尽快进入到分析，评估和创造等较高层次的思维阶段。至于，记不住的知识可以查，不会的知识可以有针对性的在思维的过程中补。这一论断有重要的应用价值。本课程有大量的案例可以佐证，下面给出第2章的两个案例：
（1）案例1：汉诺塔问题。在没有介绍算法基础知识的情况下，在第2章的学习中，就让学生将数学归纳法与求解汉诺塔的递归算法绑定在一起，要求学生掌握简单递归算法的构建。
（2）案例2：RSA公开密钥密码系统。在学生没有任何密码学基础知识的情况下，在第2章的学习中，要求学生初步掌握RSA公开密钥密码系统的构建，这也是Bloom分类法和SOLO分类法的一个成功应用案例。
Q3：如何控制和降低“复杂问题”是本课程关注的重要内容，“复杂”这个关键词贯穿于本课程的始终，这个关键词正是国际工程教育专业认证的核心。请问，“计算机科学导论”课程各章节中的案例是如何支撑专业认证对本科生的12条毕业要求的？
A3：
【第1章】计算学科的认知问题是一个引发激烈争论的复杂问题。本章借助案例“计算学科的认知模型——计算学科二维定义矩阵”对计算学科的认知问题进行分析，降低了问题分析的复杂程度，符合“毕业要求2：问题分析”中要求在构建模型降低问题复杂程度的基础上，对复杂问题进行分析的要求。
注：本课程有大量符合“毕业要求”的具体案例，正是这些案例证明了本课程对复杂工程问题的处理是有方法的，再加上严格的训练就可以确保合格毕业生的质量。
【第2章】计算问题的复杂性体现在时间和空间两个方面。本章借助案例“汉诺塔问题”、“证比求易算法”、“阿姆达定律”认知计算复杂性。在此基础上，构建“轻量级”的RSA公开密钥密码系统，符合“毕业要求3：设计/开发解决方案”中设计满足特定需求系统的要求。
【第3章】如何将客观世界中的一类问题抽象到信息世界是复杂计算系统中的一个工程问题。本章借助案例“学生选课”，要求学生掌握简单的数据库应用系统的建模方法，理解实例属性的约束条件，实现客观世界到信息世界的抽象，了解系统复杂性随实体和属性数量的增加而呈非线性增加
的结果。借助案例“图灵机”、“冯诺依曼计算机”，加深对存储程序式计算机结构的理解，了解“程序与数据同样看待”这一思想的背景和重要意义。借助案例“虚拟机”和“Vcomputer机器”理解采用分层抽象降低和控制复杂系统的重要作用。符合“毕业要求1：工程知识”中将专业知识用于解决复杂工程问题的要求。
【第4章】数据结构与算法是复杂软件系统的基础。本章将数据结构与Vcomputer机器绑定在一起，降低了计算机软件系统理解的复杂性，符合“毕业要求1：工程知识”中将专业知识用于解决复杂工程问题的要求。
【第5章】计算机科学基础概念建立在数学集合概念的基础上，如何将集合中的元素变为有序，是降低软件系统复杂性的关键。本章借助“等价类”这个数学概念，要求学生将等价类与抽象层次这个计算思维中的重要概念绑定在一起，理解分层抽象、网络的层次结构、冯·诺依曼计算机、虚拟机、分割、政企分开、传染病人隔离等类似的各种控制和降低非良好结构系统（问题）复杂程度的划分策略及在计算学科工程实践中的巨大作用，符合“毕业要求1：工程知识”将数学知识用于解决复杂工程问题的要求。
本章还要求将将公理化方法与形式模型（形式化的公理体系）的构建绑定在一起，了解形式系统的局限性，掌握构建形式系统的基本方法，符合“毕业要求4：研究”中采用科学方法解决复杂工程问题的要求。
【第6章】软件的复杂度是软件生产的主要困难。本章将控制计算机软硬件系统复杂度的分层抽象思想与数学中的等价类绑定在一起，对软件复杂性进行分析，符合“毕业要求2：问题分析”应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析复杂工程问题，以获得有效结论的要求。
【第7章】本章采用计算机科学的思想与方法对学科的职业规范进行分析。比如，采用算法的思想培养学生道德分析的职业习惯；从协议（模型）的角度理解职业化的本质，培养学生的职业精神；从过程的角度，区分什么是有效检举，什么不是，要求学生了解检举泛滥的危害，掌握有效检举的步骤（算法），培养学生进行有效检举的职业观念。符合“毕业要求8：职业规范”中对遵守工程职业道德和规范，履行责任的要求。
本章借助案例“Therac-25”事件分析计算机系统的风险，在设计安全至上的应用系统的时候，要充分考虑系统出现故障时，危害如何降至最低。符合“毕业要求6：工程与社会”中专业工程实践和复杂工程问题解决方法对社会、健康、安全的影响，并理解应承担的责任。
本章要求学生了解团队最重要的特征（运作机制），了解提高团队业绩的两种常用方法（团队制和单一领导制），了解团队合作的困难，学习“小团队的敏捷开发案例”，了解这种实际使用并受到支持的特定软件开发方法，为未来从事专业工作进行团队合作打下基础。符合“毕业要求9：个人与团队”中能够在多学科背景下的团队中承担个体、团队成员以及负责人的角色的要求。
本章借助案例“小团队的敏捷开发案例”，了解这种实际使用并受到支持的特定软件开发方法，将经常交付、反思改进、渗透式交流（沟通）、个人安全、焦点、与专家用户建立方便的联系（沟通）、配有自动测试的技术环境等7个属性与小团队绑定在一起，了解卓越小团队成功的特征，在项目的开发过程中认知沟通的重要性。符合“毕业要求10：沟通”的要求。
【第8章】通过实例认知注意力，了解养成良好的思维习惯的重要性，为终身学习奠定认知基础；了解难度，复杂度与能力的不同，了解Bloom分类法的研究背景和意义，为终身学习奠定认知基础；区分浅层学习和深度学习，为终身学习奠定认知基础。符合“毕业要求12：终身学习”的要求，让学生在未来的学习和工作中终身受益。