离散数学建模.doc
《离散数学建模.doc》由会员分享,可在线阅读,更多相关《离散数学建模.doc(12页珍藏版)》请在咨信网上搜索。
1、离散建模专 业计算机科学与技术班 级 姓 名 学 号授课教师 二 O一七 年 十二 月离散建模就是离散数学与计算机科学技术及T技术应用间得联系桥梁。也就是学习离散数学得根本目得。它有两部分内容组成: 1、离散建模概念与方法 2、离散建模应用实例 一、离散建模概念与方法 、离散建模概念 在客观世界中往往需要有许多问题等待人们去解决。而解决得方法很多,最为常见得方法就是将客观世界中得问题域抽象成一种形式化得数学表示称数学模型,从而将对问题域得求解变成为对数学表示式得求解。而由于人们对数学得研究已有数千年历史,并已形成了一整套行之有效得对数学求解得理论与方法,因此用这种数学方法去解决实际问题可以取得
2、事倍功半得作用。而采用这种方法得关键之处就是数学模型得建立,它称为数学建模,而当这种数学模型就是建立在有限集或可列集之上时,此种模型得建立称离散建模。 、2、离散建模方法 (1)两个世界理论 在离散建模中有两个世界,一个就是现实世界另一个就是离散世界。现实世界就是问题域产生得世界,离散世界则就是一种数学世界,它有三个特性: 离散世界采用离散数学语言,该语言具有简洁性且表达力丰富。 离散世界所表示得就是一种抽象符号,它就是一种形式化符号体系。 离散世界中得环境简单,它在离散建模时设立,可以屏蔽大量无关信息对问题求解得干扰. 为求解问题须将问题域转换成离散模型,然后对离散模型求解,再逆向转换成现实
3、世界中得解、 (2)两个世界得转换 在离散建模方法中需要构作两种转换,即由现实世界到离散世界得转换以及由离散世界到现实世界得逆转换,而其中第一种转换尤为重要,这种转换我们一般即称之为离散建模。 下面对两种转换作介绍: 现实世界到离散世界得转换 该转换又称离散建模或简称转换.这种转换就是离散建模方法得核心.它实际上就是将现实世界中得问题转换成离散世界中得离散模型。这种过程就是将问题域中问题采取屏蔽语义、简化环境、强化关系所形成得一种抽象化、形式化过程,在转换时所要采用下面几种手段: 、选取一种离散语言,亦即就是选择一个离散数学学科门类,(如图论,代数系统,数理逻辑及关系等,也可以选择其中得一些子
4、门类如图论中得树,代数系统中得群论等等),以此学科得符号体系作为一种形式语言称离散语言。 从问题域中确定离散模型得基本对象集合。 从问题域中确定离散模型得静态结构、动态行为以及约束规则。 用离散语言描述这些集合、结构,行为与规则并组成离散模型。 在转换过程中要注意如下几点: 所选用得离散语言并不就是唯一得,有时可以有多种选择。 所建得离散模型有时可能与传统得数学结构不完全一致,此时须构造新得数学结构以适应建模得需要. 问题域中得环境与平台一般可用离散模型中得约束规则实现。 、从离散世界到现实世界得转换 该转换就是一种语义化得转换,它就是一种逆向转换,因此又称逆转换,在该转换中就是将离散模型得解
5、转换成问题域中得解。由于离散世界中解得形式就是一种抽象得形式化符号体系,没有任何语义,只有赋予问题域中语义后才成为问题域中得解。两个世界理论与两个世界转换构成了完整得离散建模方法,它可以用下面得图表示。 而离散建模方法得整个过程可以用下面几个步骤表示: 在现实世界中给出问题域; 将问题域抽象成离散模型; 离散模型求解; 解得语义化; 问题域得解。 、离散建模得步骤 在离散建模实际操作中须有若干个步骤得操作过程,它们就是: 需求描述-问题域形成; 离散模型形成; 离散模型检验与修改; 离散模型求解; 解得语义化及问题域解得获得。 二 、 离散建模应用实例 1、需求描述 死锁检测为操作系统中死锁现
6、象出现提供实时报警信号。 操作系统就是管理计算机资源,协调计算机用户与资源间得关系,为用户在计算机中顺利运行提供支撑得一种软件系统.而死锁现象则就是用户间为争夺资源而产生得一种矛盾,因此及时发现矛盾及化解矛盾就是操作系统重要职能之一。在操作系统中有两种重要得注视目标,它们就是“资源”与“进程”: (1)资源:操作系统就是管理计算机中资源得机构,而计算机中得资源包括有CPU资源,内存资源,外部设备资源(如打印机等),通道资源等多种。 (2)进程:在一台计算机中往往可以运行多个程序,而一般运行得程序称为进程。在资源与进程之间存在着紧密得关联,其中主要得关联就是:进程需要资源,只有有了充足得资源,进
7、程才能运行. 在一般情况下,进程在运行前需申请资源,只有获得资源后才能运行,在运行过程中还不断申请资源以获得继续运行得权力,同时也不断释放资源,使资源能得以充分利用;而当进程所申请得资源无法得到时(即表示此资源被它进程所占有),它必须等待,直到它进程对该资源使用完毕并释放后此进程才能获得该资源并继续运行直至进程结束.因此,进程与资源得关系就是一种动态关系,其演化过程可以用下面得图表示之. 而死锁得产生则就是进程演化中得一种特殊现象。如进程甲占有资源同时又申请资源,与此同时进程乙占有资源同时又申请资源A,此时两进程都无法申请到所需资源,因此只能等待,而等待就是无期限得,因而称为死锁。推而广之,对
8、多个进程与多个资源可能还会出现循环等待得现象,这就就是一般意义上得死锁。 2、离散建模及模型建立 (1)选择一种离散语言:根据问题域描述,该项死锁检测主要研究资源间得一种特殊关系,因此用关系或图论较为合适,而考虑到图得方法结构性好,直观性强,因而以图论作为建模工具较为合理。 (2)确定研究对象:在离散建模中,操作系统得基本研究对象集合为资源集合与进程集合,设有n个资源与个进程,它们可表示为:资源集合:R=,2,,Rn进程集合:PP1,P2,Pm (3)资源间得关系:进程P已占有资源i且申请资源Rj并处等待中,可用有序偶(i,R)表示。而它们得全体则构成一个关系,称资源申请关系S。 ()模型得建
9、立:以R为结点以为边可以构成一个有向图G=(,)。它组成了进程资源申请得图模型。在这个图中得每个边均有权i,它表示申请资源得进程。 3、模型求解 在问题域中死锁检验得解就是资源循环等待,而在图论模型中资源循环等待相当于图中存在回路。进一步,可以用可达性矩阵计算方法判别就是否出现回路,即可达性矩阵得对角线中出现有“1”。 如设可达性矩阵为如图3所示,则判别产生回路得计算公式为D=d11(+)d2(+)(+)dnn=1、 、解得语义化 最后在模型中所产生得判别公式D,可将其语义化为: 当D为1时表操作系统已产生死锁; 当D为0时表操作系统未产生死锁。 在例中我们有该图得可达性矩阵为: 从而有D=,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 建模
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。