计算机方法论chapter4计算学科中的三个学科形态课件.ppt

1、计算学科中的三个学科形态计算学科中的三个学科形态fuhao_zoufoxmail计算机科学中的问题求解初探计算机科学中的问题求解初探计算学科中的三个学科形态计算学科中的三个学科形态 抽象抽象理论理论设计（三种形态）：计算学科中的基设计（三种形态）：计算学科中的基本内容，基本概念；同时反映了人们的认识是从本内容，基本概念；同时反映了人们的认识是从感性认感性认识（抽象）识（抽象）到到理性认识（理论）理性认识（理论），再由，再由理性认识（理论理性认识（理论）回到回到实践（设计）实践（设计）中来的一般科学思维方法。中来的一般科学思维方法。21、抽象形态、抽象形态p 科学抽象是指在思维中对同类事物去除其

2、现象科学抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。知过程和思维方法。p 学科中的抽象形态包含着具体的内容，它们是学科中的抽象形态包含着具体的内容，它们是学科中所具有的科学概念、科学符号和思想模型。学科中所具有的科学概念、科学符号和思想模型。一、三个形态的主要内容一、三个形态的主要内容3 抽象形态抽象形态源于现实世界（建立对客观事物源于现实世界（建立对客观事物 进行抽象描述的方法，建立概念模型）进行抽象描述的方

3、法，建立概念模型）p 形成假设形成假设p 建造模型并作出预测建造模型并作出预测p 设计实验并收集数据设计实验并收集数据p 对结果进行分析对结果进行分析 4p 科学认识由感性阶段上升为理性阶段，就形成了科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了的科学理论。科学理论是经过实践检验的系统化了的科学知识体系，它是由科学概念、科学原理以及对科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。这些概念、原理的理论论证所组成的体系。p 理论源于数学，是从抽象到抽象的升华，它们已理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事物

4、，不受现实事物的限制，具有经完全脱离现实事物，不受现实事物的限制，具有精确的、优美的特征，因而更能把握事物的本质。精确的、优美的特征，因而更能把握事物的本质。2、理论形态、理论形态5p 表述研究对象的特征（定义和公理）表述研究对象的特征（定义和公理）p 假设对象之间的基本性质和对象之间可能存在的假设对象之间的基本性质和对象之间可能存在的关系（定理）关系（定理）p 确定这些关系是否为真（证明）确定这些关系是否为真（证明）p 结论结论 理论形态理论形态源于数学（建立理论体系，建立源于数学（建立理论体系，建立 数学模型）数学模型）63、设计形态、设计形态p设计形态与抽象、理论两个形态存在的联系：设计

5、形态与抽象、理论两个形态存在的联系：设计源于工程，用于系统或设备的开发，实现给定的任务设计源于工程，用于系统或设备的开发，实现给定的任务n设计形态和抽象、理论两个形态都须以对自然规律的设计形态和抽象、理论两个形态都须以对自然规律的认识为前提认识为前提n设计必须创造出相应的人工系统和人工条件，还必须设计必须创造出相应的人工系统和人工条件，还必须认识自然规律的具体表现形式认识自然规律的具体表现形式p设计形态的主要特征与抽象、理论两个形态的主要区别：设计形态的主要特征与抽象、理论两个形态的主要区别：设计形态具有较强的实践性、社会性、综合性设计形态具有较强的实践性、社会性、综合性7p 需求分析需求分析

6、p 建立规格说明建立规格说明p 设计并实现该系统设计并实现该系统p 对系统进行测试与分析对系统进行测试与分析 设计形态设计形态源于工程（完成一个具体任务，源于工程（完成一个具体任务，总结与升华）总结与升华）8三三个学科形态的内在联系个学科形态的内在联系p在计算学科的原始命题中，蕴含着人类认识过程的在计算学科的原始命题中，蕴含着人类认识过程的两次飞跃两次飞跃n第一次飞跃是从物质到精神，从实践到认识的飞跃。这第一次飞跃是从物质到精神，从实践到认识的飞跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。个是科学理论。n第二次飞跃是从精神

7、到物质，从认识到实践的飞跃。这第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。具来完成各种设计工作。9p抽象源于现实世界。抽象源于现实世界。建立对客观事物进行抽象描述的方法，建立对客观事物进行抽象描述的方法，建立具体问题的概念模型，实现对客观世界的感性认识。建立具体问题的概念模型，实现对客观世界的感性认识。p理论源于数学。理论源于数学。建立完整的理论体系，建立具体问题的数学建立完

8、整的理论体系，建立具体问题的数学模型，从而实现对客观世界的理性认识。模型，从而实现对客观世界的理性认识。p设计源于工程。设计源于工程。对客观世界的感性认识和理性认识的基础上，对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进行总结，完成一个具体的任务；对工程设计中所遇到的问题进行总结，提出问题，由理论界去解决它。提出问题，由理论界去解决它。三三个学科形态的内在联系个学科形态的内在联系 10二、程序设计语言三种形态实例二、程序设计语言三种形态实例自然语言自然语言应用语言应用语言（4GL）高级语言高级语言汇编语言汇编语言机器语言机器语言抽象抽象 理论理论 设计设

9、计t11计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机计算机语言语言抽象抽象理论理论设计设计裸机级裸机级（机 器 语（机 器 语言）的 主言）的 主要 内 容 和要 内 容 和成果成果语言的符号集语言的符号集为：为：0，1；用机器指令对用机器指令对算法进行描述算法进行描述图灵机图灵机(过程语言的基础过程语言的基础)；波斯特系统（字符串处理波斯特系统（字符串处理语言的基础）；语言的基础）；-演算（函数式语言的基演算（函数式语言的基础）等计算模型础）等计算模型冯冯诺依曼型计诺依曼型计算机算机等实现技等实现技术；术；数字电子计算数字电子计算机产品机产品BACK121、自然

10、语言与形式语言、自然语言与形式语言歧义性；歧义性；不够严格和不够统一的语法结构。不够严格和不够统一的语法结构。他的发理得好。他的发理得好。他的理发水平高；他的理发水平高；理发师理他的发理得好。理发师理他的发理得好。他的小说看不完。他的小说看不完。他写的小说看不完；他写的小说看不完；他收藏的小说看不完；他收藏的小说看不完；他是个小说迷。他是个小说迷。13高级语言的歧义性问题高级语言的歧义性问题高级程序设计语言也有语义的歧义性问题，只是高级程序设计语言也有语义的歧义性问题，只是存在的歧义存在的歧义性较少而已性较少而已例例 IF(表达式表达式1)THEN IF(表达式表达式2)THEN 语句语句1

11、ELSE 语语句句2。IF(表达式表达式1)THEN(IF(表达式表达式2)THEN 语句语句1 ELSE 语语句句2)；IF(表达式表达式1)THEN(IF(表达式表达式2)THEN 语句语句1)ELSE 语语句句2。14形式语言形式语言有一组初始的、专门的符号集；有一组初始的、专门的符号集；有一组精确定义的，由初始的、专门的符号组成的符号有一组精确定义的，由初始的、专门的符号组成的符号串转换成另一个符号串的规则。串转换成另一个符号串的规则。在形式语言中，不允许出现根据形成规则无法确定的符在形式语言中，不允许出现根据形成规则无法确定的符号串。号串。15形式语言的语法形式语言的语法16例例1：

12、形式语言语法示例：形式语言语法示例17例例2：形式语言语法示例：形式语言语法示例18例例3：形式语言语法示例：形式语言语法示例19例例4：形式语言语法示例：形式语言语法示例20图灵机与冯图灵机与冯诺依曼型计算机诺依曼型计算机 212.图灵机图灵机图灵的观点及结论：图灵的观点及结论：凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：与图灵机等价的计算模型：递归函数递归函数-演算演算POST规范系统规范系统图灵机是从过程这一角度来刻画

13、计算的本质，其结图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所构简单、操作运算规则也较少，从而为更多的人所理解。理解。22图灵机图灵机图灵机由一条两端可无限延长的带子、一个读写头图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成。以及一组控制读写头工作的命令组成。b b 1 0 1 0 0 0 1 0 b b b 读写头 控制器 状态 q 23图灵机图灵机写在带子上的符号为一个有穷字母表：写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp可以认为这个有穷字母表仅有可以认为这个有穷字母表仅有S0、S1两个字符两个字符其中其

14、中S0可以看作是可以看作是“0”，S1可以看作是可以看作是“1”由由“0”和和“1”组成的字母表可以表示任何一个数组成的字母表可以表示任何一个数24一个给定机器的一个给定机器的“程序程序”机器内的五元组（机器内的五元组（qiSjSkR（或（或L或或N）ql）形式的指令集，五）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。取的动作。5个元素的含义如下：个元素的含义如下：qi表示机器目前所处的状态；表示机器目前所处的状态；Sj表示机器从方格中读入的符号；表示机器从方格中读入的符号；Sk表示机器用来代替表示机器用来代

15、替Sj写入方格中的符号；写入方格中的符号；R、L、N分别表示向右移一格、向左移一格、不移动；分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。表示下一步机器的状态。25一个机器计算的结果是从机器停止时带子上的信息一个机器计算的结果是从机器停止时带子上的信息得到的。得到的。如果如果q1S2S2Rq3指令和指令和q3S3S3Lq1指令同时出现在机器中，指令同时出现在机器中，当机器处于状态当机器处于状态q1，第一条指令读入的是，第一条指令读入的是S2，第二条指，第二条指令读入的是令读入的是S3，那么机器会在两个方块之间无休止地工，那么机器会在两个方块之间无休止地工作。作。-死循环死循

16、环如果如果q3S2S2Rq4和和q3S2S4Lq6指令同时出现在机器中，当指令同时出现在机器中，当机器处于状态机器处于状态q3并在带子上扫描到符号并在带子上扫描到符号S2时，就产生了时，就产生了二义性的问题，机器就无法判定。二义性的问题，机器就无法判定。-歧义歧义26例例5：图灵机示例：图灵机示例b表示空格，表示空格，q1表示机器的初始状态，表示机器的初始状态，q4表示机器的结表示机器的结束状态，设带子上的输入信息是束状态，设带子上的输入信息是10100010，读入头位，读入头位对准对准最右边最右边第一个为第一个为0的方格，状态为初始状态的方格，状态为初始状态q1。规。规则如下。则如下。q1

17、0 1 L q2 q1 1 0 L q3 q1 b b N q4q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4 b b 1 0 1 0 0 0 1 0 b b b 读写头 控制器 状态 ql 27计算过程如下：计算过程如下：28计算结果是计算结果是10100011，即对给定的数加，即对给定的数加1。b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 以上命令计算的是这样一个函数：以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（

18、当没有输入时，即初始状态所指的方格为空格（b）时，不改变）时，不改变空格符，读写头不动并停机。空格符，读写头不动并停机。29图灵机的计算能力图灵机的计算能力图灵机可以计算图灵机可以计算S(x)x1（后继函数），（后继函数），N(x)0（零函数），（零函数），Ui(n)(x1，x2，xn)xi，1in（投影函数）（投影函数）上述上述3个函数的任意组合。个函数的任意组合。从递归论中，我们知道这从递归论中，我们知道这3个函数属于个函数属于初始递归函数初始递归函数任何原始递归函数都是从这任何原始递归函数都是从这3个初始递归函数经有限次的复个初始递归函数经有限次的复合、递归和极小化操作得到的。合、递归和

19、极小化操作得到的。从可计算理论可知，每一个原始递归函数都是图灵机可计算从可计算理论可知，每一个原始递归函数都是图灵机可计算的。的。303、预备知识、预备知识冯冯诺依曼计算机诺依曼计算机 P641946年年2月月14日，世界上第一台数字电子计算机日，世界上第一台数字电子计算机ENIAC在美在美国宾夕法尼亚大学研制成功。国宾夕法尼亚大学研制成功。ENIAC的结构在很大程度上是依照机电系统设计的，还存在的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。重大的线路结构等问题。在图灵等人工作的影响下，在图灵等人工作的影响下，1946年年6月，美国杰出的数学家月，美国杰出的数学家冯冯诺依

20、曼（诺依曼（VonNeumann）及其同事完成了关于）及其同事完成了关于“电子计电子计算装置逻辑结构设计算装置逻辑结构设计”的研究报告，的研究报告，具体介绍了制造电子计算机和程序设计的新思想具体介绍了制造电子计算机和程序设计的新思想至今为止，大多数计算机采用的仍然是冯至今为止，大多数计算机采用的仍然是冯诺依曼型计算机诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯的组织结构，只是作了一些改进而已。因此，冯诺依曼被诺依曼被人们誉为人们誉为“计算机器之父计算机器之父”。31冯冯诺依曼型计算机的组织结构诺依曼型计算机的组织结构 存 储 器 运 算 器 控 制 器 输入/输出设备 命令寄存器

21、32 冯冯诺依曼计算机的体系结构诺依曼计算机的体系结构33基于总线的计算机系统的硬件组成基于总线的计算机系统的硬件组成34输入设备和输出设备输入设备和输出设备35存储器存储器36存储器存储器37运算器和控制器运算器和控制器38寄存器、控制单元寄存器、控制单元39总线（总线（Bus）40CPU和主存储器通过总线相连和主存储器通过总线相连41早期计算机设计中的程序执行早期计算机设计中的程序执行 42基于冯基于冯诺依曼计算机体系结构的程序执行诺依曼计算机体系结构的程序执行434、机器指令（语言）、机器指令（语言）CISC与与RISCo为了实现程序存储的概念，为了实现程序存储的概念，CPU要能识别二要

22、能识别二进制编码的指令进制编码的指令44指令系统指令系统CPU必须能够解码并且执行的机器指令很少必须能够解码并且执行的机器指令很少一旦计算机可以执行一些基本的而且是精选的操一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的作，加入额外的操作理论上是不会改变计算机的能力的。能力的。是否充分利用这种特性导致了两种不同的计是否充分利用这种特性导致了两种不同的计算机设计：算机设计：CISC(Complex instruction set computer)RISC(Reduced instruction set computer)45CISC最初人们采用的是进一步增强

23、原有指令的功最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法。能，并设置更为复杂的指令的方法。采用这种设计思路的计算机被称为复杂指令采用这种设计思路的计算机被称为复杂指令系统计算机（系统计算机（CISC）。）。CISC的思路是由的思路是由IBM公司提出的，并以公司提出的，并以1964年年IBM研制的研制的IBM 360系统为代表。系统为代表。46CISC缺点缺点80%的指令只在的指令只在20%的运行时间里用到。的运行时间里用到。一些指令非常繁杂，而执行效率甚至比用几一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。条简单的基本指令组合的实现还要慢。庞杂

24、的指令系统也给超大规模集成电路庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难，的设计带来了困难，它不但不利于设计自动化技术的应用，延长了设它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本，计周期，增加了成本，容易增加设计中出现错误的机会，从而降低了系容易增加设计中出现错误的机会，从而降低了系统的可靠性。统的可靠性。47RISC思路主要是通过减少指令总数和简化指令的思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指功能来降低硬件设计的复杂度，从而提高指令的执行速度。令的执行速度。优点：与优点：与CISC技术相比技术相比简化了指令系统，适合超大

25、规模集成电路的实现；简化了指令系统，适合超大规模集成电路的实现；提高了机器执行的速度和效率；提高了机器执行的速度和效率；降低了设计成本，提高了系统的可靠性；降低了设计成本，提高了系统的可靠性；提供了直接支持高级语言的能力，简化了编译提供了直接支持高级语言的能力，简化了编译程序的设计。程序的设计。48机器指令机器指令机器指令系统机器指令系统每台数字电子计算机在设每台数字电子计算机在设计中，都规定了一组指令。计中，都规定了一组指令。机器语言机器语言用机器指令形式编写的程序。用机器指令形式编写的程序。在裸机级，计算机语言关于算法的描述采用在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，

26、它的符号集是的是实际机器的机器指令，它的符号集是0,1。支撑实际机器的理论是支撑实际机器的理论是图灵机等计算模型图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计在图灵机等计算模型理论的指导下，有关设计形态的主要成果有形态的主要成果有冯冯诺依曼型计算机诺依曼型计算机等具体实等具体实现思想和技术，以及各类数字电子计算机产品。现思想和技术，以及各类数字电子计算机产品。495、汇编语言、汇编语言 采用字符和十进制数来采用字符和十进制数来代替二进制代码的思想。代替二进制代码的思想。虚拟机的概念：汇编语虚拟机的概念：汇编语言需要通过汇编程序译言需要通过汇编程序译为机器指令；对用户而为机器指令；对

27、用户而言，机器可直接识别汇言，机器可直接识别汇编语言编语言例例7 对对2+6进行计算的算法描述进行计算的算法描述用机器指令对用机器指令对“2+6”进行计算进行计算的算法描述：的算法描述：1011000000000110 0000010000000010 101000100101000000000000汇编语言对汇编语言对“2+6”进行计算的进行计算的算法描述：算法描述：MOV AL，6 ADD AL，2 MOV VC，AL 506、高级语言、高级语言 高级语言分类高级语言分类 高级语言的形式化高级语言的形式化7、4GL（应用语言）（应用语言）51数据类型的抽象数据类型的抽象相对于汇编语言和机器

28、语言，高级语言的相对于汇编语言和机器语言，高级语言的数据数据类型类型的抽象层次有了很大地提高，出现了的抽象层次有了很大地提高，出现了整型整型实型实型字符型字符型布尔型布尔型用户自定义类型用户自定义类型抽象数据类型抽象数据类型数据类型的抽象数据类型的抽象极大地方便了用户对数据的抽极大地方便了用户对数据的抽象描述，为实现软件设计的工程化奠定了基础。象描述，为实现软件设计的工程化奠定了基础。52计算机处理分为四个层次：计算机处理分为四个层次：第一层次是文字和语音，即基本语言信息的第一层次是文字和语音，即基本语言信息的构成；构成；第二层次是语法，即语言的形态结构；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之第三层次是语义，即语言与它所指的对象之间的关系；间的关系；第四层次是语用，即语言与它的使用者之间第四层次是语用，即语言与它的使用者之间的关系。的关系。8、自然语言、自然语言*539、虚拟机、虚拟机与时俱进的抽象层次与时俱进的抽象层次5455