科学导论-分支-学科形态

计算机学科的分支及学科形态一、学科的基本问题计算学科在各个分支学科方向的发展进程中，不断地出现了一些在表现形式上虽然不同，但在科学哲学的解释下本质上是相同或相近的问题，即学科研究与发展普遍关心的基本问题。计算学科的三个基本问题：⑴计算的平台与环境问题⑵计算过程的能行操作与效率问题⑶计算的正确性问题学科的基本问题计算的平台与环境问题为了实现自动计算—计算机的发明为了解题或证明问题本身不可解—计算模型只有构造性计算模型才是能行的模型还必须是确定性的计算平台的使用还必须是方便的—计算环境从某种意义上讲,计算的平台与环境问题包括计算模型计算机体系结构操作系统高级程序设计软件开发工具与开发环境学科的基本问题计算过程的能行操作与效率问题理论上的可计算,但实际上并不一定能行例:梵天塔问题相传印度教的天神梵天在创造地球这一世界时,建了一座神庙.神庙里竖有三根宝石柱子,柱子由一个铜座支撑.梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上,形成一座金塔.即所谓的梵天塔,又称汉诺塔.例:梵天塔问题(续)天神让庙里的僧侣们将第一根柱子上的64个盘子,借助第二根柱子,全部移到第三根柱子上.同时定下3条规则每次只能移动一个盘子.盘子只能在三根柱子上来回移动,不能放在他处.在移动过程中,三根柱子上的盘子必须始终保持大盘在下小盘在上解决该问题的方法是递归解法将一个较大的问题归约为一个或多个子问题的求解方法例:梵天塔问题(续)将64个盘子的梵天塔问题转化为求解63个盘子的梵天塔问题.如果63个盘子的梵天塔问题能够解决,则可以先将63个盘子先移动到第二个柱子上再将最后一个盘子直接移动到第三个柱子上最后又一次将63个盘子从第二个柱子移动到第三个柱子上63个盘子的梵天塔求解问题可以转化为62个盘子的梵天塔求解问题62个盘子的梵天塔求解问题又可以转化为61个盘子的梵天塔求解问题…2个盘子的梵天塔求解问题又可以转化为1个盘子的梵天塔求解问题1个盘子的梵天塔求解是直接的例:梵天塔问题(续)下面用C语言对该问题的求解算法进行描述hanoi(intn,charleft,charmiddle,charright){if(n==1)move(1,one,_,three);else{hanoi(n-1,left,right,middle);move(1,left,_,right);hanoi(n-1,middle,left,right);}}n表示n个盘子的梵天塔问题left表示第一个柱子middle表示第二个柱子right表示第三个柱子例:梵天塔问题(续)问题:当n=64时,64个盘子时需要移动多少次盘子要用多少时间?设h(n)是移动n个盘子的梵天塔问题需要的移动次数n个盘子的梵天塔问题需要移动的盘子数是n-1个盘子的梵天塔问题需要移动的盘子数的2倍加1.于是

h(n)=2h(n1)+1 =2(2h(n2)+1)+1=22h(n2)+2+1 =23h(n3)+22+2+1 …… =2nh(0)+2n1+…+22+2+1 =2n1+…+22+2+1 =2n1例:梵天塔问题(续)因此要完成梵天塔的搬迁需要移动盘子的次数为

2641=18,446,744,073,709,551,615如果每秒移动一次,一年有31,536,000秒,则僧侣们一刻不停地来回搬动也需要花费大约5,849亿年的时间.假定计算机以每秒1,000万个盘子的速度进行搬迁则需要花费大约58,490年的时间.二、学科的分类与分支学科简介1.离散结构主要内容集合论,数理逻辑,近世代数,图论以及组合数学等.该领域与计算学科各主领域有着紧密的联系CC2001为了强调它的重要性,特意将它列为计算学科的第一个主领域.该主领域以抽象和理论两个学科形态出现在计算学科中,它为计算学科各分支领域解决其基本问题提供了强有力的数学工具

学科的分类与分支学科简介2.程序设计基础主要内容程序设计结构、算法、问题求解和数据结构等基本问题对给定的问题,如何进行有效的描述并给出算法？如何正确选择数据结构？如何进行设计编码测试和调试程序？学科的分类与分支学科简介3.算法与复杂性主要内容算法的复杂度分析、典型的算法策略、分布式算法、并行算法、可计算理论、P类和NP类问题、自动机理论、密码算法以及几何算法等基本问题主要包括

对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折衷？访问数据的最好方法是什么？算法最好和最坏的情况是什么？算法的平均性能如何？算法的通用性如何？学科的分类与分支学科简介4.体系结构主要内容数字逻辑、数据的机器表示、汇编级机器组织、存储技术、接口和通信、多道处理和预备体系结构、性能优化、网络和分布式系统的体系结构等。基本问题主要包括实现处理器内存和机内通信的方法是什么？如何设计和控制大型计算系统，而且使其令人相信，尽管存在错误和失败，但它仍然是按照我们的意图工作的。哪种类型的体系结构能够有效地包含许多在一个计算中能够并行工作的处理元素？如何度量性能？学科的分类与分支学科简介5.操作系统主要内容操作系统的逻辑结构、并发处理、资源分配与调度、存储管理、设备管理、文件系统等基本问题在计算机系统操作的每一个级别上，可见的对象和允许进行的操作各是什么？对于每一类资源,能够对其进行有效利用的最小操作集是什么？如何组织接口才能使得用户只需与抽象的资源,而非硬件的物理细节打交道?作业调度,内存管理,通信软件,资源访问,并发任务间的通信以及可靠性与安全的控制策略是什么?通过少数构造规则的重复使用,进行系统功能扩展的原则是什么?学科的分类与分支学科简介6.网络计算主要内容计算机网络的体系结构,网络安全,网络管理,无线和移动计算,以及多媒体数据技术等基本问题网络中的数据如何进行交换?网络协议如何验证?如何保证网络的安全?分布式计算的性能如何评价?分布式计算如何组织才能够使通过通信网连接在一起的自主计算机参加到一项计算中,而网络协议,主机地址,带宽和资源则具有透明性?学科的分类与分支学科简介7.程序设计语言主要内容程序设计模式,虚拟机,类型系统,执行控制模型,语言翻译系统,程序设计语言的语义学,基于语言的并行构件等基本问题语言(数据类型,操作控制结构,引进新类型和操作的机制)表示的虚拟机的可能组织结构是什么?语言如何定义机器?如何定义语言?什么样的表示法(语义)可以有效地用于描述计算机应该做什么?学科的分类与分支学科简介8.人机交互主要内容以人为中心的软件开发和评价,图形用户接口设计,多媒体系统的人机接口等基本问题表示物体和自动产生供阅览的照片的有效方法是什么?接受输入和给出输出的有效方法是什么?怎样才能减小产生误解和由此产生的人为错误的风险?图表和其他工具怎样才能通过存储在数据集中的信息去理解物理现象?学科的分类与分支学科简介9.图形学和可视化计算主要内容计算机图形学,可视化,虚拟现实,计算机视觉等4个学科子领域的研究内容基本问题支撑图像产生以及信息浏览的更好模型如何提取科学的计算、医学和更抽象的相关数据图像形成过程的解释和分析方法学科的分类与分支学科简介10.智能系统主要内容约束可满足性问题,知识表示和推理,Agent,自然语言处理,机器学习和神经网络,人工智能规划系统和机器人学等基本问题基本的行为模型是什么？如何建造模拟它们的机器？规则评估、推理、演绎和模式计算在多大程度上描述了智能？通过这些方法模拟行为的机器的最终性能如何？传感数据如何编码才使得相似的模式有相似的代码。电机编码如何与传感编码相关联？学习系统的体系结构怎样？这些系统是如何表示它们对这个世界的理解的？学科的分类与分支学科简介11.信息管理主要内容信息模型与信息系统,数据库系统,数据建模,关系数据库,数据库查询语言,关系数据库设计,事务处理,分布式数据库,数据挖掘,信息存储与检索,超文本和超媒体,多媒体信息与多媒体系统,数字图书馆等基本问题使用什么样的建模概念来表示数据元素及其相互关系?怎样把基本操作,如存储定位,匹配和恢复组合成有效的事务?这些事务怎样才能与用户有效地进行交互?高级查询如何翻译成高质量的程序?哪种机器体系结构能够进行有效的恢复和更新?怎样保护数据以避免非授权访问泄露和破坏?如何保护大型的数据库以避免由于同时更新引起的不一致性?当数据分布在许多机器上时，如何保护数据保证性能?文本如何索引和分类才能够进行有效的恢复?

学科的分类与分支学科简介12.软件工程主要内容软件过程，软件需求与规格说明，软件设计，软件验证，软件演化，软件项目管理，软件开发工具与环境，基于构件的计算，形式化方法，软件可靠性，专用系统开发等基本问题程序和程序设计系统发展背后的原理是什么?如何证明一个程序或系统满足其规格说明?如何编写不忽略重要情况且能用于安全分析的规格说明?软件系统是如何历经不同的各代进行演化的?如何从可理解性和易修改性着手设计软件?学科的分类与分支学科简介13.社会和职业的问题主要内容计算的历史，计算的社会背景，分析方法和工具，专业和道德责任，基于计算机系统的风险与责任，知识产权隐私与公民的自由，计算机犯罪与计算有关的经济问题、哲学框架等基本问题计算学科本身的文化、社会、法律和道德的问题有关计算的社会影响问题以及如何评价可能的一些答案的问题哲学问题技术问题以及美学问题学科的分类与分支学科简介14.科学计算主要内容数值分析,运筹学,模拟和仿真,高性能计算基本问题如何精确地以有限的离散过程近似表示连续和无限的离散过程?如何处理这种近似产生的错误?给定某一类方程在某精确度水平上能以多快的速度求解?如何实现方程的符号操作如积分微分以及到最小项的归约?如何把这些问题的答案包含到一个有效的、可靠的、高质量的数学软件包中?例:哥尼斯堡七桥问题

17世纪的东普鲁士有一座哥尼斯堡(Konigsberg)城(现为俄国的加里宁格勒),哥尼斯堡城城中有一座奈佛夫(Kneiphof)岛,普雷格尔(Pregol)河的两条支流环绕其旁,并将整个城市分成北区,东区,南区和岛区4个区域.全城共有7座桥将4个城区相连起来.人们常通过这7座桥到各城区游玩.北区岛区南区东区例:哥尼斯堡七桥问题(续)问题能否从某区出发,走遍这7座桥,且每座桥只走一次,最后又回到原出发点?许多人尝试都未成功,也没人能够证明不行1736年,大数学家欧拉(L.Euler)发表了关于哥尼斯堡七桥问题的论文—《与位置几何有关的一个问题的解》.他在文中指出:从一点出发,不重复地走遍七桥,最后又回到原出发点是不可能的.欧拉开创了图论例:哥尼斯堡七桥问题(续)抽象从问题本质考虑,抽象出问题最本质的东西,忽视问题非本质的东西,如桥的长度等.欧拉用A表示岛区,用B,C,D分别表示其他3个区,将哥尼斯堡七桥问题转换为从下图A,B,C或D出发,经过每条边一次,最后回到出发点例:哥尼斯堡七桥问题(续)一般化一旦我们学会了一种技巧,仔细查看它是否是有启发的,并看和它一起我们能走多远----Knuth从一个具体问题推广到一般问题哥尼斯堡七桥问题的一般化对给定的任意一个河道图与任意多座桥,判定可能不可能每座桥恰好走过一次回到出发点不回到出发点哥尼斯堡七桥问题的进一步一般化图的边遍历问题:从图的任意顶点出发,不重复地经过图中每一条边(回到出发点/不回到出发点)例:哥尼斯堡七桥问题(续)图的边遍历问题从图的某顶点出发,不重复地经过图中每一条边,回到出发点当且仅当图的每个顶点都有偶数条边.(任意点为出发点)从图的某顶点出发,不重复地经过图中每一条边不回到出发点当且仅当图中恰有两个顶点有奇数条边(分别为出发点和终点)

三、计算机学科形态每一个学科都有其自身的知识组织结构、学科形态、核心概念和基本工作流程方式。所谓学科形态，是指从事该领域工作的文化方式。对计算科学的深入研究使我们已知该学科存在三种主要的学科形态抽象理论设计学科形态第一种形态:抽象科学抽象是指在思维中对同类事物去除其现象的次要的方面,抽取其共同的主要的方面,从而做到从个别中把握一般,从现象中把握本质的认知过程和思维方法抽象源于现实世界,源于经验,是对现实原形的理想化理想化后的现实原形与现实事物有了质的区别.但它们总是现实事物的概念化,有现实背景抽象是科学认识的基础和决定性环节学科中的抽象形态包含着具体的内容,它们是学科中所具有的科学概念,科学符号和思想模型学科形态计算学科的抽象,或称模型化基于计算科学的实验科学方法,广泛采用实验物理学的研究方法.按照对客观现象和规律的实验研究过程,包含以下四个步骤：⑴确定可能世界（环境）并形成假设⑵构造模型并做出预测；⑶设计实验并收集数据；⑷分析结果。这个学科形态主要出现在计算科学中与硬件设计和实验有关的研究之中。当计算科学理论比较深奥，理解较为困难时，不少科研人员在大致了解理论、方法和技术的情况下，基于经验和技能常以这种学科形态方式开展工作例:四色问题例:四色问题(续)任何规范的地图都可以至多用四种颜色着色,使得任何两个相邻的区域都具有不同的颜色两个区域相邻是指它们有一条公共边下面两个图都形状不完全相同,从着色角度是相同例:四色问题(续)抽象:将地图按如下方式转换顶点:地图上每个区域边:如果地图上的两个区域相邻,则对应的两个顶点之间有一条边前面的例子转换成湖北省河南省河北省山东省安徽省陕西省山西省例:四色问题(续)可以证明:转换后的图没有交叉边----平面图可以证明:任何平面图都可以至多用五种颜色着色,使得任意两个相邻的顶点都具有不同的颜色可以用如下定理归纳地证明:任何平面图都有小于5度的顶点地图的四着色问题转换成任何平面图都可以至多用四种颜色着色,使得任意两个相邻的顶点都具有不同的颜色转换后的平面图与原地图很不相同,但是从着色角度,两个问题是否有解是等价的抽象去除了问题的次要方面,如每个区域的形状,大小抽象保留了问题的本质方面----区域的相邻性被顶点的相邻性捕获抽象得到的平面图概念不仅可以解决地图着色问题,而且还有其他应用,如电路板布线问题学科形态计算学科的理论计算科学的数学基础和计算科学理论,广泛采用数学的研究方法.按统一的合理的理论发展过程，包含以下四个步骤：⑴对研究对象的概念抽象（定义和公理）⑵假设对象的基本性质和对象之间可能存在的关系（定理）⑶确定这些性质和关系是否正确（证明）⑷解释结果（与计算机系统或研究对象形成对应）这个学科形态的基本特征是其