计算机科学导论
分享
课程详情
课程评价
spContent=本课程是“计算机科学导论”国家级精品课程的MOOC版本,本课程将课程的结构建立在计算学科认知模型的基础上,并以计算机科学的内容为背景,在学科思想与方法层面上对学生认知计算学科进行导引,借助大量案例,着力提高学生在复杂问题的分析和求解,系统设计,以及人类行为理解方面的计算思维能力。
—— 课程团队
课程概述

本课程是计算机类专业学生入学学习的第一门计算机基础必修课,它构建在计算学科认知模型的基础上,并以计算机科学的内容为背景,从学科思想与方法层面对计算学科进行导引,着力提高学生的计算思维能力。本课程来源于ACM教育委员会对“整个计算学科综述性导引”课程构建的要求,即用严密的方式将学生引入计算学科各个富有挑战性的领域之中。本课程为学生正确认知计算学科提供方法,为今后深入学习计算机课程作铺垫。



                 

授课目标

本课程要求学生了解计算学科的认知模型;学科的基本问题;学科抽象、理论和设计三个形态;学科中的核心概念、数学方法、系统科学方法,以及社会和职业问题等内容。“复杂”这个词贯穿本课程的始终,要求学生通过大量案例的训练,初步掌握运用计算机科学的基础概念控制和降低复杂工程问题的思想与方法。

课程大纲

第1章 绪论

【第1课时】计算机科学导论课程的构建问题

【第2课时】计算思维与计算机科学导论

【教学文档】

【控制和降低复杂工程问题的讨论-贯穿全课程】

【习题1】

【单元测验1】

【讨论1-0】

第2章 计算学科的基本问题

【第10课时】停机问题

【第1课时】哥尼斯堡七桥问题

【第2课时】汉诺塔问题

【第3课时】证比求易算法和P=NP?

【第4课时】RSA公开密钥密码系统

【第5课时】旅行商问题与组合爆炸

【第6课时】GOTO与程序结构

【第7课时】哲学家共餐问题

【第8课时】两军问题

【第9课时】图灵测试

【教学文档】

【习题2】

【单元测验2】

【第11课时】找零问题、背包问题与贪婪算法

第3章 计算学科的3个学科形态

【第1课时】学生选课实例

【第2课时】自然语言与形式语言

【第3课时】自然语言形式化及实例

【第4课时】图灵机的工作原理

【第5课时】VComputer软件的演示、说明及下载使用

【教学文档】

【习题3】

【单元测验3】

实验一 分支和循环结构的简单程序设计

【视频】Raptor使用介绍(注:如果无法播放视频,请切换到兼容模式或者使用Chrome、IE、火狐浏览器)

【文档】实验内容

【程序及文档】实验答案

选择结构(热身实验)

循环结构(热身实验)

性能分析(热身实验)

求平方根的“亚历山大的海伦算法”(进阶实验)

两个正整数求和的算法(进阶实验)

两个整数较大值的判定(进阶实验)

输出1至10的累加和(进阶实验)

三个数最大值的判定(进阶实验)

两个循环嵌套程序效率的比较(进阶实验)

分段函数求解(综合实验)

农场主问题(综合实验)

金字塔图形的输出(综合实验)

二分支函数(综合实验)

实验二 RSA公开密钥密码系统

【文档】实验内容

【程序及文档】实验答案

质数判定(热身实验)

输出给定区间内质数(热身实验)

欧拉函数(热身实验)

RSA公开密钥密码系统的构建(进阶实验)

RSA公开密钥密码系统的加密和解密(进阶实验)

实验三 存储程序式计算机的简单程序设计

【视频】Vcomputer软件演示

【文档】实验内容

【程序及文档】实验答案

一个机器指令程序的执行过程(热身实验)

一个汇编指令程序的执行过程(热身实验)

一个机器指令程序的简单修改(热身实验)

一个机器指令程序的简单设计(热身实验)

分段函数的求解(进阶实验)

累加求和(进阶实验)

迭代求和(进阶实验)

第4章 计算学科的核心概念

【第1课时】算法的基本知识

【第2课时】两个常见的算法

【第3课时】数据结构

【第4课时】数据的存储和表示

【教学文档】

【习题4】

【单元测验4】

实验四 递归算法、迭代算法及其比较

【视频】迭代与递归

【文档】实验内容

【程序及文档】实验答案

斐波那契数列的迭代实现(热身实验)

斐波那契数列的递归实现(热身实验)

n!的迭代求解(进阶实验)

n!的递归求解(进阶实验)

汉诺塔问题的递归算法(进阶实验)

求f(a,b)=a^b(进阶实验)

猴子吃桃(综合实验)

判断回文(综合实验)

递归画二叉树(扩展实验)

第5章 计算学科中的数学方法

【第1课时】递归与迭代

【教学文档】

【习题5】

【单元测验5】

【第2课时】随机数和蒙特卡罗方法

实验五 数组实验

【视频】一维数组热身实验

【文档】实验内容

【程序及文档】实验答案

一维数组实验(热身实验)

二维数组实验(热身实验)

创建长度为100的数组(进阶实验)

创建长度为100的数组并对数组元素赋值(进阶实验)

存储斐波那契数列的前20项(进阶实验)

二维数组(进阶实验)

字符数组中单空格替换为双空格(综合实验)

二维数组中元素的查找(综合实验)

单重循环完成二分支函数(综合实验)

第6章 计算学科中的系统科学方法

【第3课时】软件开发的系统化方法需要遵循的基本原则

【第1课时】系统同构

【教学文档】

【习题6】

【单元测验6】

【第2课时】人固有能力的局限性及使用工具后产生的力量

实验六 栈的基本操作:push和pop

【文档】实验内容

【程序及文档】实验答案

模拟栈操作(热身实验)

两个栈用一个数组的表示(进阶实验)

两个栈模拟一个队列(进阶实验)

括号匹配的检验(综合实验)

第7章 社会与职业问题

【第1课时】道德选择

【第2课时】检举

【教学文档】

【习题7】

【单元测验7】

实验七 归并排序与折半查找

【视频】归并排序与折半查找

【文档】实验内容

【程序及文档】实验答案

子数组的合并算法(热身实验)

二路归并排序(热身实验)

折半查找(热身实验)

查找和为x的两个元素(进阶实验)

背包问题(进阶实验)

轮转数组内数值的查找(综合实验)

第8章 探讨与展望

【第1课时】难度、复杂度与能力

【第2课时】SOLO分类法

【教学文档】

【习题8】

【单元测验8】

实验八 蒙特卡洛方法应用

【视频】蒙特卡洛方法求π的程序示例

【文档】实验内容

【程序及文档】实验答案

基于蒙特卡洛方法对圆周率π的求解(热身实验)

基于蒙特卡洛方法对椭圆面积的求解(热身实验)

基于蒙特卡洛方法对简单曲线下面积的求解(进阶实验)

基于蒙特卡洛方法对球体在第一卦限体积的求解(进阶实验)

基于蒙特卡洛方法对曲线下面积的求解(综合实验)

基于蒙特卡洛方法对椭球在第一卦限体积的求解(综合实验)

基于蒙特卡洛方法对抛物面相交部分体积的求解(综合实验)

实验九 简单的卡通与游戏实验

【文档】实验内容

【程序及文档】实验答案

绘制一个Hello Kitty(热身实验)

绘制一朵花(进阶实验)

设计一个“找茬”游戏(综合实验)

实验十 基于Access的简单数据库设计

【视频】建数据库、建表及建立表间关系

【视频】创建查询

【视频】创建窗体

【视频】创建报表

【视频】热身实验前两问答案

【视频】热身实验第三问答案

【视频】进阶实验答案

【文档】实验内容

【程序及文档】实验答案

学生信息管理系统的查询实验(热身实验)

学生信息管理系统的“瘦身”(热身实验)

学生信息管理系统的“复原”(热身实验)

学生信息管理系统的扩展实验(进阶实验)

学生信息管理扩展系统的综合查询实验(进阶实验)

预备知识

证书要求

设置“合格”(达到60分)、“优秀”(达到80分)两档课程标准。

参考资料

推荐教材:

1.董荣胜.计算机科学导论—思想与方法(第3版).高等教育出版社,2015.07

2.董荣胜.计算思维的结构. 人民邮电出版社, 2017.08


参考教材:

1.董荣胜,古天龙.计算机科学与技术方法论.人民邮电出版社,2002

2.陈国良.大学计算机—计算思维视角(第2版).高等教育出版社,2014

3.李廉.大学计算机教程—从计算到计算思维.高等教育出版社,2016

4.J.Glenn Brookshear著,刘艺等译.计算机科学概论(第11版),人民邮电出版社,2011

5.赵致琢.计算科学导论(第三版).科学出版社,2004

 

国家精品课程“计算机科学导论”网站:http://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


Q2Bloom分类法和SOLO分类法降低了课程评估的复杂程度,为课程的开发提供了基本的依据。老师能用两个本课程的案例来佐证一下吗?

A2Bloom分类法将人类思维的复杂程度划分为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:终身学习”的要求,让学生在未来的学习和工作中终身受益。