离散数学建模.doc

离散建模
专 　业
计算机科学与技术
班 级

姓 　名

学　 　 号

授课教师

　 二 O　一　七 年 十二 月
离散建模就是离散数学与计算机科学技术及ＩT技术应用间得联系桥梁。也就是学习离散数学得根本目得。
它有两部分内容组成：
　1、离散建模概念与方法
　 　 2、离散建模应用实例
　一、离散建模概念与方法
　 １、１离散建模概念
　 在客观世界中往往需要有许多问题等待人们去解决。而解决得方法很多,最为常见得方法就是将客观世界中得问题域抽象成一种形式化得数学表示称数学模型，从而将对问题域得求解变成为对数学表示式得求解。而由于人们对数学得研究已有数千年历史,并已形成了一整套行之有效得对数学求解得理论与方法，因此用这种数学方法去解决实际问题可以取得事倍功半得作用。而采用这种方法得关键之处就是数学模型得建立，它称为数学建模，而当这种数学模型就是建立在有限集或可列集之上时,此种模型得建立称离散建模。
　　 １、2、离散建模方法
（1）两个世界理论
　 在离散建模中有两个世界，一个就是现实世界另一个就是离散世界。现实世界就是问题域产生得世界,离散世界则就是一种数学世界，它有三个特性：
　 离散世界采用离散数学语言,该语言具有简洁性且表达力丰富。
　　 　 离散世界所表示得就是一种抽象符号，它就是一种形式化符号体系。
　 　　 离散世界中得环境简单,它在离散建模时设立，可以屏蔽大量无关信息对问题求解得干扰.
　 为求解问题须将问题域转换成离散模型，然后对离散模型求解,再逆向转换成现实世界中得解、
　 （2)两个世界得转换
　 在离散建模方法中需要构作两种转换，即由现实世界到离散世界得转换以及由离散世界到现实世界得逆转换，而其中第一种转换尤为重要,这种转换我们一般即称之为离散建模。
　　　下面对两种转换作介绍： 　 　
　 现实世界到离散世界得转换
该转换又称离散建模或简称转换.这种转换就是离散建模方法得核心.它实际上就是将现实世界中得问题转换成离散世界中得离散模型。这种过程就是将问题域中问题采取屏蔽语义、简化环境、强化关系所形成得一种抽象化、形式化过程,在转换时所要采用下面几种手段:
　１、选取一种离散语言，亦即就是选择一个离散数学学科门类，(如图论，代数系统，数理逻辑及关系等,也可以选择其中得一些子门类如图论中得树，代数系统中得群论等等）,以此学科得符号体系作为一种形式语言称离散语言。
　　　从问题域中确定离散模型得基本对象集合。
　 从问题域中确定离散模型得静态结构、动态行为以及约束规则。
用离散语言描述这些集合、结构，行为与规则并组成离散模型。
　 　 在转换过程中要注意如下几点：
　所选用得离散语言并不就是唯一得，有时可以有多种选择。
　 　所建得离散模型有时可能与传统得数学结构不完全一致,此时须构造新得数学结构以适应建模得需要.
　 　 问题域中得环境与平台一般可用离散模型中得约束规则实现。
　２、从离散世界到现实世界得转换
　　该转换就是一种语义化得转换，它就是一种逆向转换,因此又称逆转换，在该转换中就是将离散模型得解转换成问题域中得解。由于离散世界中解得形式就是一种抽象得形式化符号体系，没有任何语义,只有赋予问题域中语义后才成为问题域中得解。两个世界理论与两个世界转换构成了完整得离散建模方法，它可以用下面得图表示。

而离散建模方法得整个过程可以用下面几个步骤表示:
　 在现实世界中给出问题域；
将问题域抽象成离散模型；
　 离散模型求解；
解得语义化；
　 　 问题域得解。
　 １、３、离散建模得步骤
　 　 在离散建模实际操作中须有若干个步骤得操作过程，它们就是：
　 需求描述-问题域形成;
离散模型形成；
　 离散模型检验与修改；
离散模型求解;
　 　 解得语义化及问题域解得获得。
　 　 二 、 离散建模应用实例
　 　1、需求描述
　　 死锁检测为操作系统中死锁现象出现提供实时报警信号。
操作系统就是管理计算机资源，协调计算机用户与资源间得关系,为用户在计算机中顺利运行提供支撑得一种软件系统.而死锁现象则就是用户间为争夺资源而产生得一种矛盾，因此及时发现矛盾及化解矛盾就是操作系统重要职能之一。在操作系统中有两种重要得注视目标,它们就是“资源”与“进程”：
　 （1）资源:操作系统就是管理计算机中资源得机构,而计算机中得资源包括有CPU资源,内存资源，外部设备资源（如打印机等），通道资源等多种。
　 （2）进程：在一台计算机中往往可以运行多个程序，而一般运行得程序称为进程。在资源与进程之间存在着紧密得关联,其中主要得关联就是:进程需要资源,只有有了充足得资源，进程才能运行.
在一般情况下，进程在运行前需申请资源,只有获得资源后才能运行，在运行过程中还不断申请资源以获得继续运行得权力，同时也不断释放资源,使资源能得以充分利用;而当进程所申请得资源无法得到时（即表示此资源被它进程所占有）,它必须等待，直到它进程对该资源使用完毕并释放后此进程才能获得该资源并继续运行直至进程结束.因此,进程与资源得关系就是一种动态关系,其演化过程可以用下面得图１表示之.

　而死锁得产生则就是进程演化中得一种特殊现象。如进程甲占有资源Ａ同时又申请资源Ｂ，与此同时进程乙占有资源Ｂ同时又申请资源A，此时两进程都无法申请到所需资源,因此只能等待，而等待就是无期限得,因而称为死锁。推而广之，对多个进程与多个资源可能还会出现循环等待得现象,这就就是一般意义上得死锁。
　 　 2、离散建模及模型建立
（1）选择一种离散语言:根据问题域描述,该项死锁检测主要研究资源间得一种特殊关系，因此用关系或图论较为合适,而考虑到图得方法结构性好，直观性强,因而以图论作为建模工具较为合理。
　 　（2）确定研究对象：在离散建模中，操作系统得基本研究对象集合为资源集合与进程集合,设有n个资源与ｍ个进程，它们可表示为：
资源集合：R=｛Ｒ１,Ｒ2，…,Rn｝
进程集合:P＝｛P1，P2，…，Pm}
　 　（3)资源间得关系:进程P已占有资源Ｒi且申请资源Rj并处等待中，可用有序偶(Ｒi,Rｊ)表示。而它们得全体则构成一个关系，称资源申请关系S。
　(４）模型得建立:以R为结点以Ｓ为边可以构成一个有向图G=(Ｒ，Ｓ)。它组成了进程资源申请得图模型。在这个图中得每个边均有权Ｐi，它表示申请资源得进程。
3、模型求解
在问题域中死锁检验得解就是资源循环等待,而在图论模型中资源循环等待相当于图中存在回路。进一步,可以用可达性矩阵计算方法判别就是否出现回路,即可达性矩阵得对角线中出现有“1”。
　 如设可达性矩阵为如图3所示,则判别产生回路得计算公式为D’=d11（+）d2２(+)…(+）dnn=1、

４、解得语义化
　 最后在模型中所产生得判别公式D’,可将其语义化为：
　 当D'为1时表操作系统已产生死锁；
　当D’为0时表操作系统未产生死锁。
　 　在例中我们有该图得可达性矩阵为：

　从而有D’=１，这表明在时刻t时系统产生死锁.
　 5、 　死锁检测得离散建模特点就是：
（1)该离散建模所建模型简单，可计算且效果好。
（2）该离散建模可以同时用图论与关系实现,但由于在图论中对回路得研究与表示都优于关系,因此用图论较为合适。
(3）在该离散模型中运用图论中得通路与回路以及相应得矩阵计算方法较为方便得解决了死锁问题。
　 ２、3数据库中关系数据模型得离散建模
1、需求描述
关系数据理论就就是用关系理论研究数据模型,在这里涉及到两方面得问题，它们就是:
　数据模型
　 关系模型
(1)数据模型
　数据模型就是对数据存储与操纵得抽象表示。其主要内容就是用于存储数据得数据结构表示以及建立在该结构上得数据操作表示。
　（2）关系数据模型
　关系数据模型就是一种以二维表得形式表示数据结构又以二维表上得数据操作为特点得数据模型。
1)首先介绍二维表。二维表又称表，它由表框架及表元组两部分组成.表框架由表名及n个命名属性列所构成.表1２、1给出了一个表名为stuｄent得表框架

　 　 　 　 　 　表1 表名为stuｄenｔ得表框架
其中sno，sn,sd及sa分别表示属性学号、学生姓名,学生系别及学生年龄等。
　　 在表框架中可以按行存放数据，表中每个数据称元组。元组由若干个分量组成,其每个分量对应表框架中得一个属性值,如在表框架sｔｕdｅｎt中可以有如下得元组:
　 它表示一个学生得相应信息，该学生学号为07001，姓名为张曼英,计算机系,年龄为１８岁，它们分别就是一个元组中得四个元组分量。
　　 一个表框架可以存储若干个元组.它们构成了一个完整得二维表。表１２、2给出了二维表得例.

　 　 　　 表2 　　二维表stuｄent得例
2）接下来,介绍建立在二维表上得数据操作：
　查询操作　
　 删除操作
　　 插入操作
　 　　修改操作
关系数据模型中得基本逻辑操作共六种：
表得列指定
表得行选择
两表得合并
查询操作
删除操作
　　 插入操作 　 　
3)关系数据模型得基本面貌：
　 关系数据模型就是以二维表为数据结构，以元组为基本数据单位,在它得上面可以有六种基本操作。它构成了一个数据库系统得基本面貌。
3、关系数据模型离散建模之一-关系代数模型
　关系代数模型以关系与代数系统为工具研究关系数据模型。
（1)首先从二维表讨论起，二维表实际上就是元组得集合，而元组则可视为n元有序组，因此二维表就是n元有序组得集合亦即二维表即就是n元关系。
(2)其次，二维表上得操作即就是关系得运算。二维表上得六种基本操作可对应关系得五种运算.　
1）插入:
Ｒ∪R’
2）删除
R－R’
3)两表合并
R× S
4)列指定:
∏Ai1, Aｉ2,…,Aｉm　（ R ）
5）行选择
σF（R）
(3)关系代数
　 由关系所组成得集合Ａ上得五种运算,它们分别就是三种二元运算—并，差及笛卡尔运算，以及两种一元运算-投影及选择运算,且都就是封闭得，从而构成一个代数系统：
　 　 　　　（A,∏,σ，∪，—,×)
　 该代数系统称关系代数。
　 　 　（4)关系代数得运算规则
　1)并运算满足结合律与交换律:
　 R1∪（R２∪R3）=（R1∪Ｒ2）∪R３
　　 R１∪R2= R2∪R１
　 ２）投影运算满足交换律、吸收律及归零律
　当a1, a ２，…， ａｎ与Ｒ无关时有∏a1，　a 2,…, am （R）＝?
∏a1, a 2,…, am（∏ｂ1, ｂ 2,…, bn(R)）=
∏b１， b ２,…， bn（∏a1，　a 2,…, aｍ（Ｒ))
　当ａ1， a 2，…, ａn与Ｒ无关而b１, b ２，…,　bm与R有关时,　
∏a1, a 2,…, ａｎ， ｂ1, b 2，…， ｂｍR=∏ｂ１， b　2,…， bmR
　∏a１, a ２，…, am（∏b1, b　2，…, bｎ(R））=∏ａ1, ａ 2，…，　am (Ｒ）
3）选择运算满足交换律、串接律:
　σF１(σF2（R）)=σF2(σF1(R）)
σF1（σF２（R)）=σF１∧F2（Ｒ）
4）选择与投影运算满足交换律：
　 σＦ(∏a1，　ａ 2，…, aｍ（R））=
　 ∏ａ1， a 2，…，　aｍ（σＦ(R）)
5)选择对笛卡尔乘积满足分配律:
　 σF(Ｒ１×R２）=σFR1×σＦR２
当F与R无关,此时有：σＦR= R，因此有:
若F仅涉及R1有：σF(Ｒ1×Ｒ2)=σF（R1）×R2
若F仅涉及R２有:σF(Ｒ1×R２)=　R１×σＦ（Ｒ２）
　若F= F1∧F2，而F１仅涉及R1；Ｆ2仅涉及R2,有:　 σF(R1×R2)=σF1（Ｒ1）×σF2（R２)
　 　6）投影对笛卡尔乘积满足分配律:
　 ∏ａ1， ａ　2，…， ａn（Ｒ１×R2)=
　　 ∏a1, a　2,…,　aｎＲ1×∏ａ１， a 2,…， ａn R2
　(５)关系代数模型
　 关系代数及其七组运算规则组成了关系代数模型。
　　 3、关系代数模型得求解
　　 关系代数模型可以用于数据库中得数据结构表示，数据操作表示及其优化,最后并可构造规范化表达式。
　　（１)数据结构表示
　 可以用n元关系表示关系模型中得二维表。
　 例：有如表３所示得学生数据库由学生、选课及课程三张二维表组成,它可以用下面得三个关系表示之.
　　S={(S10１，Ｊoｈn，CS，１8）,(S1０2，Aris,ＣＳ,19)，(Ｓ103,Maｒy,CＳ,20)｝
　 　S Ｃ={（Ｓ101，C0１，4），(S10１，C０２,5),(S１02，C０3,4),(S１０3，C01,3),(S10３，C０3,5）｝
C={(C01,DB，C02)，（Ｃ02,OＳ,C０2)，(C０3，AI,C02）}

　 　　 　 　 　 　 表3　　 学生数据库
　(2）数据操作表示
　 可以用关系代数表达式表示数据操作。
例:　对学生数据库用关系代数公式表示查询及增、删、改操作如下:
查询学生年龄大于18岁得学生姓名：
∏sn(σsa＞１8（S）)
查询Joｈn所修读得课程得课程号：
∏cnｏσSn＝Ｊｈon（s×SＣ)
在选课表中增加学生Ｓ102 选读C0３分数为５分得元组。
SC∪｛(Ｓ１02，C０3，５）｝
　 　（３）数据操作表示优化
　 　 例： 优化下面二式:
　 ∏sn（σsa＞18（ｓ×ＳC）=
　∏sｎ（σsa＞１8(S) ×SC)＝
　 ∏ｓn(σsａ＞18（Ｓ）　×∏sn（ＳＣ）)=
　 ∏sn(σsa＞１８（S)）
　 ∏ｓｎｏ,cｎo（σＳｄ=CS∧pｃno=C01(∏ｓｄ, sno（S)×∏cno,pcno(C)））= ∏sno，ｃno(σＳd=CＳ(∏ｓd,sno(S)）)×（σpcno=Ｃ０1（∏cｎo,ｐcnｏ（C)））=
∏ｓno（σSｄ=CＳ（∏sd,sno（Ｓ））×∏cno(σpcno=C01（∏ｃnｏ，pcno（C)）)＝
　 ∏ｓno（∏sd,ｓno（σSd=CS(S）)）×（∏cno（∏ｃｎo，ｐcnｏ（σpcno=C01(Ｃ）))=
　 　 ∏snｏ(σＳｄ=CS(S）)×∏cnｏ(σpcno=Ｃ0１（C））
（4)查询操作得规范化表示
可以用前面六组运算规则将任一查询表达式规范化为下面得形式：
　　∏a１，　ａ ２，…, anσＦ（Ｒ１×R2×…×Rm）
　 这个规范化形为数据库查询语言ＳQL提供了表示上得理论基础。在SQL中一个查询语句由标准得三个子句组成，它们就是选择子句ＳＥLECT，范围子句FROM及条件子句WHERE,它们分别表示投影运算∏、选择运算σ以及笛卡儿乘积×，其具体表示形式为：
　 　　SELＥCT　 a１， a 2，…, an
FRＯＭ R1, R2，…，　Rm
　 WHERE Ｆ
　 5、解得语义化及问题域解得获得
　 (1）离散数学中得n元关系即表示了数据库关系数据模型中得数据结构即二维表。
（2）关系运算即表示了关系数据模型中得基本数据操作。
(３)关系代数即表示了关系数据模型。
　(4）关系代数中得关系表达式即表示了关系数据模型中得多种操作表示.
（5)关系代数中得关系表达式得优化即表示了关系数据模型中操作得优化,它不但可简化表示，更主要还可以提高操作效率。
(6）关系代数中得查询规范化形式提供了标准、统一得表示形式并为SQＬ语言得设计提供了理论基础。
结束语：以上就就是数据库中关系数据模型得离散建模以及离散建模概念与方法。