離散數(shù)學(xué)建模

-.z.離散建模專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)****授課教師二O一七年十二月-.z.離散建模是離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)技術(shù)及IT技術(shù)應(yīng)用間的聯(lián)系橋梁。也是學(xué)習(xí)離散數(shù)學(xué)的根本目的。它有兩局部?jī)?nèi)容組成:1.離散建模概念與方法2.離散建模應(yīng)用實(shí)例一.離散建模概念與方法1.1離散建模概念在客觀世界中往往需要有許多問題等待人們?nèi)ソ鉀Q。而解決的方法很多，最為常見的方法是將客觀世界中的問題域抽象成一種形式化的數(shù)學(xué)表示稱數(shù)學(xué)模型，從而將對(duì)問題域的求解變成為對(duì)數(shù)學(xué)表示式的求解。而由于人們對(duì)數(shù)學(xué)的研究已有數(shù)千年歷史，并已形成了一整套行之有效的對(duì)數(shù)學(xué)求解的理論與方法，因此用這種數(shù)學(xué)方法去解決實(shí)際問題可以取得事倍功半的作用。而采用這種方法的關(guān)鍵之處是數(shù)學(xué)模型的建立，它稱為數(shù)學(xué)建模，而當(dāng)這種數(shù)學(xué)模型是建立在有限集或可列集之上時(shí)，此種模型的建立稱離散建模。1.2.離散建模方法〔1〕兩個(gè)世界理論在離散建模中有兩個(gè)世界，一個(gè)是現(xiàn)實(shí)世界另一個(gè)是離散世界?，F(xiàn)實(shí)世界是問題域產(chǎn)生的世界，離散世界則是一種數(shù)學(xué)世界，它有三個(gè)特性：離散世界采用離散數(shù)學(xué)語言，該語言具有簡(jiǎn)潔性且表達(dá)力豐富。離散世界所表示的是一種抽象符號(hào)，它是一種形式化符號(hào)體系。離散世界中的環(huán)境簡(jiǎn)單，它在離散建模時(shí)設(shè)立，可以屏蔽大量無關(guān)信息對(duì)問題求解的干擾。為求解問題須將問題域轉(zhuǎn)換成離散模型,然后對(duì)離散模型求解,再逆向轉(zhuǎn)換成現(xiàn)實(shí)世界中的解.〔2〕兩個(gè)世界的轉(zhuǎn)換在離散建模方法中需要構(gòu)作兩種轉(zhuǎn)換，即由現(xiàn)實(shí)世界到離散世界的轉(zhuǎn)換以及由離散世界到現(xiàn)實(shí)世界的逆轉(zhuǎn)換，而其中第一種轉(zhuǎn)換尤為重要，這種轉(zhuǎn)換我們一般即稱之為離散建模。下面對(duì)兩種轉(zhuǎn)換作介紹：現(xiàn)實(shí)世界到離散世界的轉(zhuǎn)換該轉(zhuǎn)換又稱離散建模或簡(jiǎn)稱轉(zhuǎn)換。這種轉(zhuǎn)換是離散建模方法的核心。它實(shí)際上是將現(xiàn)實(shí)世界中的問題轉(zhuǎn)換成離散世界中的離散模型。這種過程是將問題域中問題采取屏蔽語義、簡(jiǎn)化環(huán)境、強(qiáng)化關(guān)系所形成的一種抽象化、形式化過程，在轉(zhuǎn)換時(shí)所要采用下面幾種手段：1.選取一種離散語言，亦即是選擇一個(gè)離散數(shù)學(xué)學(xué)科門類，〔如圖論，代數(shù)系統(tǒng)，數(shù)理邏輯及關(guān)系等，也可以選擇其中的一些子門類如圖論中的樹，代數(shù)系統(tǒng)中的群論等等〕，以此學(xué)科的符號(hào)體系作為一種形式語言稱離散語言。從問題域中確定離散模型的根本對(duì)象集合。從問題域中確定離散模型的靜態(tài)構(gòu)造、動(dòng)態(tài)行為以及約束規(guī)則。用離散語言描述這些集合、構(gòu)造，行為與規(guī)則并組成離散模型。在轉(zhuǎn)換過程中要注意如下幾點(diǎn)：所選用的離散語言并不是唯一的，有時(shí)可以有多種選擇。所建的離散模型有時(shí)可能與傳統(tǒng)的數(shù)學(xué)構(gòu)造不完全一致，此時(shí)須構(gòu)造新的數(shù)學(xué)構(gòu)造以適應(yīng)建模的需要。問題域中的環(huán)境與平臺(tái)一般可用離散模型中的約束規(guī)則實(shí)現(xiàn)。2.從離散世界到現(xiàn)實(shí)世界的轉(zhuǎn)換該轉(zhuǎn)換是一種語義化的轉(zhuǎn)換，它是一種逆向轉(zhuǎn)換，因此又稱逆轉(zhuǎn)換，在該轉(zhuǎn)換中是將離散模型的解轉(zhuǎn)換成問題域中的解。由于離散世界中解的形式是一種抽象的形式化符號(hào)體系，沒有任何語義，只有賦予問題域中語義后才成為問題域中的解。兩個(gè)世界理論與兩個(gè)世界轉(zhuǎn)換構(gòu)成了完整的離散建模方法，它可以用下面的圖表示。而離散建模方法的整個(gè)過程可以用下面幾個(gè)步驟表示：在現(xiàn)實(shí)世界中給出問題域；將問題域抽象成離散模型；離散模型求解；解的語義化；問題域的解。1.3.離散建模的步驟在離散建模實(shí)際操作中須有假設(shè)干個(gè)步驟的操作過程，它們是：需求描述—問題域形成；離散模型形成；離散模型檢驗(yàn)與修改；離散模型求解；解的語義化及問題域解的獲得。二.離散建模應(yīng)用實(shí)例1.需求描述死鎖檢測(cè)為操作系統(tǒng)中死鎖現(xiàn)象出現(xiàn)提供實(shí)時(shí)報(bào)警信號(hào)。操作系統(tǒng)是管理計(jì)算機(jī)資源，協(xié)調(diào)計(jì)算機(jī)用戶與資源間的關(guān)系，為用戶在計(jì)算機(jī)中順利運(yùn)行提供支撐的一種軟件系統(tǒng)。而死鎖現(xiàn)象則是用戶間為爭(zhēng)奪資源而產(chǎn)生的一種矛盾，因此及時(shí)發(fā)現(xiàn)矛盾及化解矛盾是操作系統(tǒng)重要職能之一。在操作系統(tǒng)中有兩種重要的注視目標(biāo)，它們是"資源〞與"進(jìn)程〞：〔1〕資源：操作系統(tǒng)是管理計(jì)算機(jī)中資源的機(jī)構(gòu)，而計(jì)算機(jī)中的資源包括有CPU資源，內(nèi)存資源，外部設(shè)備資源〔如打印機(jī)等〕，通道資源等多種?！?〕進(jìn)程：在一臺(tái)計(jì)算機(jī)中往往可以運(yùn)行多個(gè)程序，而一般運(yùn)行的程序稱為進(jìn)程。在資源與進(jìn)程之間存在著嚴(yán)密的關(guān)聯(lián)，其中主要的關(guān)聯(lián)是：進(jìn)程需要資源，只有有了充足的資源，進(jìn)程才能運(yùn)行。在一般情況下，進(jìn)程在運(yùn)行前需申請(qǐng)資源，只有獲得資源后才能運(yùn)行，在運(yùn)行過程中還不斷申請(qǐng)資源以獲得繼續(xù)運(yùn)行的權(quán)力，同時(shí)也不斷釋放資源，使資源能得以充分利用；而當(dāng)進(jìn)程所申請(qǐng)的資源無法得到時(shí)〔即表示此資源被它進(jìn)程所占有〕，它必須等待，直到它進(jìn)程對(duì)該資源使用完畢并釋放后此進(jìn)程才能獲得該資源并繼續(xù)運(yùn)行直至進(jìn)程完畢。因此，進(jìn)程與資源的關(guān)系是一種動(dòng)態(tài)關(guān)系，其演化過程可以用下面的圖1表示之。而死鎖的產(chǎn)生則是進(jìn)程演化中的一種特殊現(xiàn)象。如進(jìn)程甲占有資源A同時(shí)又申請(qǐng)資源B，與此同時(shí)進(jìn)程乙占有資源B同時(shí)又申請(qǐng)資源A，此時(shí)兩進(jìn)程都無法申請(qǐng)到所需資源，因此只能等待，而等待是無期限的，因而稱為死鎖。推而廣之，對(duì)多個(gè)進(jìn)程與多個(gè)資源可能還會(huì)出現(xiàn)循環(huán)等待的現(xiàn)象，這就是一般意義上的死鎖。2.離散建模及模型建立〔1〕選擇一種離散語言：根據(jù)問題域描述，該項(xiàng)死鎖檢測(cè)主要研究資源間的一種特殊關(guān)系，因此用關(guān)系或圖論較為適宜，而考慮到圖的方法構(gòu)造性好，直觀性強(qiáng)，因而以圖論作為建模工具較為合理?！?〕確定研究對(duì)象：在離散建模中，操作系統(tǒng)的根本研究對(duì)象集合為資源集合與進(jìn)程集合，設(shè)有n個(gè)資源與m個(gè)進(jìn)程，它們可表示為：資源集合：R={R1，R2，…，Rn}進(jìn)程集合：P={P1，P2，…，Pm}〔3〕資源間的關(guān)系：進(jìn)程P已占有資源Ri且申請(qǐng)資源Rj并處等待中，可用有序偶〔Ri，Rj〕表示。而它們的全體則構(gòu)成一個(gè)關(guān)系，稱資源申請(qǐng)關(guān)系S?！?〕模型的建立：以R為結(jié)點(diǎn)以S為邊可以構(gòu)成一個(gè)有向圖G=〔R，S〕。它組成了進(jìn)程資源申請(qǐng)的圖模型。在這個(gè)圖中的每個(gè)邊均有權(quán)Pi，它表示申請(qǐng)資源的進(jìn)程。3.模型求解在問題域中死鎖檢驗(yàn)的解是資源循環(huán)等待，而在圖論模型中資源循環(huán)等待相當(dāng)于圖中存在回路。進(jìn)一步，可以用可達(dá)性矩陣計(jì)算方法判別是否出現(xiàn)回路，即可達(dá)性矩陣的對(duì)角線中出現(xiàn)有"1〞。如設(shè)可達(dá)性矩陣為如圖3所示，則判別產(chǎn)生回路的計(jì)算公式為D’=d11〔+〕d22〔+〕…〔+〕dnn=1.4.解的語義化最后在模型中所產(chǎn)生的判別公式D’，可將其語義化為：當(dāng)D’為1時(shí)表操作系統(tǒng)已產(chǎn)生死鎖；當(dāng)D’為0時(shí)表操作系統(tǒng)未產(chǎn)生死鎖。在例中我們有該圖的可達(dá)性矩陣為：從而有D’=1，這說明在時(shí)刻t時(shí)系統(tǒng)產(chǎn)生死鎖。5.死鎖檢測(cè)的離散建模特點(diǎn)是：〔1〕該離散建模所建模型簡(jiǎn)單，可計(jì)算且效果好?！?〕該離散建?？梢酝瑫r(shí)用圖論與關(guān)系實(shí)現(xiàn)，但由于在圖論中對(duì)回路的研究與表示都優(yōu)于關(guān)系，因此用圖論較為適宜?！?〕在該離散模型中運(yùn)用圖論中的通路與回路以及相應(yīng)的矩陣計(jì)算方法較為方便的解決了死鎖問題。2.3數(shù)據(jù)庫中關(guān)系數(shù)據(jù)模型的離散建模1.需求描述關(guān)系數(shù)據(jù)理論就是用關(guān)系理論研究數(shù)據(jù)模型，在這里涉及到兩方面的問題，它們是：數(shù)據(jù)模型關(guān)系模型〔1〕數(shù)據(jù)模型數(shù)據(jù)模型是對(duì)數(shù)據(jù)存儲(chǔ)與操縱的抽象表示。其主要內(nèi)容是用于存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)構(gòu)造表示以及建立在該構(gòu)造上的數(shù)據(jù)操作表示。〔2〕關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型是一種以二維表的形式表示數(shù)據(jù)構(gòu)造又以二維表上的數(shù)據(jù)操作為特點(diǎn)的數(shù)據(jù)模型。1〕首先介紹二維表。二維表又稱表，它由表框架及表元組兩局部組成。表框架由表名及n個(gè)命名屬性列所構(gòu)成。表12.1給出了一個(gè)表名為student的表框架表1表名為student的表框架其中sno，sn，sd及sa分別表示屬性**、學(xué)生**，學(xué)生系別及學(xué)生年齡等。在表框架中可以按行存放數(shù)據(jù)，表中每個(gè)數(shù)據(jù)稱元組。元組由假設(shè)干個(gè)分量組成，其每個(gè)分量對(duì)應(yīng)表框架中的一個(gè)屬性值，如在表框架student中可以有如下的元組：它表示一個(gè)學(xué)生的相應(yīng)信息，該學(xué)生**為07001，**為張曼英，計(jì)算機(jī)系，年齡為18歲，它們分別是一個(gè)元組中的四個(gè)元組分量。一個(gè)表框架可以存儲(chǔ)假設(shè)干個(gè)元組。它們構(gòu)成了一個(gè)完整的二維表。表12.2給出了二維表的例。表2二維表student的例2〕接下來，介紹建立在二維表上的數(shù)據(jù)操作:eq\o\ac(○,1)查詢操作eq\o\ac(○,2)刪除操作eq\o\ac(○,3)插入操作eq\o\ac(○,4)修改操作關(guān)系數(shù)據(jù)模型中的根本邏輯操作共六種：eq\o\ac(○,1)表的列指定eq\o\ac(○,2)表的行選擇eq\o\ac(○,3)兩表的合并eq\o\ac(○,4)查詢操作eq\o\ac(○,5)刪除操作eq\o\ac(○,6)插入操作3〕關(guān)系數(shù)據(jù)模型的根本面貌：關(guān)系數(shù)據(jù)模型是以二維表為數(shù)據(jù)構(gòu)造，以元組為根本數(shù)據(jù)單位，在它的上面可以有六種根本操作。它構(gòu)成了一個(gè)數(shù)據(jù)庫系統(tǒng)的根本面貌。3.關(guān)系數(shù)據(jù)模型離散建模之一—關(guān)系代數(shù)模型關(guān)系代數(shù)模型以關(guān)系與代數(shù)系統(tǒng)為工具研究關(guān)系數(shù)據(jù)模型?！?〕首先從二維表討論起，二維表實(shí)際上是元組的集合，而元組則可視為n元有序組，因此二維表是n元有序組的集合亦即二維表即是n元關(guān)系?！?〕其次，二維表上的操作即是關(guān)系的運(yùn)算。二維表上的六種根本操作可對(duì)應(yīng)關(guān)系的五種運(yùn)算。1〕插入：R∪R’2〕刪除R－R’3〕兩表合并R×S4〕列指定：∏Ai1,Ai2,…,Aim(R)5〕行選擇σF〔R〕〔3〕關(guān)系代數(shù)由關(guān)系所組成的集合A上的五種運(yùn)算，它們分別是三種二元運(yùn)算—并，差及笛卡爾運(yùn)算，以及兩種一元運(yùn)算—投影及選擇運(yùn)算，且都是封閉的，從而構(gòu)成一個(gè)代數(shù)系統(tǒng)：〔A，∏，σ，∪，－，×〕該代數(shù)系統(tǒng)稱關(guān)系代數(shù)?！?〕關(guān)系代數(shù)的運(yùn)算規(guī)則1〕并運(yùn)算滿足結(jié)合律與交換律：R1∪〔R2∪R3〕=〔R1∪R2〕∪R3R1∪R2=R2∪R12〕投影運(yùn)算滿足交換律、吸收律及歸零律當(dāng)a1,a2,…,an與R無關(guān)時(shí)有∏a1,a2,…,am(R)="∏a1,a2,…,am〔∏b1,b2,…,bn(R)〕=∏b1,b2,…,bn〔∏a1,a2,…,am(R)〕當(dāng)a1,a2,…,an與R無關(guān)而b1,b2,…,bm與R有關(guān)時(shí)，∏a1,a2,…,an,b1,b2,…,bmR=∏b1,b2,…,bmR∏a1,a2,…,am〔∏b1,b2,…,bn(R)〕=∏a1,a2,…,am(R)3〕選擇運(yùn)算滿足交換律、串接律：σF1〔σF2(R)〕=σF2〔σF1(R)〕σF1〔σF2(R)〕=σF1∧F2(R)4〕選擇與投影運(yùn)算滿足交換律：σF〔∏a1,a2,…,am(R)〕=∏a1,a2,…,am〔σF〔R〕〕5〕選擇對(duì)笛卡爾乘積滿足分配律：σF〔R1×R2〕=σFR1×σFR2當(dāng)F與R無關(guān)，此時(shí)有：σFR=R，因此有：假設(shè)F僅涉及R1有：σF〔R1×R2〕=σF〔R1〕×R2假設(shè)F僅涉及R2有：σF〔R1×R2〕=R1×σF〔R2〕假設(shè)F=F1∧F2，而F1僅涉及R1；F2僅涉及R2，有：σF〔R1×R2〕=σF1〔R1〕×σF2〔R2〕6〕投影對(duì)笛卡爾乘積滿足分配律：∏a1,a2,…,an〔R1×R2〕=∏a1,a2,…,anR1×∏a1,a2,…,anR2〔5〕關(guān)系代數(shù)模型關(guān)系代數(shù)及其七組運(yùn)算規(guī)則組成了關(guān)系代數(shù)模型。3.關(guān)系代數(shù)模型的求解關(guān)系代數(shù)模型可以用于數(shù)據(jù)庫中的數(shù)據(jù)構(gòu)造表示，數(shù)據(jù)操作表示及其優(yōu)化，最后并可構(gòu)造標(biāo)準(zhǔn)化表達(dá)式。〔1〕數(shù)據(jù)構(gòu)造表示可以用n元關(guān)系表示關(guān)系模型中的二維表。例:有如表3所示的學(xué)生數(shù)據(jù)庫由學(xué)生、選課及課程三張二維表組成，它可以用下面的三個(gè)關(guān)系表示之。S={〔S101，John，CS，18〕，〔S102，Aris，CS，19〕，〔S103，Mary，CS，20〕}SC={〔S101，C01，4〕，〔S101，C02，5〕，〔S102，C03，4〕，〔S103，C01，3〕，〔S103，C03，5〕}C={〔C01，DB，C02〕，〔C02，OS，C02〕，〔C03，AI，C02〕}表3學(xué)生數(shù)據(jù)庫〔2〕數(shù)據(jù)操作表示可以用關(guān)系代數(shù)表達(dá)式表示數(shù)據(jù)操作。例:對(duì)學(xué)生數(shù)據(jù)庫用關(guān)系代數(shù)公式表示查詢及增、刪、改操作如下：eq\o\ac(○,1)查詢學(xué)生年齡大于18歲的學(xué)生**：∏sn(σsa＞18(S)〕eq\o\ac(○,2)查詢John所修讀的課程的課程號(hào)：∏oσSn=Jhon〔s×SC〕eq\o\ac(○,3)在選課表中增加學(xué)生S102選讀C03分?jǐn)?shù)為5分的元組。SC∪{〔S102，C03，5〕}〔3〕數(shù)據(jù)操作表示優(yōu)化例:優(yōu)化下面二式：eq\o\ac(○,1)∏sn(σsa＞18〔s×SC〕=∏sn(σsa＞18(S)×SC〕=∏sn(σsa＞18(S)×∏sn〔SC〕)=∏sn(σsa＞18(S))eq\o\ac(○,2)∏sno，o〔σSd=CS∧po=C01〔∏sd，sno(S)×∏o，po(C)〕〕=∏sno，o〔σSd=CS〔∏sd，sno(S)〕〕×〔σpo=C01〔∏o，po(C)〕〕=∏sno〔σSd=CS〔∏sd，sno(S)