离散数学建模

1、 离散建模专 业计算机科学与技术班 级 姓 名 学 号授课教师 二 O 一 七 年 十二 月离散建模是离散数学与计算机科学技术及IT技术应用间的联系桥梁。也是学习离散数学的根本目的。它有两部分内容组成: 1.离散建模概念与方法 2.离散建模应用实例 一.离散建模概念与方法 1.1离散建模概念 在客观世界中往往需要有许多问题等待人们去解决。而解决的方法很多，最为常见的方法是将客观世界中的问题域抽象成一种形式化的数学表示称数学模型，从而将对问题域的求解变成为对数学表示式的求解。而由于人们对数学的研究已有数千年历史，并已形成了一整套行之有效的对数学求解的理论与方法，因此用这种数学方法去解决实际问题可

2、以取得事倍功半的作用。而采用这种方法的关键之处是数学模型的建立，它称为数学建模，而当这种数学模型是建立在有限集或可列集之上时，此种模型的建立称离散建模。 1.2.离散建模方法 （1）两个世界理论 在离散建模中有两个世界，一个是现实世界另一个是离散世界。现实世界是问题域产生的世界，离散世界则是一种数学世界，它有三个特性： 离散世界采用离散数学语言，该语言具有简洁性且表达力丰富。 离散世界所表示的是一种抽象符号，它是一种形式化符号体系。 离散世界中的环境简单，它在离散建模时设立，可以屏蔽大量无关信息对问题求解的干扰。 为求解问题须将问题域转换成离散模型,然后对离散模型求解,再逆向转换成现实世界中的

3、解. （2）两个世界的转换 在离散建模方法中需要构作两种转换，即由现实世界到离散世界的转换以及由离散世界到现实世界的逆转换，而其中第一种转换尤为重要，这种转换我们一般即称之为离散建模。 下面对两种转换作介绍： 现实世界到离散世界的转换 该转换又称离散建模或简称转换。这种转换是离散建模方法的核心。它实际上是将现实世界中的问题转换成离散世界中的离散模型。这种过程是将问题域中问题采取屏蔽语义、简化环境、强化关系所形成的一种抽象化、形式化过程，在转换时所要采用下面几种手段： 1.选取一种离散语言，亦即是选择一个离散数学学科门类，（如图论，代数系统，数理逻辑及关系等，也可以选择其中的一些子门类如图论中的

4、树，代数系统中的群论等等），以此学科的符号体系作为一种形式语言称离散语言。 从问题域中确定离散模型的基本对象集合。 从问题域中确定离散模型的静态结构、动态行为以及约束规则。 用离散语言描述这些集合、结构，行为与规则并组成离散模型。 在转换过程中要注意如下几点： 所选用的离散语言并不是唯一的，有时可以有多种选择。 所建的离散模型有时可能与传统的数学结构不完全一致，此时须构造新的数学结构以适应建模的需要。 问题域中的环境与平台一般可用离散模型中的约束规则实现。 2.从离散世界到现实世界的转换 该转换是一种语义化的转换，它是一种逆向转换，因此又称逆转换，在该转换中是将离散模型的解转换成问题域中的解。

5、由于离散世界中解的形式是一种抽象的形式化符号体系，没有任何语义，只有赋予问题域中语义后才成为问题域中的解。两个世界理论与两个世界转换构成了完整的离散建模方法，它可以用下面的图表示。 而离散建模方法的整个过程可以用下面几个步骤表示： 在现实世界中给出问题域； 将问题域抽象成离散模型； 离散模型求解； 解的语义化； 问题域的解。 1.3.离散建模的步骤 在离散建模实际操作中须有若干个步骤的操作过程，它们是： 需求描述问题域形成； 离散模型形成； 离散模型检验与修改； 离散模型求解； 解的语义化及问题域解的获得。 二 . 离散建模应用实例 1.需求描述 死锁检测为操作系统中死锁现象出现提供实时报警信

6、号。 操作系统是管理计算机资源，协调计算机用户与资源间的关系，为用户在计算机中顺利运行提供支撑的一种软件系统。而死锁现象则是用户间为争夺资源而产生的一种矛盾，因此及时发现矛盾及化解矛盾是操作系统重要职能之一。在操作系统中有两种重要的注视目标，它们是“资源”与“进程”： （1）资源：操作系统是管理计算机中资源的机构，而计算机中的资源包括有CPU资源，内存资源，外部设备资源（如打印机等），通道资源等多种。 （2）进程：在一台计算机中往往可以运行多个程序，而一般运行的程序称为进程。在资源与进程之间存在着紧密的关联，其中主要的关联是：进程需要资源，只有有了充足的资源，进程才能运行。 在一般情况下，进程

7、在运行前需申请资源，只有获得资源后才能运行，在运行过程中还不断申请资源以获得继续运行的权力，同时也不断释放资源，使资源能得以充分利用；而当进程所申请的资源无法得到时（即表示此资源被它进程所占有），它必须等待，直到它进程对该资源使用完毕并释放后此进程才能获得该资源并继续运行直至进程结束。因此，进程与资源的关系是一种动态关系，其演化过程可以用下面的图1表示之。 而死锁的产生则是进程演化中的一种特殊现象。如进程甲占有资源A同时又申请资源B，与此同时进程乙占有资源B同时又申请资源A，此时两进程都无法申请到所需资源，因此只能等待，而等待是无期限的，因而称为死锁。推而广之，对多个进程与多个资源可能还会出现

8、循环等待的现象，这就是一般意义上的死锁。 2.离散建模及模型建立 （1）选择一种离散语言：根据问题域描述，该项死锁检测主要研究资源间的一种特殊关系，因此用关系或图论较为合适，而考虑到图的方法结构性好，直观性强，因而以图论作为建模工具较为合理。 （2）确定研究对象：在离散建模中，操作系统的基本研究对象集合为资源集合与进程集合，设有n个资源与m个进程，它们可表示为：资源集合：R=R1，R2，Rn进程集合：P=P1，P2，Pm （3）资源间的关系：进程P已占有资源Ri且申请资源Rj并处等待中，可用有序偶（Ri，Rj）表示。而它们的全体则构成一个关系，称资源申请关系S。 （4）模型的建立：以R为结点以

9、S为边可以构成一个有向图G=（R，S）。它组成了进程资源申请的图模型。在这个图中的每个边均有权Pi，它表示申请资源的进程。 3.模型求解 在问题域中死锁检验的解是资源循环等待，而在图论模型中资源循环等待相当于图中存在回路。进一步，可以用可达性矩阵计算方法判别是否出现回路，即可达性矩阵的对角线中出现有“1”。 如设可达性矩阵为如图3所示，则判别产生回路的计算公式为D=d11（+）d22（+）（+）dnn=1. 4.解的语义化 最后在模型中所产生的判别公式D，可将其语义化为： 当D为1时表操作系统已产生死锁； 当D为0时表操作系统未产生死锁。 在例中我们有该图的可达性矩阵为： 从而有D=1，这表明

10、在时刻t时系统产生死锁。 5. 死锁检测的离散建模特点是：（1）该离散建模所建模型简单，可计算且效果好。（2）该离散建模可以同时用图论与关系实现，但由于在图论中对回路的研究与表示都优于关系，因此用图论较为合适。（3）在该离散模型中运用图论中的通路与回路以及相应的矩阵计算方法较为方便的解决了死锁问题。 2.3数据库中关系数据模型的离散建模 1.需求描述 关系数据理论就是用关系理论研究数据模型，在这里涉及到两方面的问题，它们是： 数据模型 关系模型 （1）数据模型 数据模型是对数据存储与操纵的抽象表示。其主要内容是用于存储数据的数据结构表示以及建立在该结构上的数据操作表示。 （2）关系数据模型 关

11、系数据模型是一种以二维表的形式表示数据结构又以二维表上的数据操作为特点的数据模型。 1）首先介绍二维表。二维表又称表，它由表框架及表元组两部分组成。表框架由表名及n个命名属性列所构成。表12.1给出了一个表名为student的表框架 表1 表名为student的表框架 其中sno，sn，sd及sa分别表示属性学号、学生姓名，学生系别及学生年龄等。 在表框架中可以按行存放数据，表中每个数据称元组。元组由若干个分量组成，其每个分量对应表框架中的一个属性值，如在表框架student中可以有如下的元组： 它表示一个学生的相应信息，该学生学号为07001，姓名为张曼英，计算机系，年龄为18岁，它们分别是

12、一个元组中的四个元组分量。 一个表框架可以存储若干个元组。它们构成了一个完整的二维表。表12.2给出了二维表的例。 表2 二维表student的例 2）接下来，介绍建立在二维表上的数据操作: 查询操作 删除操作 插入操作 修改操作 关系数据模型中的基本逻辑操作共六种： 表的列指定 表的行选择 两表的合并 查询操作 删除操作 插入操作 3）关系数据模型的基本面貌： 关系数据模型是以二维表为数据结构，以元组为基本数据单位，在它的上面可以有六种基本操作。它构成了一个数据库系统的基本面貌。 3.关系数据模型离散建模之一关系代数模型 关系代数模型以关系与代数系统为工具研究关系数据模型。 （1）首先从二维

13、表讨论起，二维表实际上是元组的集合，而元组则可视为n元有序组，因此二维表是n元有序组的集合亦即二维表即是n元关系。 （2）其次，二维表上的操作即是关系的运算。二维表上的六种基本操作可对应关系的五种运算。 1）插入： RR2）删除 RR3）两表合并 R S4）列指定： Ai1, Ai2,Aim ( R )5）行选择 F（R） （3）关系代数 由关系所组成的集合A上的五种运算，它们分别是三种二元运算并，差及笛卡尔运算，以及两种一元运算投影及选择运算，且都是封闭的，从而构成一个代数系统： （A，） 该代数系统称关系代数。 （4）关系代数的运算规则 1）并运算满足结合律与交换律： R1（R2R3）=（

14、R1R2）R3 R1R2= R2R1 2）投影运算满足交换律、吸收律及归零律 当a1, a 2, an与R无关时有a1, a 2, am (R)=? a1, a 2, am（b1, b 2, bn(R)）= b1, b 2, bn（a1, a 2, am(R)） 当a1, a 2, an与R无关而b1, b 2, bm与R有关时， a1, a 2, an, b1, b 2, bmR=b1, b 2, bmR a1, a 2, am（b1, b 2, bn(R)）=a1, a 2, am (R) 3）选择运算满足交换律、串接律： F1（F2(R)）=F2（F1(R)） F1（F2(R)）=F1F

15、2(R) 4）选择与投影运算满足交换律： F（a1, a 2, am(R)）= a1, a 2, am（F（R） 5）选择对笛卡尔乘积满足分配律： F（R1R2）=FR1FR2 当F与R无关，此时有：FR= R，因此有： 若F仅涉及R1有：F（R1R2）=F（R1）R2 若F仅涉及R2有：F（R1R2）= R1F（R2） 若F= F1F2，而F1仅涉及R1；F2仅涉及R2，有： F（R1R2）=F1（R1）F2（R2） 6）投影对笛卡尔乘积满足分配律： a1, a 2, an（R1R2）= a1, a 2, anR1a1, a 2, an R2 （5）关系代数模型 关系代数及其七组运算规则组成

16、了关系代数模型。 3.关系代数模型的求解 关系代数模型可以用于数据库中的数据结构表示，数据操作表示及其优化，最后并可构造规范化表达式。 （1）数据结构表示 可以用n元关系表示关系模型中的二维表。 例:有如表3所示的学生数据库由学生、选课及课程三张二维表组成，它可以用下面的三个关系表示之。 S=（S101，John，CS，18），（S102，Aris，CS，19），（S103，Mary，CS，20） S C=（S101，C01，4），（S101，C02，5），（S102，C03，4），（S103，C01，3），（S103，C03，5） C=（C01，DB，C02），（C02，OS，C02），（C

17、03，AI，C02） 表3 学生数据库 （2）数据操作表示 可以用关系代数表达式表示数据操作。 例: 对学生数据库用关系代数公式表示查询及增、删、改操作如下： 查询学生年龄大于18岁的学生姓名：sn(sa18(S)）查询John所修读的课程的课程号：cnoSn=Jhon（sSC）在选课表中增加学生S102 选读C03分数为5分的元组。SC（S102，C03，5） （3）数据操作表示优化 例: 优化下面二式： sn(sa18（sSC）= sn(sa18(S) SC）= sn(sa18(S) sn（SC）)= sn(sa18(S) sno，cno（Sd=CSpcno=C01（sd， sno(S)c

18、no，pcno(C)）= sno，cno（Sd=CS（sd，sno(S)）（pcno=C01（cno，pcno(C)）= sno（Sd=CS（sd，sno(S)）cno（pcno=C01（cno，pcno(C)）= sno（sd，sno（Sd=CS(S)）（cno（cno，pcno（pcno=C01(C)）= sno（Sd=CS(S)）cno（pcno=C01(C)） （4）查询操作的规范化表示 可以用前面六组运算规则将任一查询表达式规范化为下面的形式： a1, a 2, anF（R1R2Rm） 这个规范化形为数据库查询语言SQL提供了表示上的理论基础。在SQL中一个查询语句由标准的三个子句组成，它们是选择子句SELECT，范围子句FROM及条件子句WHERE，它们分别表示投影运算、选择运算以及笛卡儿乘积，其具体表示形式为： SELECT a1, a 2, an FROM R1,