第8章(1)软件进化

1、1 第第8章计算机章计算机进化规律的发掘进化规律的发掘（ 1 ）8.1计算机软件进化规律的发掘计算机软件进化规律的发掘28.1计算机计算机软件进化规律的发掘软件进化规律的发掘8.1.1 数值计算的进化数值计算的进化 8.1.2 计算机程序的进化计算机程序的进化8.1.3 数据存储的进化数据存储的进化8.1.4 知识处理的进化知识处理的进化 8.1.5 软件进化规律软件进化规律3 简简 述述计算机软件的进化经历了计算机软件的进化经历了: 从从“算术运算算术运算”到到“微积分运算微积分运算”再到再到“解方程解方程”的进化的进化 从从“数值计算数值计算”到到“信息处理信息处理”再到再到“知识推理知识

2、推理”的进化。的进化。 通过软件进化的研究，通过软件进化的研究，从软件解决问题的能力从软件解决问题的能力由简单到复杂、由低级到高级逐渐发展过程中，由简单到复杂、由低级到高级逐渐发展过程中，找出进化规律，来提升我们的软件开发能力，进找出进化规律，来提升我们的软件开发能力，进一步促进软件的进化。一步促进软件的进化。4 8.1.1 数值计算的进化数值计算的进化(一一) 数值计算能力进化数值计算能力进化(二二) 二进制计算到二值数据表示二进制计算到二值数据表示5(一一) 数值计算能力进化数值计算能力进化 初等函数初等函数 微积分运算微积分运算 解方程解方程 6 (1)加加(+)是最是最基本运算基本运算

3、 (2)减减(-)是利用减数的补数是利用减数的补数(求反加求反加1)，变减为加变减为加 (3)乘乘()是把是把乘变成累加乘变成累加 如如： 53=5+5+5，即即5加加3次次 (4)除除()是把除变成累减是把除变成累减的的次数次数， 如如： 63为为6-3-3=0，减了减了2次次，即商为即商为21、 7 初等函数的计算初等函数的计算不是利用定义不是利用定义,而是利用台而是利用台劳级数公式劳级数公式 来计算的来计算的,即即变成加减乘除运算变成加减乘除运算.(1)三角公式三角公式(2)指数公式指数公式 2、初等函数初等函数 357sin1!3!5!7!xxxxx 2311!2 !3!xxxxe 取

4、级数的项数在于满足计算精度。取级数的项数在于满足计算精度。83、微积分运算、微积分运算,000( )( )( )limxf xf xf xx x ,00( )()( )f xf xfxxx 01( )lim( )bnkxkaf xdxf xx 1( )()bnkkaf x dxf xx 变成变成(2)积分运算积分运算(求和求和) (1)微分运算微分运算(差分化差分化) 变成变成 取取x 尽量小，就能满足误差精度尽量小，就能满足误差精度9二阶导数的差分方程二阶导数的差分方程2210212102( )( )( )()()( )()2 ( )()d f xddf xdxdxdxf xf xf xf

5、xxxxf xf xf xx高阶导数类似处理。高阶导数类似处理。10一阶和二阶导数的结点关系一阶和二阶导数的结点关系11偏微分方程的偏微分方程的差分方程差分方程1211222nnnnnjjjjjuuuuuuuyyxx说明说明:n表示y方向的增长,j表示x方向的增长12偏导数结点关系图偏导数结点关系图yxx134、解方程、解方程(1)方程的直接求解方程的直接求解线代数方程组的一般表示为线代数方程组的一般表示为(数据与运算符是混数据与运算符是混在一起表示的在一起表示的):11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb1

6、4计算机中并不存放方程的结构形式。计算机中并不存放方程的结构形式。数据与运算符是分开的，数据数据与运算符是分开的，数据放在数据存储单元中，放在数据存储单元中，运运算符算符只出现在程序指令的操作码中。只出现在程序指令的操作码中。线代数方程线代数方程去掉运算符，去掉运算符，形成三个数组，它们分别存放形成三个数组，它们分别存放在不同的地方。在不同的地方。解方程时，是程序中指令的操作码对三个数组进行处理，解方程时，是程序中指令的操作码对三个数组进行处理，最后得出最后得出xi值。值。15线代数方程组的高斯主元素消去法线代数方程组的高斯主元素消去法(加减乘除加减乘除): 系数距阵消元成单位距阵：系数距阵消

7、元成单位距阵：1112111212222212,nnnnnnnnaaaxbaaaxbaaaxb 16 计算机的计算过程与计算机的计算过程与“人人”的的计算过程是不一样的。计算过程是不一样的。“人人”直接在方程中进行处理，直接在方程中进行处理，程序程序是指令中操作是指令中操作码对数据的地址码进行操作的。码对数据的地址码进行操作的。1122100010,001nnxbxbxb 17 偏微分方程边值问题偏微分方程边值问题的求解一般是在一个的求解一般是在一个区域内进行，区域中的点是未知数，区域边区域内进行，区域中的点是未知数，区域边界点是巳知数。界点是巳知数。 偏微分方程偏微分方程差分化差分化后，经过

8、整理就变成了后，经过整理就变成了以区域中点的未知数形成的线代数方程组。以区域中点的未知数形成的线代数方程组。 偏微分方程的求解就变成了线代数方程组偏微分方程的求解就变成了线代数方程组的求解的求解(加减乘除加减乘除)18汽轮机转子的网络划分汽轮机转子的网络划分19微分方程数值计算的价值微分方程数值计算的价值 传统的数学分析方法传统的数学分析方法(解析求解表达式推演，得解析求解表达式推演，得到的解是表达式到的解是表达式)只能解决少数的较简单的和典型的只能解决少数的较简单的和典型的微分方程的求解微分方程的求解。 微分方程的微分方程的数值计算方法数值计算方法，无论是常系数还是变，无论是常系数还是变系数

9、，是线性还是非线性，都能得到解决。系数，是线性还是非线性，都能得到解决。 解决的手段是差分方法解决的手段是差分方法(加减乘除加减乘除)，让计算机来，让计算机来完成。完成。20(2)方程的迭代求解方程的迭代求解迭代法的思想是迭代法的思想是:将方程将方程变成变成( )0f x ( )xx建立迭代法方程建立迭代法方程:1()1,2,nnxxn初值初值x1任意选定，经过无限次迭代后，使任意选定，经过无限次迭代后，使:1nnxx21 牛顿牛顿1()()nnnnfxxxfx1,2,n 牛顿牛顿()0nf x22231( )xx24 BP神经网络中权值和阈值的求解神经网络中权值和阈值的求解就是采用就是采用(

10、1)( )ijijijW kW kx iiikk()( ) 1例如：例如： 异或问题的异或问题的B-P神经网络神经网络 计算机运行结果计算机运行结果 迭代次数：迭代次数：16745次；总误差：次；总误差：0.05隐层网络权值和阈值：隐层网络权值和阈值： w11=5.24，w12=5.23，w21=6.68，w22=6.64 1=8.01 2=2.98输出层网络权值和阈值：输出层网络权值和阈值：T1=-10，T2=10， =4.79275、数值计算的误差问题、数值计算的误差问题数值计算的数值计算的误差积累会引起结果的错误误差积累会引起结果的错误！例如，把正数算出负数。例如，把正数算出负数。为了使

11、误差积累不产生错误的结果，需要：为了使误差积累不产生错误的结果，需要：(1)原始数据的有效位数要比结果数据有效位数原始数据的有效位数要比结果数据有效位数多多出出1-2位。位。(2)使用不很合理的公式时，要检查可能出现错误使用不很合理的公式时，要检查可能出现错误的地方，的地方，增加判别公式增加判别公式，限制错误发生。，限制错误发生。28(二二) 二进制计算到二值数据表示二进制计算到二值数据表示十进制计算十进制计算 二进制计算二进制计算 汉字编码汉字编码+点阵表示点阵表示(字形字形) 图象点阵表示图象点阵表示(各点的色彩各点的色彩)291、十进制到二进制的转换十进制到二进制的转换计算机只能采用二进

12、制！计算机只能采用二进制！ 在使用计算机进行数值计算时，在使用计算机进行数值计算时，虽然我们输入的数是十进制的，计虽然我们输入的数是十进制的，计算机内有一个程序算机内有一个程序(类似于初等函数类似于初等函数子程序子程序)会把数据转换成二进制。会把数据转换成二进制。302、 汉字表示汉字表示(1)英文字母、数字、标点符号等用英文字母、数字、标点符号等用ASCII码值码值表示表示 如如“A”的码值的码值65，数字，数字“0”的的码值的的码值48。(2)汉字编码汉字编码 一个汉字用一个汉字用4位十进制数字编码，前两位是位十进制数字编码，前两位是区区号号，后两位是，后两位是位号位号。 一个汉字的内码占

13、两个字节，第一个字节用于一个汉字的内码占两个字节，第一个字节用于区号区号，第二个字节用于，第二个字节用于位号位号。汉字的形状用点阵数据表示汉字的形状用点阵数据表示。如。如“工工”的点阵表的点阵表示示:31“工工”字的点阵表示字的点阵表示323、 图像的表示图像的表示 图像看成点图像看成点(像素像素)的集合，每个像素的颜色的集合，每个像素的颜色用三个字节用三个字节(24位位)表示。表示。 任何颜色由红、绿、蓝三色混合而成，三色任何颜色由红、绿、蓝三色混合而成，三色各占一个字节，一个字节中各位的各占一个字节，一个字节中各位的0或或1的不的不同表示，构成了不同的颜色浓度。同表示，构成了不同的颜色浓度

14、。 一幅图像在计算机中表示为一个长度惊人的一幅图像在计算机中表示为一个长度惊人的0、1串。串。334、 视频的表示视频的表示 视频是连续播放一系列图像。每幅图视频是连续播放一系列图像。每幅图像称为帧。像称为帧。 每秒播出帧的数目在每秒播出帧的数目在2430幅图像时，幅图像时，就是像电影一样的视频。就是像电影一样的视频。 由于视频数据量太大，一般采取由于视频数据量太大，一般采取MPEG压缩技术，相邻帧只记录前面帧压缩技术，相邻帧只记录前面帧的变化部分。的变化部分。34 8.1.2 计算机程序的进化计算机程序的进化二进制程序二进制程序 汇编程序汇编程序 高级语言程序高级语言程序 程序生成程序生成3

15、51、二进制程序二进制程序 二进制程序是最原始的计算机运行控制程序二进制程序是最原始的计算机运行控制程序，由，由一串机器指令组成。一串机器指令组成。 机器指令含：操作码和地址码机器指令含：操作码和地址码例如：操作码：例如：操作码：02 加法加法 地址码：地址码：1001 x 05 取数取数 1002 y 06 送数送数 1003 空空 完成完成 x+y 的计算程序的计算程序(八进制八进制)为：为： 3001 05 1001 取取 x 3002 02 1002 加加 y 3003 06 1003 送结果送结果 36其中其中3001-3003是存储程序的地址。是存储程序的地址。这里程序中的这里程序

16、中的操作码和地址码都是二进制操作码和地址码都是二进制表示的，表示的，这样程序就完全用二进制形式这样程序就完全用二进制形式存入计算机中。存入计算机中。37机器语言程序的重要特点机器语言程序的重要特点 （1）在地址码中只放数据，不放运算符。运算）在地址码中只放数据，不放运算符。运算符都在操作码中，即符都在操作码中，即运算和数据是分开的运算和数据是分开的。（2）操作码中的指令是）操作码中的指令是对变量的地址进行操作对变量的地址进行操作，而不是直接对变量的操作而不是直接对变量的操作。 这是一种这是一种间接操作间接操作，这适合机器的运算。，这适合机器的运算。38间接操作的好处间接操作的好处 （1）对于不

17、同数据的相同操作，只需把不同数对于不同数据的相同操作，只需把不同数据放入相同地址单元中，程序不用变化据放入相同地址单元中，程序不用变化。间接。间接操作为程序的通用性带来了好处。操作为程序的通用性带来了好处。（2）编程序时，不要求先把数据都准备好后再编程序时，不要求先把数据都准备好后再编程序，但要求把数据的存放地址都分配好后，编程序，但要求把数据的存放地址都分配好后，就可以编程序。就可以编程序。 39 我国我国60年代年代的第一台计算机的第一台计算机(电子管电子管)103型型(仿苏仿苏M3)，提供的就是机器语言，提供的就是机器语言(二进制二进制)。 编程序时需要自己编编程序时需要自己编“十进制到

18、二进制十进制到二进制”、“初等初等函数函数”等子程序。等子程序。 编一个实用程序编一个实用程序(八进制八进制)很长，程序纸有几十页厚，很长，程序纸有几十页厚，程序是用纸穿孔输入，很容易出错。上机计时收费，程序是用纸穿孔输入，很容易出错。上机计时收费，24小时排队上机，上机心情很紧张，上机很多次才小时排队上机，上机心情很紧张，上机很多次才能通过能通过。402、汇编程序汇编程序 汇编程序是将二进制汇编程序是将二进制(或八进制、十六进制或八进制、十六进制)程序中的程序中的数字用字母符号数字用字母符号(助记符助记符)代替代替。 使用汇编程序简化了繁琐的数字。使用汇编程序简化了繁琐的数字。上例程序的汇编

19、程序为：上例程序的汇编程序为： LDA x 取取 x ADD y 加加 y STA r 送结果送结果 41汇编程序返回二进制程序汇编程序返回二进制程序 汇编程序便利人书写，运行时还是要返回到汇编程序便利人书写，运行时还是要返回到二进制程序。二进制程序。 汇编程序通过汇编程序通过解释程序解释程序返回到二进制程序。返回到二进制程序。 解释程序很简单，只需要二张对照表即可，一解释程序很简单，只需要二张对照表即可，一个是指令操作码的二进制对照表，另一个是数个是指令操作码的二进制对照表，另一个是数据地址的二进制对照表。据地址的二进制对照表。423、高级语言程序、高级语言程序 高级语言程序是用高级语言程序

20、是用接近自然语言和数学语言编写接近自然语言和数学语言编写的程序的程序。接近人们的习惯，便利非专业人员编写。接近人们的习惯，便利非专业人员编写。 高级语言程序种类很多，如：高级语言程序种类很多，如：C、Pascal、ADA等，等，主要完成数值计算。主要完成数值计算。 高级语言把程序的基本结构归纳为：高级语言把程序的基本结构归纳为：顺序、选择、顺序、选择、循环循环。任何复杂的程序都是这。任何复杂的程序都是这三个基本结构的嵌套三个基本结构的嵌套组合。组合。43高级语言的效果高级语言的效果(1)高级语言高级语言便利了程序的编写便利了程序的编写(2)高级语言的高级语言的功能更强了功能更强了(很多标准的程

21、序段通过连很多标准的程序段通过连接程序直接嵌入到用户程序中接程序直接嵌入到用户程序中)，极大地提高了解决，极大地提高了解决问题的能力和扩充了计算机的应用范围问题的能力和扩充了计算机的应用范围(3)高级语言的应用高级语言的应用促进了新语言的出现促进了新语言的出现: 面向对象语言、数据库语言、网络编程语言以及第面向对象语言、数据库语言、网络编程语言以及第四代语言四代语言(程序生成程序生成)等等444、高级语言程序的编译、高级语言程序的编译 高级语言程序同样要返回到二进制程序，这高级语言程序同样要返回到二进制程序，这就是就是编译程序编译程序。 编译程序包括编译程序包括词法分析、语法分析、代码生词法分

22、析、语法分析、代码生成。成。它的技术原理同人工智能中的专家系统。它的技术原理同人工智能中的专家系统。 计算机程序的本质还是二进制程序计算机程序的本质还是二进制程序。 转换过程如下：转换过程如下：源程序源程序编译程序编译程序二进制程序二进制程序执行45 8.1.3 数据存储的进化数据存储的进化(一一)数据存储的进化过程数据存储的进化过程(二二)数据库与数据仓库数据库与数据仓库(三三)数据存储的进化小结数据存储的进化小结46数据存储的进化过程数据存储的进化过程变量变量 数组数组 线性表线性表 堆栈与队列堆栈与队列 数据库数据库 数据仓库数据仓库471、变量变量 线性表线性表(1)变量：计算公式中的

23、基本元素，分配一个存变量：计算公式中的基本元素，分配一个存 储地址。储地址。(2)数组：数组：相同类型相同类型的一维、二维数据集合，存的一维、二维数据集合，存 储地址是连续的。储地址是连续的。(3)线性表：线性表：不同类型数据不同类型数据的集中存储。如学生的集中存储。如学生 表中含：姓名、性别、年龄等不同表中含：姓名、性别、年龄等不同 类型数据集合。类型数据集合。482、堆栈与队列堆栈与队列用于特殊运算而暂时存放的数组或线性表用于特殊运算而暂时存放的数组或线性表(1)堆栈：对进栈的数据采用堆栈：对进栈的数据采用后进先出后进先出的处理方的处理方式，如对急诊病人的处理。式，如对急诊病人的处理。(2

24、)队列：对进队的数据采用队列：对进队的数据采用先进先出先进先出的处理方的处理方式，如对一般病人的处理。式，如对一般病人的处理。493、数据库数据库通过通过数据库管理系统数据库管理系统管理的数据文件。管理的数据文件。数据库管理系统数据库管理系统(数据库语言数据库语言)的主要功能为：的主要功能为：1、建立数据库、建立数据库 描述数据库的结构并输入数据。描述数据库的结构并输入数据。2、管理数据库、管理数据库 （1）控制数据库系统的运行；）控制数据库系统的运行； （2）进行数据的检索、插入、删除和修改的操作；）进行数据的检索、插入、删除和修改的操作；3、维护数据库、维护数据库 （1）修改、更新数据库；

25、）修改、更新数据库； （2）恢复故障的数据库；）恢复故障的数据库；4、数据通信、数据通信 完成数据的传输。完成数据的传输。数据库存储结构数据库存储结构数据库由二大部分组成：文件头部分记录正文部分数据库由二大部分组成：文件头部分记录正文部分文件头部分包括：数据库记录信息和各字段的说明，文件头部分包括：数据库记录信息和各字段的说明，数据库记录信息是由年月日，记录数，文件头长度，记录长度数据库记录信息是由年月日，记录数，文件头长度，记录长度等信息组成。等信息组成。 0DH和和00H两字节为文件头的尾。两字节为文件头的尾。51记录正文部分的结构（一个记录）为记录正文部分的结构（一个记录）为:524、数

26、据仓库数据仓库 数据仓库是大量数据的集合，用于支持管理中数据仓库是大量数据的集合，用于支持管理中决策制定决策制定过程。过程。按决策按决策主题重主题重新组合新组合二维数据二维数据DBDB1DBDBi DBDBnDW多维数据多维数据53数据仓库结构数据仓库结构元数据高 度 综 合 数 据 层轻 度 综 合 数 据 层当 前 基 本 数 据 层历 史 数 据 层54(二二)数据库与数据仓库数据库与数据仓库1. 数据库用于数据库用于管理业务管理业务2. 数据仓库用于数据仓库用于决策支持决策支持551. 数据库用于管理业务数据库用于管理业务数据库存储数据库存储当前的现状数据当前的现状数据，用于，用于管理

27、业务管理业务(商商业计算业计算)。(1)不同的业务不同的业务(人事、财务、设备等人事、财务、设备等)需要建立需要建立不同的数据库。不同的数据库。(2)随时间、业务的变化随时修改数据随时间、业务的变化随时修改数据(3)数据库是共享的数据数据库是共享的数据56管理管理业务业务(商业计算商业计算)管理业务管理业务(商业计算商业计算)主要是利用数据库来完成主要是利用数据库来完成(1)对数据库的查询、浏览来掌握现状对数据库的查询、浏览来掌握现状 如：记录查找时如：记录查找时“”表示数值相等或字符相表示数值相等或字符相同同(2)对数据库的处理是对数据库中记录的增加、删对数据库的处理是对数据库中记录的增加、

28、删除、修改工作除、修改工作 对记录对记录编码用到编码用到“、”(3)对数据库的统计计算只用到初等运算对数据库的统计计算只用到初等运算 ( ) 如：工资中加入奖金，减去房租。如：工资中加入奖金，减去房租。572. 数据仓库的用于决策支持数据仓库的用于决策支持 数据仓库存储的数据包括：数据仓库存储的数据包括：当前数据、历史当前数据、历史数据和汇总数据数据和汇总数据。用于。用于决策支持决策支持。(1)历史数据用于预测历史数据用于预测(2)从汇总数据的比较从汇总数据的比较(不同角度不同角度)中发现问题中发现问题(3)从祥细数据中找出原因从祥细数据中找出原因58数据库与数据仓库的对比数据库与数据仓库的对

29、比59数据仓库数据仓库的决策支持的决策支持 利用汇总数据的利用汇总数据的比较比较(、)来发现问题来发现问题 利用多维数据分析找出原因利用多维数据分析找出原因(从汇总数据追踪到从汇总数据追踪到原始数据原始数据) 利用历史数据进行预测分析利用历史数据进行预测分析(预测模型的计算预测模型的计算) 利用利用不同层次汇总数据不同层次汇总数据(不同粒度数据不同粒度数据)适应不适应不同层同层 次管理人员的决策支持次管理人员的决策支持60(三三)数据存储的进化小结数据存储的进化小结数组数组一般用于数值计算，一般用于数值计算，数据库数据库用于管理业务，用于管理业务，数据仓库数据仓库用于决策支持。用于决策支持。计

30、算机的数据存储量愈来愈大，数据种类也愈计算机的数据存储量愈来愈大，数据种类也愈来愈多，这样使计算机处理问题的能力也愈来愈多，这样使计算机处理问题的能力也愈来愈强。来愈强。数据存储是计算机重要组成部分，数据存储是计算机重要组成部分，数据存储的数据存储的进化是计算机进化的一个大方面。进化是计算机进化的一个大方面。 618.1.4 知识推理的进化知识推理的进化知识推理进化的典型过程：知识推理进化的典型过程：知识表示与知识推理知识表示与知识推理 专家系统专家系统 知识发现与数据挖掘知识发现与数据挖掘 621、知识表示与知识推理、知识表示与知识推理 知识表示知识表示：知识在计算机中的存储和使用的形：知识

31、在计算机中的存储和使用的形 式，典型的知识表示有：式，典型的知识表示有： 产生式规则产生式规则(A B)、 谓词谓词 P(x，y) 等等知识推理知识推理：从已知条件推出结果：从已知条件推出结果 规则的推理：假言推理：规则的推理：假言推理： 谓词的推理：归结原理谓词的推理：归结原理 (反证法反证法)qp pq， 63 书本是人类传承知识的主要手段。书本是人类传承知识的主要手段。 在计算机中在计算机中“书本书本”以文本形式存储，但以文本形式存储，但是计算机无法利用书本来解决问题，原因是计算机无法利用书本来解决问题，原因是计算机无法理解书本的内容。要理解文是计算机无法理解书本的内容。要理解文本就必须

32、分析句子的结构，即分清楚主语、本就必须分析句子的结构，即分清楚主语、谓语、宾语的含义，这项工作极其复杂。谓语、宾语的含义，这项工作极其复杂。 自然语言理解是计算机的难题。自然语言理解是计算机的难题。64逻辑运算逻辑运算(2) 逻辑运算逻辑运算 (1) 关系的比较运算关系的比较运算 65逻辑运算的简化逻辑运算的简化逻辑运算简化成：逻辑运算简化成：、1、 化简为化简为、 pq化为化为pq2、在在或或中中保留一个保留一个 (1)谓词公式中保留谓词公式中保留 (2)专家系统中保留专家系统中保留 66谓词逻辑谓词逻辑用谓词公式表示文本内容用谓词公式表示文本内容。例：每个储蓄的人都获得利息。例：每个储蓄的

33、人都获得利息。表示成表示成谓词公式谓词公式为：为：其中：其中：x表示人表示人，y表示钱表示钱，S()表示储蓄，表示储蓄，M()表示有钱，表示有钱，I()表示利息，表示利息，E()表示获得表示获得。()( ( , )( )()( ( )( , )xy S x yM yy I yE x y 67谓词公式化简谓词公式化简把谓词公式化简成只含把谓词公式化简成只含的子句的子句。1、消去消去：、2、把谓词公式化为把谓词公式化为合取范式合取范式。 如：如：(AB) (CD)3、分解合取范式为分解合取范式为只含只含的子句的子句。 子句为子句为：AB、 CD 68谓词公式的子句谓词公式的子句上面谓词公式的子句为

34、：上面谓词公式的子句为：( , )( )( ( )S x yM yI f x ( , ) ( )( , ( )S x yM yE x f x（1）（2） 69谓词逻辑的推理：归结原理谓词逻辑的推理：归结原理(反证法反证法)利用利用前提谓词公式前提谓词公式证明证明结论谓词公式结论谓词公式：(1)把前提谓词公式化简成子句。把前提谓词公式化简成子句。(2)把结论谓词公式把结论谓词公式取非后取非后，化简成子句。，化简成子句。(3)归结时，消去二个子句中正、负谓词后，归结时，消去二个子句中正、负谓词后，合并为一个子句。合并为一个子句。(4)归结的最后为空子句归结的最后为空子句(产生矛盾产生矛盾)，就证，

35、就证明了结论谓词公式的正确性！明了结论谓词公式的正确性！举例：从公理集：证明结果 。（1）把公理集转换成子句型 n这样子句集为：（2）证明命题的非为tqtsrqpp,)( ,)(,()pqrpqr()stqqtqs，tqtqsrqpp,rr（3）归结过程 最后得到空语句，是矛盾的，故可得出结论：从公理集中可以推出 。rqp rqpqt qpttr722、专家系统、专家系统这里要说明的是，对规则知识的逆向推理这里要说明的是，对规则知识的逆向推理中，并没有将所有的规则都连接成一棵中，并没有将所有的规则都连接成一棵知识推理树，进行深度优先搜索。知识推理树，进行深度优先搜索。利用规则栈，反复地搜索知识

36、库中的知识，利用规则栈，反复地搜索知识库中的知识，通过知识的进栈和出栈，达到推理树的通过知识的进栈和出栈，达到推理树的深度优先搜索。为什么要这样做？深度优先搜索。为什么要这样做？73利用规则栈推理的理由利用规则栈推理的理由（1）将规则知识连接成知识推理树并不好做，）将规则知识连接成知识推理树并不好做，因为树的分枝个数是不固定形式的，用指针因为树的分枝个数是不固定形式的，用指针链表难于设计；链表难于设计；（2）在规则栈中从栈顶规则知识找到和它连）在规则栈中从栈顶规则知识找到和它连接的知识，需要在知识库中从头到尾搜索一接的知识，需要在知识库中从头到尾搜索一遍知识库，才能找到所要的知识。遍知识库，才

37、能找到所要的知识。 74知识推理是对知识的多次反复搜索知识推理是对知识的多次反复搜索 例：有如下规则集和可信度：例：有如下规则集和可信度：R1：ABCG CF(0.8）R2：DEACF(0.7）R3：JKBCF(0.8）R4：PQCCF(0.9）R5：F（RS）D CF(0.6） 已知事实及可信度：已知事实及可信度：F(0.4)，R(0.5)，S(0.6)，E(n)，J(0.4)，K(0.6)，P(n)，Q(0.4)。 对目标对目标G进行推理求解。进行推理求解。75便利人理解的知识树便利人理解的知识树GCBAPKJEDQSRF0.80.90.90.80.70.70.60.6(0.4)(0.6)

38、(0)(0.4)(0.6)(0)(0.4)(0.5)76计算机中用规则栈推理计算机中用规则栈推理在计算机中采用规则栈，反复搜索知识库，规在计算机中采用规则栈，反复搜索知识库，规则的进栈和退栈来实现知识树的深度优先搜索。则的进栈和退栈来实现知识树的深度优先搜索。77 这种反复搜索知识库中的知识，计算机程序这种反复搜索知识库中的知识，计算机程序利用循环就能完成。利用循环就能完成。 这是用耗费计算机的计算时间（反复搜索知这是用耗费计算机的计算时间（反复搜索知识库）来完成知识的推理。识库）来完成知识的推理。78知识库中搜索找到所要的知识，也是一个知识库中搜索找到所要的知识，也是一个“比较比较”操作。操

39、作。可见，可见，“比较比较”操作对于规则知识的推理操作对于规则知识的推理和谓词推理的归结都是基础。可以归纳和谓词推理的归结都是基础。可以归纳出，出，“比较比较”操作是符号处理的基础。操作是符号处理的基础。798.1.5 软件软件进化规律进化规律（一）计算机的原始本能（一）计算机的原始本能（二）计算机的优势和不足（二）计算机的优势和不足（三）复杂问题的解决途径（三）复杂问题的解决途径（四）问题化解方法（四）问题化解方法（五）利用计算机的优势（五）利用计算机的优势 80（一）计算机的原始本能（一）计算机的原始本能1、数值计算的加法、数值计算的加法 任何复杂的运算只要能化简单任何复杂的运算只要能化简

40、单算术运算（加、减、算术运算（加、减、乘、除）乘、除），它就能在计算机中实现。，它就能在计算机中实现。2、二值数据、二值数据 所有的所有的数值计算数值计算均用二进制数据进行计算。均用二进制数据进行计算。 任何媒体只要能用二值数据表示，它就能在计算机任何媒体只要能用二值数据表示，它就能在计算机中中存储和处理存储和处理。这是计算机存储的基础。这是计算机存储的基础。 813、 “比较比较”操作操作 计算机程序的计算机程序的顺序、选择、循环顺序、选择、循环结构的运行基结构的运行基础是础是“比较比较”操作。操作。 计算机应用于数值计算和非数值计算（计算机应用于数值计算和非数值计算（数据处数据处理（数据库

41、应用）和知识处理理（数据库应用）和知识处理）等，它们的）等，它们的运行基础仍然是运行基础仍然是“比较比较”操作。操作。 82在在数据处理（数据库应用）数据处理（数据库应用）中，主要操作是中，主要操作是查查询、增加、删除、修改询、增加、删除、修改，其操作的核心也是，其操作的核心也是“比较比较”操作。操作。在在知识处理知识处理中，主要操作是中，主要操作是对知识库的搜索和对知识库的搜索和匹配匹配，其操作的核心也是，其操作的核心也是“比较比较”操作。操作。83“比较比较”操作操作:数值数值的比较是大小的比较，的比较是大小的比较，符号符号的比较在于是否相同。的比较在于是否相同。84（二）计算机的优势和不

42、足（二）计算机的优势和不足1、计算机的优势、计算机的优势（1）计算机的存储量很大）计算机的存储量很大（2）计算机的计算速度很快）计算机的计算速度很快852. 计算机的缺点计算机的缺点（1）计算机不能做随机的跳转（程序无计算机不能做随机的跳转（程序无法完成），只能机械地顺序的执行。法完成），只能机械地顺序的执行。（2）计算机不能对的结点按指数增长的）计算机不能对的结点按指数增长的大数量搜索（计算机运行时间太长、跟大数量搜索（计算机运行时间太长、跟不上需求）。不上需求）。 86（三）复杂问题的解决途径（三）复杂问题的解决途径复杂问题求解复杂问题求解 = 计算机的本能计算机的本能 + 问题化解方法问

43、题化解方法87（四）问题化解方法（四）问题化解方法1复杂问题的化解原则复杂问题的化解原则2表达式的化解原则表达式的化解原则3. 采用间接运算方法采用间接运算方法4. 有效使用标准程序工具有效使用标准程序工具5. 多资源组合形成解决问题的方案多资源组合形成解决问题的方案881复杂问题的化解原则复杂问题的化解原则(1)所有的所有的复杂数值运算复杂数值运算经过化简都经过化简都回归到回归到 “ ”(2)所有的所有的复杂程序结构复杂程序结构都用都用“顺序、选择、循环顺序、选择、循环”三三种基本结构的嵌套组合来完成。种基本结构的嵌套组合来完成。(3)充分利用大量的充分利用大量的存储空间存储空间和计算机的和

44、计算机的快速运算快速运算，即，即把复杂问题在空间布局上细化（如二值化表示、未知把复杂问题在空间布局上细化（如二值化表示、未知数结点增加），或使计算重复化（如迭代、搜索），数结点增加），或使计算重复化（如迭代、搜索），即充分发挥计算机的优势。即充分发挥计算机的优势。 89（1）改变算术运算的）改变算术运算的“先乘除、后加减，括先乘除、后加减，括号优先号优先”原则，成为顺序关系。原则，成为顺序关系。 把表达式（中缀）变成逆波兰式（后把表达式（中缀）变成逆波兰式（后缀），例如：缀），例如： a (b+c) a b c + 2表达式的化解原则表达式的化解原则90（2）改变微分运算中，对表达式中运算符求

45、微分）改变微分运算中，对表达式中运算符求微分的顺序是先低级（的顺序是先低级（+、-）后高级（）后高级（、）的）的原则，成为顺序关系。原则，成为顺序关系。 把表达式（中缀）变成波兰式（前缀），例把表达式（中缀）变成波兰式（前缀），例如：如： a (b+c) a + b c 91波兰记法波兰记法1951年波兰逻辑学家年波兰逻辑学家 J.Lukasiewicz 提出提出了逻辑运算无括号的记法：了逻辑运算无括号的记法： 1、前缀表达式、前缀表达式-波兰式波兰式 2、后缀表达式、后缀表达式-逆波兰式逆波兰式923. 采用间接运算方法采用间接运算方法 （1） 专家系统工具的研制专家系统工具的研制在知识库还

46、是空时，只要规定知识的结构在知识库还是空时，只要规定知识的结构形式，就可以编制推理机程序。形式，就可以编制推理机程序。推理机程序是对知识结构进行操作，包括推理机程序是对知识结构进行操作，包括对知识的搜索、进栈、退栈、提问、解对知识的搜索、进栈、退栈、提问、解释等。释等。编制推理机程序就是采用间接运算的方法。编制推理机程序就是采用间接运算的方法。93 （2） 遗传算法遗传算法 遗传算法是对个体编码的操作，而不是对参遗传算法是对个体编码的操作，而不是对参数本身的操作。数本身的操作。 这是重要特点。这也是典型的这是重要特点。这也是典型的间接运算间接运算。94（3）解决方程中随机求解问题解决方程中随机求解问题例如：运输问题的位势方程求解是随机求解过例如：运输问题的位势方程求解是随机求解过程程位势方程如下：位势方程如下： c1d47，c2d22，c2d46 c3d19，c3d34，c3d48 给定给定 c10 ，求解其它的，求解其它的ci 和和 dj95位势方程（位势方程（cidjDij）放在解线性表中，并设）放在解线性表中，并设计两个求解表，计两个求解表，c表和表和d表表，其中，其中ct和和dt标志位，标志位，0表示未求出，表示未求出，1表示巳求出。表示巳求出。232133ci234441djijDij2467890cict（i）100djdt（j）000096