当前位置:首页 >> 理学 >>

13-14第1学期 第3章(1)[2013


计算机科学导论
主讲教师:王慧娇 E-mail: whj@guet.edu.cn 手机: 13978321977 QQ: 248886622 答疑时间:周二14:00-15:30

内容回顾
? 计算学科二维定义矩阵:
? 从感性认识(抽象)到理性认识(理论) ? 再由理性认识(理论)回到实践(设计)

? 典型实例:
? 哥尼斯堡七桥问题 ? 抽象:图;欧拉回路问题 ? 三条判定规则;判断是否存在欧拉回路的充分必要条件

第3章 3个学科形态
? 本章主要内容:
? “学生选课”例子 ? 计算学科中的3个学科形态 ? 从一般科学技术方法论的角度考察3个形态 ? 从计算学科的角度考察3个学科形态 ? 计算机语言的发展以及其中3个学科形态的内在联系 ? 自然语言与形式化语言 ? 图灵机 ? 冯· 诺依曼计算机 ? 机器指令与汇编语言 ? 以虚拟机的观点划分计算机的层次结构 ? 高级语言 ? 应用语言 ? 自然语言及其形式化

“学生选课”例子
? 问题描述: ? 现给出“学生”和“课程”两个实体,它们的联系为:
? 一个学生可以选修若干门课程 ? 每门课程可以被任一学生所选修。

? 请建立一个信息管理系统,实现对“学生选课”这一 信息的管理。 ? 感性认识 -> 理性认识 -> 实践 ? 抽象 -> 理论 -> 设计

感性认识与概念模型
? 要实现对客观事物的感性认识,必须将客观世界(即“ 学生选课”)抽象为信息世界。

? 概念模型:
? 用于信息世界的建模,是客观世界到信息世界的抽象。

? 概念模型中的主要概念有:
? ? ? ? ? 实体:客观存在并可相互区别的事物。 属性:实体所具有的某一种特性。 码:能惟一标识实体的属性集。 域:属性的取值范围。 联系:不同实体集之间存在的联系。分为:
? 一对一 ? 一对多 ? 多对多

? 数据库领域:E-R方法(Entity-Relationship Approach)

E-R模型
? 是一种用实体和实体之间的联系来描述客观世界并建立 概念模型的抽象方法。 ? E-R图:
? ? ? ? 实体:用矩形表示, 属性:用椭圆形表示, 联系:用菱形表示, 实体之间的联系:用数字标注在图上;
? 一对一(1:1) ? 一对多(1:N) ? 多对多(N:M)。

学生选课E-R图
学 号 姓 名 年 龄 性 别

学 n 选 m 课





成 绩



课程号

课程名

关系模型
? 概念模型(E-R图)不是机器世界所支持的数据模型,仅 仅是客观世界到机器世界的一个中间层次。 ? 概念模型还需要转换成机器世界能支持的数据模型。 ? 在数据库领域中,数据库管理系统(DBMS)支持的数 据模型主要有:
? ? ? ? 层次模型 网状模型 关系模型 面向对象模型等。

? 关系模型:基于关系理论的,体现为二维表结构的数据 模型。 ? 每个关系对应于一张二维表。

“学生选课”例子的关系模型
? 从E-R图转换得到: ? 学生(学号,姓名,年龄,性别); ? 课程(课程号,课程名); ? 学生选课(学号,课程号,成绩)
学 号 姓 名 年 龄 性 别

学 n 选 m 课





成 绩



课程号

课程名

“学生选课”例子关系模型的直观例子
? 学生(学号,姓名,年龄,性别); ? 课程(课程号,课程名); ? 学生选课(学号,课程号,成绩)

“学生选课”例子的关系模型
? 从E-R图转换得到: ? 学生(学号,姓名,年龄,性别); ? 课程(课程号,课程名); ? 学生选课(学号,课程号,成绩) ? 概念模型是对现实原形的理想化; ? 但是,将概念模型直接转换成关系模型之后,还不能说 完全达到了对“学生选课”这一客观世界的理性认识。 ? 所转换得到的关系模型可能还存在问题。

感性认识中存在的问题
? 任务:在关系模型中体现出关于各个学生所在的系的信 息(包括系名和系主任)。 ? 措施:将关系“学生(学号, 姓名, 年龄, 性别)”改为 学生(学号, 姓名, 年龄, 性别, 系名, 系主任) ? 出现的问题:
? 插入异常 ? 当一个系刚成立,系主任已确定,但还未招学生时,无法将 系名和系主任的名字增加到数据库中;因为“学生”实体中 “学号”为码,码不能为空。 ? 删除异常 ? 当一个系的学生全部毕业,删除所有毕业生数据时,系名和 系主任的名字也就删除了。 ? 冗余太大 ? 由于每个学生都对应一个系名和系主任的名字,系名和系主 任的名字有很多冗余。

需要一套严格的理论 来解决这些问题!

关系模式的形式化定义
? 关系模式(R)是一个四元组 R=<U,D,dom,F> 其中: (1)U 表示关系中所有属性的集合; (2)D 表示属性集合U中属性所来自的域; (3)dom 是属性到域的映射;

(4)F 是属性集合U上的一组数据依赖。

关系范式
? 1NF :作为一张二维表的关系,每一个分量必须是不可 再分的数据项;满足这个条件的关系模式就属于1NF。 ? 2NF :若 R∈1NF,且每一个非主属性不存在对码的部 分函数依赖,则R∈2NF。
? 非主属性:不属于码的那些属性。

? 3 NF :若 R∈2NF,且每一个非主属性不存在对码的传 递函数依赖,则R∈3NF。

对“例子”问题的理性认识
? 最初的例子满足3NF。 ? 增加了“系名”和“系主任”后,就出现了如下传递函 数依赖:
? 学号(码)→系名,系名→系主任。

从而就不属于3NF了。

? 不满足3NF的关系模型会出现插入异常、删除异常和冗余 的问题。
? 可以在数据依赖理论的指导下,依靠分解算法对模式进 行分解,使其满足3NF的要求。 ? 就例子而言,可以再划分一个关系,即: 系(系号,系名,系主任名)

“学生选课”例子的关系模型
? ? ? ? 学生(学号,姓名,年龄,性别); 课程(课程号,课程名); 学生选课(学号,课程号,成绩) 系(系号,系名,系主任名)

? 从概念模型向满足规范化要求的关系模型的转换,其实 质是认识过程由感性认识(抽象)上升到理性认识(理 论)的过程,这个过程包含两方面的内容: ? 一方面是有关理论的建立; ? 另一方面是如何在理论的指导下,在具体的设计中, 实现对客观世界的理性认识。 前者是对科学研究而言的,后者是对工程设计而言的。

“学生选课”系统的工程设计
? ? ? ? 学生(学号,姓名,年龄,性别); 课程(课程号,课程名); 学生选课(学号,课程号,成绩) 系(系号,系名,系主任名)

? 建立起正确的关系模型后,还要根据具体的关系数据库管 理系统对该模型进行定义,从而可以由计算机进行处理。 ? 定义“学生”数据表的SQL语句:
? CREATE TABLE STUDENT ( SNO CHAR(9) NOT NULL, SN CHAR(16), SAGE INT, SEX CHAR(1) );

定义“学生选课”关系模型的SQL语句
? CREATE TABLE COURSE ( CNO CHAR(6) NOT NULL, CN CHAR(22) ); ? CREATE TABLE SC ( SNO CHAR(9) NOT NULL, CNO CHAR(6), GRADE INT );

? CREATE TABLE DEPARTMENT ( DNO CHAR(9) NOT NULL, DN CHAR(16), DEAN CHAR(8));

对“学生选课”关系数据库的操作
? 接下来,便可以进行数据的输入、修改和查询,从而完 成对“学生选课”的管理。 ? 一个简单的查询:
? 查询选修了“计算机科学导论”课程,并且成绩在90分以上的 所有学生的学号和姓名。

SELECT SNO,SN FROM STUDENT,SC,COURSE WHERE STUDENT. SNO=SC . SNO AND SC . CNO=COURSE . CNO AND CN=‘计算机科学导论' AND GRADE>90;
? 系统运行以上语句后,即可在屏幕上显示所求的结果。

抽象形态
? ? ? ?

(从一般科学技术方法论的角度)

? 科学抽象是指在思维中:
对同类事物去除其现象的、次要的方面, 抽取其共同的、主要的方面, 从而做到从个别中把握一般, 从现象中把握本质。

? 学科中的抽象形态包含着具体的内容,它们是学科中所 具有的科学概念、科学符号和思想模型。

抽象形态

(从计算学科的角度)

? 抽象、理论和设计是计算学科的3种主要形态。 ? 抽象源于实验科学。 ? 按客观现象的研究过程,抽象形态包括以下4个步骤的内 容:
? ? ? ? (1)形成假设; (2)建造模型并作出预测; (3)设计实验并收集数据; (4)对结果进行分析。

? 在“学生选课”例子中,有关抽象形态的内容包括: A={学生,属性,码,关系,学号,姓名,年龄,性别,课 程,课程号,课程名,成绩,E-R图,“学生选课”E-R 图,关系模型,“学生选课”关系模型,……}

? 通过建立E-R模型和关系模型,实现了对“学生选课” 问题的抽象(感性认识)。

理论形态

(从一般科学技术方法论的角度)

? 科学认识由感性阶段上升为理性阶段,就形成了科学理 论。 ? 科学理论是经过实践检验的系统化了的科学知识体系, 它是由
? 科学概念 ? 科学原理 ? 以及对这些概念、原理的理论论证

所组成的体系。 ? 理论源于数学;它们已经完全脱离现实事物,不受现实 事物的限制,具有精确的、优美的特征,因而更能把握 事物的本质。

理论形态

(从计算学科的角度)

? 理论形态包括以下4个步骤的内容:
? (1)表述研究对象的特征(定义和公理); ? (2)假设对象之间的基本性质和对象之间可能存在的关系(定 理); ? (3)确定这些关系是否为真(证明); ? (4)结论。

? 在“学生选课”例子中,有关理论形态的内容包括: T={关系代数,关系演算,数据依赖理论,……} ? 在数据库理论的指导下,在“学生选课”关系模型(感 性认识)的基础上,建立对“学生选课”问题的理性认 识,从而为“学生选课”管理系统的设计奠定基础。

设计形态

(从一般科学技术方法论的角度)

? 设计源于工程并用于系统或设备的开发,以实现给定的任 务。 ? 设计形态与抽象、理论两个形态具有许多共同点。设 计必须以对自然规律的认识为前提。 ? 设计必须创造出相应的人工系统和人工条件,还必须 认识自然规律在这些人工系统中和人工条件下的具体 表现形式 ? 设计形态具有较强的实践性、社会性、综合性。

设计形态
? ? ? ?

(从计算学科的角度)

? 设计形态包括以下4个步骤的内容:
(1)需求分析; (2)建立规格说明; (3)设计并实现该系统; (4)对系统进行测试与分析。

? 在“学生选课”例子中,有关设计形态的内容包括: D={“学生选课”应用软件,“学生选课”需求说明,……} ? 针对“学生选课”例子,在数据库理论的指导下,将运 用E-R图和关系模型,实现对例子的感性认识和理性认识 ,最后借助某种关系DBMS(如Oracle等),实现“学生 选课”应用软件的编制。最终成果是“学生选课”应用 软件以及相关资料(如需求说明书)。

3个学科形态的内在联系(从一般科学技术方法论的角度)
人类认识过程的两次飞跃

? 第一次飞跃:从物质到精神,从实践到认识。
? 这次飞跃包括两个决定性的环节: ? 科学抽象 ? 科学理论

? 第二次飞跃:从精神到物质,从认识到实践。
? 这次飞跃的实质就是在理论的指导下,以抽象的成果为工具 来完成各种设计工作。

3个学科形态的内在联系(从计算学科的角度)
? 抽象源于现实世界。
? 建立对客观事物进行抽象描述的方法 ? 建立具体问题的概念模型, ? 实现对客观世界的感性认识。

? 理论源于数学。
? 建立完整的理论体系 ? 建立具体问题的数学模型,实现对客观世界的理性认识。

? 设计源于工程 。
? 在对客观世界的感性认识和理性认识的基础上,完成一个具 体的任务; ? 对工程设计中所遇到的问题进行总结,提出问题,由理论界 去解决它。

3.7

计算机语言的发展及其 3个学科形态的内在联系

计算机语言在计算学科中占有特殊的地位,它是计 算学科中最富有智慧的成果之一,它深刻地影响着计算 学科各个领域的发展。不仅如此,计算机语言还是程序 员与计算机交流的主要工具。因此,可以说如果不了解 计算机语言,就谈不上对计算学科的真正了解。

自然语言
? 人类的语言(文字)是人类最普遍使用的符号系统。

? 自然语言符号系统的基本特征:
? (1) 歧义性; ? (2) 不够严格和不够统一的语法结构。

? 例3.2 他的发理得好。
? 他的理发水平高; ? 理发师理他的发理得好。

? 例3.3 他的小说看不完。
? 他写的小说看不完; ? 他收藏的小说看不完; ? 他是个小说迷。

形式语言
? 人们在自然语言符号系统的基础上,逐步建立起了人工 语言符号系统(也称科学语言系统),即各学科的专门 科学术语(符号),使语言符号保持其单一性、无歧义 性和明确性。 ? 人工语言符号系统发展的第二阶段叫形式化语言,简称 形式语言。 ? 形式语言的基本特点:
? (1)有一组初始的、专门的符号集; ? (2)有一组精确定义的符号串形成规则。

? 形式语言的基本要素:
? 语法:形式语言中的转换规则 ? 语义:根据需要,通过赋值或模型对符号串进行严格的语义 解释。

形式语言举例
? 例3.5 语言W定义为: ? 初始符号集:{a,b,c,d,e}。 ? 形成规则:上述符号组成的有限符号串中,能组成英语单词 的为一个公式;否则不是。 ? 问:W是否为一形式语言? ? 答:不是。因为根据形成规则,无法精确地定义转换规则。 ? 例3.6 语言X定义为: ? 初始符号集:{a,b,c,d,e,(,),?,?,?,?}。 ? 形成规则:上述符号组成的有限符号串中,能构成表达式的 为一个公式,否则不是。 ? 问:X是否为一形式语言? ? 答:不是。原因同上。

形式语言举例
? 例3.7 语言Y定义为: ? 初始符号集:{a,b,c,d,e,(,),?,?,?,?}。 ? 形成规则:上述符号组成的有限符号串中,凡以符号“(”开 头且以“)”结尾的符号串,为一公式。 ? 问:Y是否为一形式语言? ? 答:不是。 ? 根据形成规则,无法对不是以符号“ ( ”开头且以“ ) ”结尾 的符号串进行判定。

? 例3.8 语言Z定义为: ? 初始符号集:{a,b,c,d,e,(,),?,?,?,?}。 ? 形成规则:上述符号组成的有限符号串中,凡以符号“(” 开头且以“)”结尾的符号串,为一公式,否则不是。 ? 问:Z是否为一形式语言? ? 答:是。

形式语言举例
? 命题逻辑语言定义为:
(1) 单个命题变项p, q, r,…或命题常项0, 1是命题逻辑公式; (2) 若A是合式公式,则(?A)也是合式公式 ; (3) 若A, B是合式公式,则(A?B), (A?B), (A?B), (A?B) 也是合式公式 ; (4) 只有有限次地应用(1)~(3)形成的符号串是命题逻辑公式。

图灵机
? 阿兰· 麦席森· 图灵(Alan Mathison Turing)
? 1912.6.23-1954.6.7 英国数学家、逻辑学家

? 1936年:
? On Computable Numbers, with an Application to the Entscheidungsproblem (论可计算数及其在 判定问题上的应用) ? 图灵机 (Turing Machine) ? 计算机科学之父

? 从过程的角度来刻画计算的本质。 ? 凡是能用算法方法解决的问题,也一定能用图灵机解决; 凡是图灵机解决不了的问题,任何算法也解决不了。

图灵机的特征
(1) 图灵机由一条两端可无限延长的带子、一个读写头以及 一组控制读写头工作的命令组成,

?

b b

1 0 1 0 0 0

1 0 b b b

?

读-写头

状态 ql 控制器

图灵机的特征
(2) 写在带子上的符号为一个有穷字母表:{S0,S1,S2,… , S p} 。 ? 可以认为这个有穷字母表仅有S0、S1两个字符, ? 其中S0可以看作是“0”,S1可以看作是“1”, ? 由 “0”和“1”组成的字母表可以表示任何一个数。 ? 由于“0”和“1”只有形式的意义,因此,也可以将 S0改称为“白”,S1改称为“黑”,甚至,还可以改 称为“桌子”和“老虎”。

图灵机的特征
(3) 机器的控制状态表为:{q1,q2,…, qm}。将一个图灵 机的初始状态设为q1,在每一个具体的图灵机中还要确定 一个结束状态qw。 ? 一个给定的“程序”可以看作由形如 (qi Sj Sk R(或L或N) ql) 的五元组组成的指令集。 ? 每个五元组定义了机器在一个特定状态下读入一个特定 字符时所采取的动作。具有如下含义:
qi 表示机器目前所处的状态; Sj 表示机器从方格中读入的符号; Sk 表示机器用来代替Sj写入方格中的符号; R、L、N分别表示向右移一格、向左移一格、不移动; ql 表示下一步机器的状态。 ? 例如: q101Rq3 ? ? ? ? ?

图灵机的工作原理
? 带子上的初始信息作为机器计算的输入数据。 ? 机器从给定带子上的某起始点出发,其动作完全由其初 始状态及机内五元组来决定。 ? 机器停止时带子上的信息作为机器计算的结果。

? 以下两种情况是需要避免的:
? 例如,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)=x+1。

练习
? 在图灵的带子机中,设b表示空格,q1表示机器的初始状态,q4 表示机器的结束状态,如果带子上的输入信息是10011001, 读入头对准最右边第一个为1的方格,状态为初始状态q1。请写 出执行以下命令后的计算结果(用二进制表示),并给出计算过 程。 q1 0 1 L q2 q1 1 1 L q3 q1 b b N q4 q2 0 1 L q2 q2 1 1 L q3 q2 b b N q4 q3 0 1 L q2 q3 1 1 L q3 q3 b b N q4 ? 解:计算结果为11111111。

图灵机的计算能力
? 与图灵机等价的其它计算模型:
? 递归函数 ? λ-演算 ? POST规范系统

? 就计算能力而言,图灵机可以模拟现代任何计算机。 ? 但是,其毕竟不同于实际的计算机;在实际计算机的研制 中,还需要有具体的实现方法和实现技术。

作业
? 3.7,3.8, ? 3.9,3.15,3.16,3.17,3.18,3.22,3.24,3.26, 3.27,3.29,

? 3.31,3.33,3.36


相关文章:
第一学期九年级上第三章1-4节自测题
第一学期九年级上科学第三章练习(1-4 节) ...无法判断 13.一个重力不计,摩擦不计的滑轮(如图...1 米/秒 D.10 牛顿,1 米/秒 14.甲、乙两台...
思科第一学期第三章节测试答案
思科第一学期第三章节测试答案_IT/计算机_专业资料。思科第一学期第三章章节...(选择两项) ASP FTP HTML HTTP HTTPS IP 13. 为了将三台计算机连接到一起...
最新CCNA第一学期第三章答案
最新CCNA第一学期第三章答案_计算机硬件及网络_IT/计算机_专业资料。最新CCNA第一学期第三章答案 最新CCNA 第一学期第三章答案 单播通信是的通信。广播通信...
七年级地理(人教版)第一学期第三章综合检测题
七年级地理(人教版)第一学期第三章综合检测题_初一政史地_政史地_初中教育_...13.9 19.7 24.2 25.8 24.8 20.6 14.1 5.3 0.5 2 3 4 5 6 ...
2016-2017学年第一学期八年级地理上册第三章单元测...
2016-2017学年第一学期八年级地理上册第三章单元测试卷(含答案)_政史地_初中...1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B D C 12.目前能缓解...
2013-2014八年级物理第一学期中段考复习资料(1-3章...
2013-2014 八年级物理第一学期中段考复习资料(1-3 章)一、声现象 考点一:...(2011 年) 5、①如图 13 所示,秒表的读数为___s。 ②如图 14 所示,物体...
沪教版六年级第一学期数学 第三章 比和比例 练习精...
沪教版六年级第一学期数学 第三章 比和比例 练习...%x(1—20%) D4000+4000x2.31%X(1—20%) 13...1/6 B 1/5 C1/4 D1/3 ) 14.有编号为 1 ...
粤教沪科版物理九年级上册试题~第一学期第13、14章...
粤教沪科版物理九年级上册试题~第一学期第1314章学月考试试卷 - 2009~2010 学年度第一学期九年级物理第 1314 章学月考试试卷 一、单项选择题(每小题 3 ...
2016年初二第一学期物理前三章测试题
2016年初二第一学期物理前三章测试题_理化生_初中教育_教育专区。2016 年初二第一学期物理前三章测试题一、选择题: (1-12 题单选,每题 2 分,13-15 题多选...
七年级地理(人教版)第一学期第三章综合检测题
七年级地理(人教版)第一学期第三章综合检测题_政...1.3 0.4 3 5 20.3 4 13.9 35.4 5 19....(14 分) (1)山顶 C 点海拔大约为 1600 米。 ...
更多相关标签: