【文档说明】计算机方法论chapter4计算学科中的三个学科形态课件.ppt，共(55)页，1.125 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5363.html

以下为本文档部分文字说明：

计算学科中的三个学科形态fuhao_zoufoxmail计算机科学中的问题求解初探计算学科中的三个学科形态抽象—理论—设计（三种形态）：计算学科中的基本内容，基本概念；同时反映了人们的认识是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）中来的一般科学思

维方法。21、抽象形态科学抽象是指在思维中对同类事物去除其现象的、次要的方面，抽取其共同的、主要的方面，从而做到从个别中把握一般，从现象中把握本质的认知过程和思维方法。学科中的抽象形态包含着具体的内容，它们是学科中所具有的科学概念、科学符号和思想模型

。一、三个形态的主要内容3抽象形态——源于现实世界（建立对客观事物进行抽象描述的方法，建立概念模型）形成假设建造模型并作出预测设计实验并收集数据对结果进行分析4科学认识由感性阶段上升为理性阶段，就形成了科学理论。科学理论是经过实践检验的系统化了

的科学知识体系，它是由科学概念、科学原理以及对这些概念、原理的理论论证所组成的体系。理论源于数学，是从抽象到抽象的升华，它们已经完全脱离现实事物，不受现实事物的限制，具有精确的、优美的特征，因而更能

把握事物的本质。2、理论形态5表述研究对象的特征（定义和公理）假设对象之间的基本性质和对象之间可能存在的关系（定理）确定这些关系是否为真（证明）结论理论形态——源于数学（建立理论体系，建立数学模型）63、设计形态设计形态与抽象、理论两个形态存在的联系：设计源于工程，用于系

统或设备的开发，实现给定的任务设计形态和抽象、理论两个形态都须以对自然规律的认识为前提设计必须创造出相应的人工系统和人工条件，还必须认识自然规律的具体表现形式设计形态的主要特征与抽象、理论两个形态的主要区别：设计形态具有较强的实践性、社

会性、综合性7需求分析建立规格说明设计并实现该系统对系统进行测试与分析设计形态——源于工程（完成一个具体任务，总结与升华）8三个学科形态的内在联系在计算学科的原始命题中，蕴含着人类认识过程的两次飞跃第一次飞跃是从物质到精神，从实践到认识的飞

跃。这次飞跃包括两个决定性的环节：一个是科学抽象，另一个是科学理论。第二次飞跃是从精神到物质，从认识到实践的飞跃。这次飞跃的实质对技术学科（计算学科就是一门技术学科）而言，其实就是要在理论的指导下，以抽象的成果为工具来完成各种设计工作。

9抽象源于现实世界。建立对客观事物进行抽象描述的方法，建立具体问题的概念模型，实现对客观世界的感性认识。理论源于数学。建立完整的理论体系，建立具体问题的数学模型，从而实现对客观世界的理性认识。设计源于工程。对客观世界的感性认识和理性认识的基础上，完成一个具体的任务；对工程设计中所遇到的问题进

行总结，提出问题，由理论界去解决它。三个学科形态的内在联系10二、程序设计语言三种形态实例自然语言应用语言（4GL）高级语言汇编语言机器语言抽象理论设计t11计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸机级（机器语言）的主要内容和成果语言的符号集为：{0，1}；用

机器指令对算法进行描述图灵机(过程语言的基础)；波斯特系统（字符串处理语言的基础）；λ-演算（函数式语言的基础）等计算模型冯·诺依曼型计算机等实现技术；数字电子计算机产品BACK121、自然语言与形式语言歧义性；不够严格和不够统一的语法结构。他的发理得好。他的

理发水平高；理发师理他的发理得好。他的小说看不完。他写的小说看不完；他收藏的小说看不完；他是个小说迷。人类的语言（文字）是人类最普遍使用的符号系统。其最基本、最普遍的形式是自然语言符号系统自然语言是某一社会发展中形成的一种民族语言。例如，汉语、英语、法语和俄语等。13高级语言的歧义性

问题高级程序设计语言也有语义的歧义性问题，只是存在的歧义性较少而已例IF(表达式1)THENIF(表达式2)THEN语句1ELSE语句2。IF(表达式1)THEN(IF(表达式2)THEN语句1EL

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

根据形成规则无法确定的符号串。人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。形式语言是进行形式化工作的元语言，它是以数学和数理逻辑为基础的科学语言。15形式语言的语法形式语言的语法：形式语言中的转换规则。

语法不包含语义。在一个给定的形式语言中，可以根据需要，通过赋值或模型对其进行严格的语义解释，从而构成形式语言的语义。语法（Syntax）和语义（Semantics）要作严格的区分。16例1：形式语言语法示例语

言W定义为：初始符号集：{a，b，c，d，e}。形成规则：上述符号组成的有限符号串中，能组成一英语单词的为一公式；否则不是。问：W是否为一形式语言？答：不是。因为，根据形成规则，无法精确地定义转换规则。原因：形

成规则（语法）中包含了语义。17例2：形式语言语法示例语言X定义为：初始符号集：{a，b，c，d，e，(，)，，，，}。形成规则：上述符号组成的有限符号串中，构成表达式的为一公式，否则不是。问：X是否为一形式语言？答：不是

。原因：与例1相同。18例3：形式语言语法示例语言Y定义为：初始符号集：{a，b，c，d，e，(，)，，，，}。形成规则：上述符号组成的有限符号串中，凡以符号“(”开头且以“)”结尾的符号串，为一公式。问：Y是否为一形式语言？答：不是。因为，根据形成规则，无法对不是

以符号“(”开头且以“)”结尾的符号串进行判定。例如，(a+b)c。19例4：形式语言语法示例语言Z定义为：初始符号集：{a，b，c，d，e，(，)，，，，}。形成规则：上述符号组成的有限符号串中，凡以符号“（”开头且以“）”结尾的符号串，为一公式，否则不是

。问：Z是否为一形式语言？答：是。20图灵机与冯·诺依曼型计算机图灵机——计算模型（理论）图灵——计算机科学之父冯·诺依曼型计算机——计算机组织结构（设计）冯·诺依曼——计算机器之父212.图灵机图灵的观点及结论：凡是能用算法方法解决的

问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：递归函数λ-演算POST规范系统图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。22图灵机图灵机由一条两端可无限延长的

带子、一个读写头以及一组控制读写头工作的命令组成。„bb10100010bbb„读－写头控制器状态q23图灵机写在带子上的符号为一个有穷字母表：{S0，S1，S2，…，Sp}可以认为这个有穷字母表仅有S0、S1两个字符其中S0可以看作是“0”，S1可以看作是“1”由“0”和

“1”组成的字母表可以表示任何一个数24一个给定机器的“程序”机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：qi表示机器目前所处的状态；Sj表示

机器从方格中读入的符号；Sk表示机器用来代替Sj写入方格中的符号；R、L、N分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。25一个机器计算的结果是从机器停止时带子上的信息得到的。如果q1S2S2

Rq3指令和q3S3S3Lq1指令同时出现在机器中，当机器处于状态q1，第一条指令读入的是S2，第二条指令读入的是S3，那么机器会在两个方块之间无休止地工作。----死循环如果q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中，当机器处于状态q3并

在带子上扫描到符号S2时，就产生了二义性的问题，机器就无法判定。----歧义26例5：图灵机示例b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，设带子上的输入信息是10100010，读入头位对准最右边第一个为0的方格，状态为初始状态q1。规则如下。q101Lq2q110

Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq4„bb10100010bbb„读－写头控制器状态ql27计算过程如下：(1)q101Lq2(2)q110Lq3(

3)q1bbNq4(4)q200Lq2(5)q211Lq2(6)q2bbNq4(7)q301Lq2(8)q310Lq3(9)q3bbNq428计算结果是10100011，即对给定的数加1。„bb10100

010bbb„读－写头控制器状态ql以上命令计算的是这样一个函数：S(x)＝x＋1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。29图灵机的计算能力图灵机可以计算S(

x)＝x＋1（后继函数），N(x)＝0（零函数），Ui(n)(x1，x2，…，xn)＝xi，1≤i≤n（投影函数）上述3个函数的任意组合。从递归论中，我们知道这3个函数属于初始递归函数任何原始递归函数都是从这3个初始递归函数经有限次的复合、

递归和极小化操作得到的。从可计算理论可知，每一个原始递归函数都是图灵机可计算的。303、预备知识——冯·诺依曼计算机P641946年2月14日，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功

。ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯·诺依曼（VonNeumann）及其同事完成了关于“电子计算装置逻辑结构设计”的

研究报告，具体介绍了制造电子计算机和程序设计的新思想至今为止，大多数计算机采用的仍然是冯·诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯·诺依曼被人们誉为“计算机器之父”。31冯·诺依曼型计算机的组织结构存储器运算器控制器输入/输出设备命令寄存器32冯·诺依曼

计算机的体系结构中央处理器控制器□□□„□□寄存器□算术逻辑部件输入设备输出设备辅助存储设备主存储器33基于总线的计算机系统的硬件组成电源CPU主存储器键盘鼠标适配器端口光盘驱动器适配器端口硬盘驱动器适配器端口显示器端口适配器端口扩充插槽打印机端口适配器端口34输入设备和输出设备作用：是将信息输

入计算机和输出计算机。常用的文字输入设备是键盘（还有扫描仪、穿孔卡片读入机和鼠标等专用输入设备）。当在键盘上按下一个键时，按下的键通过编码变换成机器可读的数据形式，如字符“A”变换成ASCII码“1000001”，该编码数据随即存入存储器等待处理，通过与“1000001”对应的字

符点阵数据在屏幕上显示一个字符“A”。输出设备有打印机、显示器、绘图仪、磁记录设备等。35存储器存储器是一种数据或信息的存储部件分为两大类：内存储器（内存）外存储器（外存）36存储器内存随机存储器（RAM）只读存储器（ROM）：一般用于BIOS外存硬盘软

盘光盘磁带优盘（USB盘）固态硬盘（SSD）相变存储（PCM）37运算器和控制器CentralProcessingUnit（中央处理单元，CPU）38寄存器、控制单元计算机中控制数据操作的电路并不与主存直接相连这些电路被封装在一起，即CPUCPU含有

自己的存储单元（register）寄存器（Register）作为临时空间来存储CPU所操作的数，保存算术逻辑单元的输入与输出数据控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在哪个register39总线（Bus）总线：CPU与

主存之间用总线连接利用总线CPU通过提供存储单元目标地址以及读信号来选择、读取数据CPU通过提供存储单元目标地址以及写信号来放置、写入信号40CPU和主存储器通过总线相连41早期计算机设计中的程序执行在早期计算机设计中，人们认为，程序与

数据是两种完全不同的实体。自然地将程序与数据分离，数据存放在存储器中，程序则作为控制器的一个组成部分（如外插型的程序）。这样，每执行一个程序，都要对控制器进行设置。如在ENIAC中，编制一个解决小规模问题的程序，就要在40多块几英尺长的插接板上，插上几

千个带导线的插头。显然，这样的机器效率不仅低，且灵活性也很差。42基于冯·诺依曼计算机体系结构的程序执行冯·诺依曼计算机的体系结构，也即存储程序式计算机的体系结构，则是将程序与数据一样看待，对程序像数据那样进行适当的编码，然后与数据一

起共同存放在存储器中。计算机可以通过改变存储器中的内容，对数据进行操作。从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变化。434、机器指令（语言）•CISC与RISC为了实现程序存储的概念，CP

U要能识别二进制编码的指令44指令系统CPU必须能够解码并且执行的机器指令很少一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的能力的。是否充分利用这种特性导致了两种不同的计算机设计：CISC(Complexinstru

ctionsetcomputer)RISC(Reducedinstructionsetcomputer)45CISC最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法。采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。CISC的思路是由IBM公

司提出的，并以1964年IBM研制的IBM360系统为代表。46CISC缺点80%的指令只在20%的运行时间里用到。一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。庞杂的指令系统也给超大规模集成电路（VLSI）

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

集成电路的实现；提高了机器执行的速度和效率；降低了设计成本，提高了系统的可靠性；提供了直接支持高级语言的能力，简化了编译程序的设计。48机器指令机器指令系统——每台数字电子计算机在设计中，都规定了一组指令。机器语言——用机器指令形式编写的程序。在裸机级，计算机

语言关于算法的描述采用的是实际机器的机器指令，它的符号集是{0,1}。支撑实际机器的理论是图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯·诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。49

5、汇编语言•采用字符和十进制数来代替二进制代码的思想。虚拟机的概念：汇编语言需要通过汇编程序译为机器指令；对用户而言，机器可直接识别汇编语言例7对2+6进行计算的算法描述用机器指令对“2+6”进行计算的算法描述：101100000000011

00000010000000010101000100101000000000000汇编语言对“2+6”进行计算的算法描述：MOVAL，6ADDAL，2MOVVC，AL506、高级语言•高级语言分类•高级语言的形式化7、4GL（应用语言）•51数据类型的抽象相对于汇编语言和机器

语言，高级语言的数据类型的抽象层次有了很大地提高，出现了整型实型字符型布尔型用户自定义类型抽象数据类型数据类型的抽象极大地方便了用户对数据的抽象描述，为实现软件设计的工程化奠定了基础。52计算机处理分为四个层次：第一

层次是文字和语音，即基本语言信息的构成；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之间的关系；第四层次是语用，即语言与它的使用者之间的关系。8、自然语言*539、虚拟机——与时俱进的抽象层次54虚拟机的层次

结构应用语言虚拟机高级语言虚拟机汇编语言虚拟机操作系统虚拟机固件虚拟机实际机器概念机抽象逐级编译或解释执行高易用性低低执行效率高多占用硬软件资源少每个上层都是下层的虚拟机，越上越虚拟；往上是概念机的抽象55