计算机科学与技术方法论.ppt

第3章 计算学科中的三个学科形态,凌贺飞 博士 副教授 智能与分布计算实验室 () 华中科技大学计算机学院,三个学科形态,抽象理论设计（三种形态）：计算学科中的基本内容，基本概念；同时反映了人们的认识是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）中来的一般科学思维方法,一般科学技术方法论中有关抽象形态的论述,科学抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。 是科学认识由感性认识到理性认识飞跃的决定性环节,计算学科中抽象形态,计算作为一门学科报告认为：抽象源于实验科学、源于现实世界（建立对客观事物进行抽象描述的方法，建立概念模型）。 包括以下4个步骤： （1）形成假设； （2）建造模型并作出预测； （3）设计实验并收集数据； （4）对结果进行分析。,抽象过程的目的-建立概念模型 例：封建社会形成框架-天地君亲师。 资本主义社会阶级斗争(资产阶级、无产阶级)。 大学层次模型 （ 学校 院 系 组）,一般科学技术方法论中有关理论形态的论述,科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。 理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事物，不受现实事物的限制，具有精确的、优美的特征，因而更能把握事物的本质。,计算学科中理论形态,在计算学科中，源于数学（建立理论体系，建立数学模型）。 包括以下4个步骤： （1）表述研究对象的特征（定义和公理）； （2）假设对象之间的基本性质和对象之间可能存在的关系（定理）； （3）确定这些关系是否为真（证明）； （4）结论。,例：封建社会形成框架-天地君亲师，上升到理论-法则（约束）-天人合一，男女收授不亲等 资本主义社会以私营经济为主，资产阶级政党掌权，或实行资本主义的民主政治制度。 一、生产力高度发展，社会富裕，鼓励自由的市场经济，政府对经济的干预尽量少。二，商品生产发展到很高的阶段，成为社会生产普遍的和统治的形式，劳动力变成了商品。 三，资本家占有生产资料，用雇佣劳动的方式剥削工人阶级，生产的目的是创造利润。四，以使用机器的大生产为特征，生产社会化同资本主义的私人占有之间的矛盾构成资本主义社会的基本矛盾。 大学培养学生， 上下级管理。,一般科学技术方法论中有关设计形态的论述,设计源于工程，并用于系统或设备的开发，以实现给定的任务。 设计必须以对自然规律的认识为前提。设计必须创造出相应的人工系统和人工条件，还必须认识自然规律在这些人工系统中和人工条件下的具体表现形式. 设计形态的主要特征与抽象、理论两个形态的主要区别： 设计形态具有较强的实践性、社会性、综合性。,计算学科中的设计形态,源于工程（完成一个具体任务，总结与升华） 包括以下4个步骤： （1）需求分析； （2）建立规格说明； （3）设计并实现该系统； （4）对系统进行测试与分析。,例：学校 各种规章制度； 信息公开； 教师聘任制； 考核制度。,一般科学技术方法论中有关3个学科形态内在联系的简要论述,在计算机科学与技术方法论的原始命题中，蕴含着人类认识过程的两次飞跃，第一次飞跃是从物质到精神，从实践到认识的飞跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。 第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。,计算学科中有关3个学科形态内在联系 的论述,3个学科形态的内在联系 抽象源于现实世界。建立对客观事物进行抽象描述的方法，建立具体问题的概念模型，实现对客观世界的感性认识。 理论源于数学。建立完整的理论体系，建立具体问题的数学模型，从而实现对客观世界的理性认识。 设计源于工程 。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。,4、各领域中三个形态的主要内容 （P54-P59）,二、例子1 信息系统（数据库）三种形 态实例 （P44-P48）,1、问题：实体：学生与课程，联系：多对多，要 建立一个信息管理系统。,信息管理系统涉及的软件： 应用软件 中间件及工具软件 数据库管理系统 DBMS (Database management system) 操作系统（operating system，OS）,高,低,语言,实体：客观存在并可相互区别的事物 实体集 属性：实体所具有的某一方面的特性 关键字（码）：能唯一标识实体的属性集 联系：不同实体集之间的联系 1:1， 1:N， N:M,2、抽象形态建模,（1）实体（Entity）、属性（Atribute）、关键字（Key） 与联系（Relationship）,联系,联系：不同实体集之间的联系 1:1（一对一）对于实体集E1 和E2，如果E1 和E2中每一个实体至多与另一个实体集中的一个实体有联系。 例： 省省长，国家国旗，学生学号身份证（约束条件）。 1:N （一对多）对于实体集E1 和E2，如果E1 中至少有一个实体与E2中的多个实体有联系，且E2 中每一个实体至多与与E1中的一个实体有联系。 例： 班主任学生，经理员工（约束条件）。 N:M （多对多）对于实体集E1 和E2，如果E1 中至少有一个实体与E2中的多个实体有联系，且E2 中至少有一个实体与E1中的多个实体有联系。 例： 老师学生，学生社团，学生课程。,三种图元素：实体(矩形)、属性(椭圆)、联系(菱形) P45 图3.1 学生选课E-R图,（2）E-R模型,E-R模型（Entity-Relationship）,1976年，美籍华人陈品山（Peter Pingshan Chen）提出的。 用E-R模型来描述客观世界并建立概念模型的抽象方法。 实体用矩形表示，属性用椭圆形表示，联系用菱形表示，实体间的联系有一对一（1:1）、一对多（1:N）和多对多（N:M）3种情况。 要实现对客观事物的感性认识，必须将客观世界（在例中客观世界就是“学生选课”）抽象为信息世界。,E-R模型（Entity-Relationship）,型与值的区别 实体与实体集的区别 例子：作者写书、储户在储蓄所存钱，劫匪抢劫银行等。,E-R图示例1,E-R图示例2,图3.1 学生选课E-R图,学生选课E-R图扩展,概念模型,概念模型：用于信息世界的建模，是客观世界到信息世界的抽象。描述系统中实体集与实体集之间的联系，同时要便于计算机实现。 概念模型不是机器世界所支持的数据模型，而是客观世界到机器世界的一个中间层次。 概念模型还需要转换成机器世界能支持的数据模型。 随描述方法不同会产生不同的概念模型 在数据库领域中，数据库管理系统（DBMS）能支持的数据模型有：层次、网状、关系以及面向对象等数据模型。,实体及实体之间的联系均用关系（二维表）表示 笛卡尔积：设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）关系模型,准备知识-笛卡尔积,给定一组域D1，D2，Dn，这些域中可以有相同的。D1，D2，Dn的笛卡尔积为： D1D2Dn（d1，d2，dn）diDi，i1，2，n 所有域的所有取值的一个组合不能重复。 案例 给出三个域： D1=SUPERVISOR = 张清玫，刘逸 D2=SPECIALITY=计算机专业，信息专业 D3=POSTGRADUATE=李勇，刘晨，王敏 则D1，D2，D3的笛卡尔积为D：,案例 给出三个域： D1=SUPERVISOR = 张清玫，刘逸 D2=SPECIALITY=计算机专业，信息专业 D3=POSTGRADUATE=李勇，刘晨，王敏 则D1，D2，D3的笛卡尔积为D： D=D1D2D3 (张清玫，计算机专业，李勇)，(张清玫，计算机专业，刘晨)， (张清玫，计算机专业，王敏)，(张清玫，信息专业，李勇)， (张清玫，信息专业，刘晨)，(张清玫，信息专业，王敏)， (刘逸，计算机专业，李勇)，(刘逸，计算机专业，刘晨)， (刘逸，计算机专业，王敏)，(刘逸，信息专业，李勇)， (刘逸，信息专业，刘晨)，(刘逸，信息专业，王敏) 这样就把D1,D2,D3这三个集合中的每个元素加以对应组合，形成庞大的集合群。 本个例子中的D中就会有2X2X3个元素，,二维表例,关系模式设计的问题,例：描述学校的数据库： 教务管理系统，需要存储下列信息 学号，姓名， 系名，系主任名，课名， 成绩 SNO, SNAME, SDEPT, MNAME, CNAME, GRADE 设计一个关系模式： S=SNO, SNAME, SDEPT, MNAME, CNAME, GRADE,关系模式设计的问题,学校数据库的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名主任； 一个学生可以选修多门课程， 每门课程有若干学生选修； 每个学生所学的每门课程都有一个成绩。,S=SNO, SNAME, SDEPT, MNAME, CNAME, GRADE,Student中的样本数据,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之间不存在函数依赖,属性组S上的一组函数依赖F： F Sno Sdept, Sdept Mname, (Sno, Cname) Grade ,Student中存在的问题,S=SNO, SNAME, SDEPT, MNAME, CNAME, GRADE,关系模式设计的问题, 数据冗余太大 浪费大量的存储空间 例：每一个系主任的姓名重复出现 更新异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组 3.插入异常（Insertion Anomalies） 该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。 删除异常（Deletion Anomalies） 不该删除的数据不得不删 例，如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,S=SNO, SNAME, SDEPT, MNAME, CNAME, GRADE,插入异常 删除异常 冗余太大,（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。,规范化理论,范式定义 范式（NF）是符合某一种级别的关系模式的集合。 3NF2NF1NF 若R(U，F)符合x范式的要求，则称R为x范式，记作：RxNF,第一范式(1NF) (1 of 2),第一范式（1NF） 如果一个关系模式R的所有属性都是不可分的基本数据项,则 R 1NF 不满足1NF的数据库模式不能称为关系数据库 满足1NF的数据库并一定是一个好的关系模式,第一范式(1NF) 例,SLC (Sno，Sdept，Mname，Cno，Grade) 1NF，但存在下列问题： 插入异常：若学生没有选课，则他的个人信息及所在系的信息就无法插入 删除异常：若删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了 更新异常：如果学生转系，若他选修了k门课，则需要修改k条记录 数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复。,出现这些问题的原因是Sdept， Mname对键(Sno，Cno)的部分函数依赖。,三、第二范式(2NF) (1 of 2),第二范式(2NF) 满足第一范式的关系模式R, 如果所有非主属性都完全依赖于键, 则称R属于第二范式。 记为R2NF。 例：将属于第一范式的SLC进行投影分解，消除其中的部分函数依赖，就可达到第二范式。 SC(Sno, Cno, Grade) 2NF SL(Sno, Sdept, Mname) 2NF,第二范式(2NF) (2 of 2),SL(Sno，Sdept， Mname) 2NF 但存在下列问题： 插入异常 删除异常 修改复杂 数据冗余度大,在SL(Sno, Sdept, Mname) 中有下列函数依赖： SnoSdept, Sdept Mname Sno 传递 Mname 我们看到， Mname 传递函数依赖于 Sno ，即存在非主属性对键Sno传递依赖存在。,第三范式(3NF),第三范式（3NF） 若R2NF, 且它的任何一个非主属性都不传递依赖于键, 则称关系R满足第三范式。 记为R3NF 将属于第二范式的SL进行投影分解，消除其中的传递函数依赖, 就可达到第三范式。 SD(Sno, Sdept) 3NF DL(Sdept, Mname) 3NF,在数据库的模型设计中目前一般采用第三范式，它有非常严格的数学定义。如果从其表达的含义来看，一个符合第三范式的关系必须具有以下三个条件： 每个属性的值唯一，不具有多义性； 每个非主属性必须完全依赖于整个主键，而非主键的一部分； 每个非主属性不能依赖于其他关系中的属性，因为这样的话，这种属性应该归到其他关系中去。 我们可以看到，第三范式的定义基本上是围绕主键与非主属性之间的关系而作出的。 结论：从感性认识（抽象）而来的关系模式，必须 用规范化（理论）方法，使之在3NF以上。 还有改进的3NF -BCNF(BoyeeCodd Normal Form）、第四范式(4NF) 、第五范式(5NF) ，以后课程学习。,结论：从感性认识（抽象）而来的关系模式，必须 用规范化（理论）方法，使之在3NF以上。,4、设计形态依赖具体的DBMS进行定义与应用 （SQL语句）,依赖具体的DBMS进行定义与应用 （SQL语句）47页。 SQL: Struceured Query Languange ISO(International Organization for Standardization)1998 国际标准 广泛应用于各种大型数据库，如SYBASE、INFORMIX、 ORACLE、DB2、INGRES等，也用于各种小型数据库，如FOXPRO、ACCESS。,SQL功能,典型语句：,1. 基本表定义格式（SQL 92） create table 表名（ 列名 数据类型 default 缺省值 not null ，列名 数据类型 default 缺省值 not null ，primary key（列名 ，列名 ） ，foreign key （列名 ，列名 ） references 表名 （列名 ，列名 ） ，check（条件）,基本表的定义示例 I,S: 学号: char 4; 姓名: char 8 非空; 年龄: int 3; 性别: char 1; 主关键字: 学号；性别: 只能取 0 或者 1 学生基本表：CREATE TABLE S ( S# CHAR（4）, SNAME CHAR（8） NOT NULL, AGE INT (3), SEX CHAR（1）, PRIMARY KEY (S#), CHECK (SEX=0 OR SEX=1) ),基本表的定义示例 II,课程基本表：CREATE TABLE C ( C# CHAR（4）, CNAME CHAR（10） NOT NULL, TEACHER CHAR（8）, PRIMARY KEY (C#), ),关系课程C： 课程号: char 4; 课程名称: char 10 非空； 任课教师姓名: char 8; 主关键字: 课程号,SELECT 从数据库中检索行，并允许从一个或多个表中选择一个或多 个行或列。虽然 SELECT 语句的完整语法较复杂，但是其主 要的子句可归纳如下： SELECT select_list INTO new_table FROM table_source WHERE search_condition GROUP BY group_by_expression HAVING search_condition ORDER BY order_expression ASC | DESC ,行条件子句,分组子句,组条件子句,排序子句,查询语句,查询的结果是仍是一个表。 SELECT语句的执行过程是: 根据WHERE子句的检索条件，从FROM子句指定的基本表或视图中选取满足条件的元组，再按照SELECT子句中指定的列，投影得到结果表。 如果有GROUP子句，则将查询结果按照相同的值进行分组。 如果GROUP子句后有HAVING短语，则只输出满足HAVING条件的元组。 如果有ORDER子句，查询结果还要按照的值进行排序。,简单查询,SQL数据查询基本结构 SELECT A1 , A2 , , An FROM R1 , R2 , , Rm WHERE P,示例,给出所有学生的姓名，性别和所在系 SELECT sname, ssex, depart FROM student 查询结果是对student表作投影运算，得到name, ssex, depart对应的三列,说明 from子句列出查询的对象表 当目标列取自多个表时，在不混淆的情况下可以不用显式指明来自哪个关系 示例 例：查询成绩低于75的学生的姓名、系别、成绩 SELECT sname, depart, grade FROM student , sc WHERE grade 75 AND student.sno=sc.sno,4 from子句,示例,例：查询选修了“数据库”课程的学生学号、姓名和成绩 SELECT student.sno,sname, grade FROM student, course, SC WHERE student.sno=sc.sno AND o=o AND ame=数据库,5. WHERE 子句,语法成分 比较运算符 、 、=、 逻辑运算符 AND，OR，NOT BETWEEN 条件 判断表达式的值是否在某范围内,5. WHERE 子句示例,PROF(P# , PNAME, AGE, D# , SAL) DEPT(D# , DNAME , DEAN) Ex 1: 查询工资低于2000的老师的姓名、工资、系别 SELECT pname , sal , dname FROM Prof , Dept WHERE sal 2000 AND Prof.d# = Dept.d#,Ex 2: 查询工资在1000-2000之间的老师姓名 SELECT pname FROM Prof WHERE sal BETWEEN 1000 AND 2000,数据库设计流程,客观世界 抽象 关系模型 规范化 设计（SQL）,三、例子2 程序设计语言三种形态实例,1、自然语言与形式语言,图3.2 P62 状态 规则：五元组（Qi Sj Sk R（或L或N）Ql） Qi：当前状态 Sj：从方格中读入符号 Sk：写入方格中的符号 R、L、N：右移、左移（一格），不移动 Ql：下一状态 实例（P63-P64）,2、预备知识图灵机,（1）什么是图灵机,图灵机及其他计算模型,图灵的观点及结论： 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 与图灵机等价的计算模型： 递归函数 -演算 POST规范系统 图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。,图灵机,图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，,图灵机,写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。 可以认为这个有穷字母表仅有S0、S1两个字符， 其中S0可以看作是“0”，S1可以看作是“1”， 由 “0”和“1”组成的字母表可以表示任何一个数。,由于“0”和“1”只有形式的意义，因此，也可以将S0改称为“白”，S1改称为“黑”，这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值真，假，以及二进制机器本质的理解。机器的控制状态表为：q1，q2，qm。 将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。,一个给定机器的“程序”,机器内的五元组（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。当没有输入时，即初始状态所