1、第二讲 计算机科学的内容计算机科学的内容n计算学科的根本问题计算学科的根本问题n三个学科形态三个学科形态n主要领域基本问题主要领域基本问题n典型问题示例典型问题示例计算机科学的根本问题计算机科学的根本问题 n计算机科学与计算科学 定义：定义：计算学科是对描述和变换信息的算计算学科是对描述和变换信息的算 法过程，包括对其理论分析、设计、法过程，包括对其理论分析、设计、效率实现和应用等进行的系统研究。效率实现和应用等进行的系统研究。n计算学科的根本问题 计算学科的根本问题是什么能被有计算学科的根本问题是什么能被有 效地自动进行效地自动进行。计算学科中的计算学科中的3个学科形态个学科形态 n抽象形态
2、抽象形态 学科中的抽象形态包含着学科中所具有的科学学科中的抽象形态包含着学科中所具有的科学概念、科学符号和思想模型。按客观现象的研概念、科学符号和思想模型。按客观现象的研究过程，抽象形态包括以下究过程，抽象形态包括以下4 4个步骤的内容：个步骤的内容：1 1）形成假设形成假设 2 2）建造模型并作出预测建造模型并作出预测 3 3）设计实验并收集数据设计实验并收集数据 4 4）对结果进行分析对结果进行分析 计算学科中的3个学科形态 n理论形态理论形态 理论是经过实践检验的系统化了的科学知识体系，理论是经过实践检验的系统化了的科学知识体系，由科学概念、科学原理以及对这些概念原理的理由科学概念、科学
3、原理以及对这些概念原理的理论论证所组成的体系。在计算学科中，理论形态论论证所组成的体系。在计算学科中，理论形态包括以下包括以下4 4个步骤的内容：个步骤的内容：1 1）表述研究对象的特征定义和公理表述研究对象的特征定义和公理 2 2）假设对象之间的基本性质和对象之间可能存在假设对象之间的基本性质和对象之间可能存在 的关系定理的关系定理 3 3）确定这些关系是否为真证明确定这些关系是否为真证明 4 4）结论结论 计算学科中的计算学科中的3个学科形态个学科形态 n设计形态设计形态 设计形态具有较强的实践性，社会性和综合性。设计形态具有较强的实践性，社会性和综合性。在计算学科中，从为解决某个问题而实
4、现系统或在计算学科中，从为解决某个问题而实现系统或装置的过程来看，设计形态包括以下装置的过程来看，设计形态包括以下4 4个步骤的内个步骤的内容：容：1 1）需求分析需求分析 2 2）建立规格说明建立规格说明 3 3）设计并实现该系统设计并实现该系统 4 4）对系统进行测试与分析对系统进行测试与分析 计算学科中的计算学科中的3个学科形态个学科形态 n三种形态关系三种形态关系 设计、抽象和理论设计、抽象和理论3 3个形态针对具体的研究领个形态针对具体的研究领域均起作用，在具体研究中，就是要在其理域均起作用，在具体研究中，就是要在其理论的指导下，运用其抽象工具进行各种设计论的指导下，运用其抽象工具进
5、行各种设计工作，最终的成果将是计算机的软硬件系统工作，最终的成果将是计算机的软硬件系统及其相关资料。及其相关资料。抽象源于现实世界 理论源于数学 设计源于工程 计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n离散结构离散结构 主要内容：包括集合论、数理逻辑、主要内容：包括集合论、数理逻辑、近世代数、图论、以及组合数学等。近世代数、图论、以及组合数学等。计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n程序设计基础程序设计基础 1 1）主要内容：包括程序设计结构、算法、问主要内容：包括程序设计结构、算法、问 题求解和数据结构等题求解和数据结构等 2 2）基本问题主要包括：基
6、本问题主要包括：对给定的问题，如何进行有效的描述并给对给定的问题，如何进行有效的描述并给 出算法？出算法？如何正确选择数据结构？如何正确选择数据结构？如何进行设计、编码、测试和调试程序？如何进行设计、编码、测试和调试程序？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n算法与复杂性算法与复杂性 1)主要内容：包括算法的复杂度分析、典型主要内容：包括算法的复杂度分析、典型的算法策略、分布式算法、并行算法、可计算的算法策略、分布式算法、并行算法、可计算理论、自动机理论、密码算法等理论、自动机理论、密码算法等 2 2）基本问题主要包括基本问题主要包括 对于给定的问题类，最好的算法是什么？
7、要求对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如的存储空间和计算时间有多少？空间和时间如何折衷？算法最好和最坏的情况是什么？何折衷？算法最好和最坏的情况是什么？算法的通用性如何？算法的通用性如何？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n体系结构体系结构 1)主要内容：包括数字逻辑数据的机器表示、主要内容：包括数字逻辑数据的机器表示、汇编级机器组织、存储技术、接口和通信、性汇编级机器组织、存储技术、接口和通信、性能优化网络和分布式系统的体系结构等能优化网络和分布式系统的体系结构等 2）基本问题主要包括基本问题主要包括:实现处理器内存和机内通
8、信的方法是什么？实现处理器内存和机内通信的方法是什么？如何设计和控制大型计算系统？如何设计和控制大型计算系统？哪种类型的体系结构能够有效地包含许多在一哪种类型的体系结构能够有效地包含许多在一个计算中能够并行工作的处理元素？个计算中能够并行工作的处理元素？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n操作系统操作系统 1）主要内容：包括操作系统的逻辑结构、并发处主要内容：包括操作系统的逻辑结构、并发处 理资源分配与调度、存储管理、设备管理等理资源分配与调度、存储管理、设备管理等 2）基本问题主要包括：基本问题主要包括：n 在计算机系统操作的每一个级别上，可见的对象和 允许进行的操作
9、各是什么？n 对于每一类资源能够对其进行有效利用的最小操作 集是什么？n 如何组织接口才能使得用户只需与抽象的资源而非 硬件的物理细节打交道？n 作业调度、内存管理、并发任务间的通信等。计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n网络计算网络计算 1）主要内容：包括计算机网络的体系结构、网络主要内容：包括计算机网络的体系结构、网络安安 全、网络管理、无线和移动计算，以及多媒体数全、网络管理、无线和移动计算，以及多媒体数 据技术等据技术等 2）基本问题主要包括基本问题主要包括 网络中的数据如何进行交换？网络协议如何验证？网络中的数据如何进行交换？网络协议如何验证？如何保证网络的安
10、全？如何保证网络的安全？分布式计算的性能如何分布式计算的性能如何 评价？评价？分布式计算如何组织才能够使通过通信分布式计算如何组织才能够使通过通信 网连接在一起的自主计算机参加到一项计算中？网连接在一起的自主计算机参加到一项计算中？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n程序设计语言程序设计语言 1）主要内容：包括程序设计模式、类型系统、执主要内容：包括程序设计模式、类型系统、执行控制模型、语言翻译系统、程序设计语言的语行控制模型、语言翻译系统、程序设计语言的语义学等义学等 2）基本问题主要包括基本问题主要包括 语言（数据类型、操作、控制结构、引进新类型和操作的机语言（数据
11、类型、操作、控制结构、引进新类型和操作的机制）表示的虚拟机的可能组织结构是什么？制）表示的虚拟机的可能组织结构是什么？语言如何定义机器？机器如何定义语言？语言如何定义机器？机器如何定义语言？什么样的表示法语义可以有效地用于描述计算机应该做什么？什么样的表示法语义可以有效地用于描述计算机应该做什么？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n人机交互人机交互 1）主要内容：包括以人为中心的软件开发和评价，主要内容：包括以人为中心的软件开发和评价，图形用户接口设计，多媒体系统的人机接口等图形用户接口设计，多媒体系统的人机接口等 2）基本问题主要包括基本问题主要包括 表示物体和自动产
12、生供阅览的照片的有效方法是什么？表示物体和自动产生供阅览的照片的有效方法是什么？接受输入和给出输出的有效方法是什么？接受输入和给出输出的有效方法是什么？怎样才能减小产生误解和由此产生的人为错误的风险？怎样才能减小产生误解和由此产生的人为错误的风险？图表和其他工具怎样才能通过存储在数据集中的信息去理解图表和其他工具怎样才能通过存储在数据集中的信息去理解物理现象？物理现象？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n图形学和可视化计算图形学和可视化计算 1）主要内容：包括计算机图形学、可视化、虚拟主要内容：包括计算机图形学、可视化、虚拟现实、计算机视觉等现实、计算机视觉等4个学科子
13、领域的研究内容个学科子领域的研究内容 2）基本问题主要包括基本问题主要包括 支撑图像产生以及信息浏览的更好模型？支撑图像产生以及信息浏览的更好模型？如何提取科学的计算和医学和更抽象的相关数据？如何提取科学的计算和医学和更抽象的相关数据？图像形成过程的解释和分析方法图像形成过程的解释和分析方法？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n智能系统智能系统 1）主要内容：知识表示和推理、主要内容：知识表示和推理、Agent、自然语言自然语言处理、机器学习和神经网络、人工智能和机器人处理、机器学习和神经网络、人工智能和机器人学等学等 2基本问题主要有基本问题主要有 基本的行为模型是什
14、么？如何建造模拟它们的机器？基本的行为模型是什么？如何建造模拟它们的机器？规则评估、推理、演绎在多大程度上描述了智能？规则评估、推理、演绎在多大程度上描述了智能？通过这些方法模拟行为的机器的最终性能如何？通过这些方法模拟行为的机器的最终性能如何？传感数据如何编码才使得相似的模式有相似的代码传感数据如何编码才使得相似的模式有相似的代码？学习系统的体系结构怎样学习系统的体系结构怎样？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n信息管理信息管理 1）主要内容：包括信息模型与信息系统、数据库系统、数主要内容：包括信息模型与信息系统、数据库系统、数据建模、数据库查询语言、关系数据库设计、
15、事务处理、据建模、数据库查询语言、关系数据库设计、事务处理、分布式数据库、数据挖掘、信息存储与检索、超文本和超分布式数据库、数据挖掘、信息存储与检索、超文本和超媒体、多媒体信息与多媒体系统、数字图书馆等媒体、多媒体信息与多媒体系统、数字图书馆等 2）基本问题主要包括基本问题主要包括 高级查询如何翻译成高质量的程序高级查询如何翻译成高质量的程序？怎样保护数据以避免非授权访问泄露和破坏怎样保护数据以避免非授权访问泄露和破坏？如何保护大型的数据库以避免同时更新引起的不一致性如何保护大型的数据库以避免同时更新引起的不一致性？当数据分布在许多机器上时如何保护数据保证性能当数据分布在许多机器上时如何保护数
16、据保证性能？文本如何索引和分类才能够进行有效的恢复文本如何索引和分类才能够进行有效的恢复？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n软件工程软件工程 1）主要内容：包括软件过程、软件需求与规格说主要内容：包括软件过程、软件需求与规格说明、软件设计、软件验证、软件演化、软件项目明、软件设计、软件验证、软件演化、软件项目管理、软件开发工具与环境、形式化方法、软件管理、软件开发工具与环境、形式化方法、软件可靠性等可靠性等 2）基本问题主要包括基本问题主要包括 如何证明一个程序或系统满足其规格说明如何证明一个程序或系统满足其规格说明？如何编写不忽略重要情况且能用于安全分析的规格说明？
17、如何编写不忽略重要情况且能用于安全分析的规格说明？软件系统是如何历经不同的各代进行演化的软件系统是如何历经不同的各代进行演化的？如何从可理解性和易修改性着手设计软件如何从可理解性和易修改性着手设计软件？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n社会和职业的问题社会和职业的问题 1）主要内容：包括计算的历史、计算的社会背景、主要内容：包括计算的历史、计算的社会背景、分析方法和工具、专业和道德责任、基于计算机分析方法和工具、专业和道德责任、基于计算机系统的风险与责任、知识产权、隐私与公民的自系统的风险与责任、知识产权、隐私与公民的自由、计算机犯罪与计算有关的经济问题等由、计算机犯
18、罪与计算有关的经济问题等 2）基本问题主要包括基本问题主要包括 计算机学科本身的文化社会法律和道德的问题计算机学科本身的文化社会法律和道德的问题？有关计算的社会影响问题以及如何评价可能的一些答案的问有关计算的社会影响问题以及如何评价可能的一些答案的问题题？哲学问题哲学问题？技术问题以及美学问题技术问题以及美学问题？计算机学科各主领域的基本问题计算机学科各主领域的基本问题 n科学计算科学计算 1）主要内容：包括数值分析、运筹学、模拟和仿真、主要内容：包括数值分析、运筹学、模拟和仿真、高性能计算高性能计算 2）基本问题主要包括基本问题主要包括 如何精确地以有限的离散过程近似表示连续和无限的离散过程
19、？如何精确地以有限的离散过程近似表示连续和无限的离散过程？如何处理这种近似产生的错误如何处理这种近似产生的错误？给定某一类方程在某精确度水平上能以多快的速度求解给定某一类方程在某精确度水平上能以多快的速度求解？如何实现方程的符号操作如积分微分以及到最小项的归约如何实现方程的符号操作如积分微分以及到最小项的归约？计算机科学典型问题示例计算机科学典型问题示例 n哥尼斯堡七桥问题哥尼斯堡七桥问题 寻找走遍这7座桥且只许走过每座桥一次，最后又回到原出发点的路径 计算机科学典型问题示例计算机科学典型问题示例 n梵天塔问题梵天塔问题 1）每次只能移动一个盘子；2）盘子只能在三根柱子上来回移动不能放在他处；
20、3）在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上 天神说，当这64个盘子全部移到第三根柱子上后，世界末日就要到了。计算机科学典型问题示例计算机科学典型问题示例 n证比求易算法证比求易算法 一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚，公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王能在一天之内求出答案，公主便接受他的求婚。国王回去后从早到晚共算了三万多个数最终还是没有结果，国王向公主求情，公主将答案相告223 092 827是它的一个真因子。公主说我再给你一次机会，如果还求不出将来你只好做我的证婚人了。国王立即回国并向时任宰相的大数学家
21、求教，大数学家在仔细地思考后认为这个数为17位，则最小的一个真因子不会超过9位。于是他给国王出了一个主意，按自然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后立即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即上报，赏金万两。最后国王用这个办法求婚成功。计算机科学典型问题示例计算机科学典型问题示例 n旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题 威 廉 哈 密 尔 顿 爵 士 和 英 国 数 学 家 克 克 曼T.P.Kirkman于19世纪初提出的一个数学问题。大意是有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发，必须经过每一个城市且
22、只能在每个城市逗留一次，最后回到原出发城市。问如何事先确定好一条最短的路线使其旅行的费用最少。计算机科学典型问题示例计算机科学典型问题示例 n旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题计算机科学典型问题示例计算机科学典型问题示例 n旅行商问题与组合爆炸问题旅行商问题与组合爆炸问题据文献介绍，1998年科学家们成功地解决了美国13509个城市之间的TSP问题，2001年又解决了德国15112个城市之间的TSP问题，但这一工程代价也是巨大的。据报道解决15112个城市之间的TSP问题，共使用了美国Rice大学和普林斯顿大学之间网络互连的由速度为500MHz 的Compaq EV6 Alpha 处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。计算机科学典型问题示例计算机科学典型问题示例 n哲学家共餐问题哲学家共餐问题 5个哲学家围坐在一张圆桌旁，每个人的面前摆有一碗面条，碗的两旁各摆有一只筷子。假设哲学家的生活除了吃饭就是思考问题（这是一种抽象，即对该问题而言，其他活动都无关紧要），而吃饭的时候需要左手拿一只筷子、右手拿一只筷子，然后开始进餐，吃完后又将筷子摆回原处，继续思考问题。现在的问题是，如何协调现在的问题是，如何协调5 5个哲学家的生活进程，个哲学家的生活进程，使得每一个哲学家最终都可以进餐。使得每一个哲学家最终都可以进餐。
