计算学科中的三个学科形态.ppt

第3章 计算学科中的三个学科形态,文坤梅 E-Mail: 智能与分布计算实验室 Intelligence and Distributed Computing Lab,第3章 计算学科中的三个学科形态,抽象理论设计（三种形态）：计算学科中的基本内容，基本概念；同时反映了人们的认识是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）中来的一般科学思维方法,1、抽象形态,科学抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。 学科中的抽象形态包含着具体的内容，它们是学科中所具有的科学概念、科学符号和思想模型。,一、三种形态与各领域中三个形态的 主要内容 （P49-P59）,1、抽象形态源于现实世界（建立对客观事物 进行抽象描述的方法，建立概念模型）,形成假设 建造模型并作出预测 设计实验并收集数据 对结果进行分析,科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。 理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事物，不受现实事物的限制，具有精确的、优美的特征，因而更能把握事物的本质。,2、理论形态,表述研究对象的特征（定义和公理） 假设对象之间的基本性质和对象之间可能存在的 关系（定理） 确定这些关系是否为真（证明） 结论,2、理论形态源于数学（建立理论体系，建立 数学模型）,3、设计形态,设计形态与抽象、理论两个形态存在的联系 设计源于工程，用于系统或设备的开发，实现给定的任务 设计形态和抽象、理论两个形态都须以对自然规律的认识为前提 设计必须创造出相应的人工系统和人工条件，还必须认识自然规律的具体表现形式 设计形态的主要特征与抽象、理论两个形态的主要区别： 设计形态具有较强的实践性、社会性、综合性,需求分析 建立规格说明 设计并实现该系统 对系统进行测试与分析,3、设计形态源于工程（完成一个具体任务， 总结与升华）,三个学科形态的内在联系,在计算机科学与技术方法论的原始命题中，蕴含着人类认识过程的两次飞跃，第一次飞跃是从物质到精神，从实践到认识的飞跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。 第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。,抽象源于现实世界。建立对客观事物进行抽象描述的方法，建立具体问题的概念模型，实现对客观世界的感性认识。 理论源于数学。建立完整的理论体系，建立具体问题的数学模型，从而实现对客观世界的理性认识。 设计源于工程。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。,三个学科形态的内在联系,4、各领域中三个形态的主要内容 （P54-P59）,二、例子1 信息系统（数据库）三种形 态实例 （P44-P48）,1、问题：实体：学生与课程，联系：多对多，要 建立一个信息管理系统。,实体：客观存在并可相互区别的事物 实体集 属性：实体所具有的某一方面的特性 关键字（码）：能唯一标识实体的属性集 联系：不同实体集之间的联系 1:1， 1:N， N:M,2、抽象形态建模,（1）实体（Entity）、属性（Attribute）、关键字（Key） 与联系（Relationship）,三种图元素：实体(矩形)、属性(椭圆)、联系(菱形) P45 图3.1 学生选课E-R图,（2）E-R模型,实体及实体之间的联系均用关系（二维表）表示 笛卡尔积：设D1，D2，Dn为任意集合，定义 D1，D2，Dn笛卡尔积为： D1 D2 Dn = (d1, d2, , dn)|diDi, i=1, , n 关系：笛卡尔积D1 D2 Dn的任意一个子集，称为 D1，D2，Dn上的一个n元关系 关系模式：二维表的表框架，R = U：关系中所有属性的集合 F：属性集合U上的一组函数依赖,（3）关系模型,3、理论形态规范化理论,定义：设有关系模式R（A1, A2, , An），X和Y均为 A1, A2, , An的子集，r是R的任一具体关系（R-型， r-值）。如果R的所有关系r都存在着：对于X的每一 个具体值，都有Y唯一的具体值与之对应，则称X函数 决定Y，或Y函数依赖于X。记为X Y,（1）函数依赖：属性间的关系,函数依赖判别简法：设有属性集X、Y及关系模式R 如果X、Y之间是“1:1”关系，则 XY YX 如果X、Y之间是“N:1”关系，则 XY 如果X、Y之间是“N:M”关系，则 X、Y之间不存在函数依赖,插入异常 删除异常 冗余太大,（2）感性认识中存在的问题,1NF（1 Normal Form）:每个属性值都是不可再分的 最小单元 2NF：若R1NF，且每一非主属性不存在对关键字的 部分依赖，则R2NF。 部分依赖：设R中XY，YX，如果存在X的真 子集X1Y成立，则称Y部分依赖于X，否则称Y完 全函数依赖于X。,（3）规范化理论,3NF：若R2NF，且每一非主属性不存在对关键字 的传递依赖，则R3NF。 传递依赖：对R，X、Y、Z均为R的属性子集，如果 XY，YZ，则称Z传递依赖于X。,结论：从感性认识（抽象）而来的关系模式，必须 用规范化（理论）方法，使之在3NF以上。,4、设计形态依赖具体的DBMS进行定义与应用 （SQL语句）,三、例子2 程序设计语言三种形态实例,计算机语言在裸机级所取得的主要成果,BACK,1、自然语言与形式语言,歧义性； 不够严格和不够统一的语法结构。 他的发理得好。 他的理发水平高； 理发师理他的发理得好。 他的小说看不完。 他写的小说看不完； 他收藏的小说看不完； 他是个小说迷。,人类的语言（文字）是人类最普遍使用的符号系统。其最基本、最普遍的形式是自然语言符号系统,高级语言的歧义性问题,高级程序设计语言其实也有语义的歧义性问题,高级程序设计语言存在较少的歧义性而已 例3.4 IF (表达式1) THEN IF (表达式2) THEN 语句1 ELSE 语句2。 IF (表达式1) THEN (IF (表达式2) THEN 语句1 ELSE 语句2)； IF (表达式1) THEN (IF (表达式2) THEN 语句1) ELSE 语句2。,形式语言,有一组初始的、专门的符号集； 有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。 在形式语言中，不允许出现根据形成规则无法确定的符号串。,人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。,2. 图灵机,图灵的观点及结论： 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 与图灵机等价的计算模型： 递归函数 -演算 POST规范系统 图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。,图灵机,图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，,图灵机,写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。 可以认为这个有穷字母表仅有S0、S1两个字符， 其中S0可以看作是“0”，S1可以看作是“1”， 由 “0”和“1”组成的字母表可以表示任何一个数。,一个给定机器的“程序”,机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下： qi表示机器目前所处的状态； Sj表示机器从方格中读入的符号； Sk表示机器用来代替Sj写入方格中的符号； R、L、N分别表示向右移一格、向左移一格、不移动； ql表示下一步机器的状态。,一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同时出现在机器中，当机器处于状态q1，第一条指令读入的是S2，第二条指令读入的是S3，那么机器会在两个方块之间无休止地工作。 另外，如果q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中，当机器处于状态q3并在带子上扫描到符号S2时，就产生了二义性的问题，机器就无法判定。,例3.9,b表示空格，q1表示机器的初始状态， q4表示机器的结束状态，设带子上的输入信息是10100010，读入头位对准最右边第一个为0的方格，状态为初始状态q1。规则如下。 q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4 q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4,计算过程如下：,计算结果是10100011，即对给定的数加1。,以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。,图灵机的计算能力,图灵机可以计算 S(x)x1（后继函数）， N(x)0（零函数）， Ui(n)(x1，x2，xn)xi，1in（投影函数） 上述3个函数的任意组合。 从递归论中，我们知道这3个函数属于初始递归函数， 任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。 从可计算理论可知每一个原始递归函数都是图灵机可计算的。,3、预备知识冯诺依曼计算机,ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。 在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼（Von Neumann）及其同事完成了关于“电子计算装置逻辑结构设计”的研究报告， 具体介绍了制造电子计算机和程序设计的新思想 至今为止，大