第五篇 離散建模講稿

第五篇離散建模

離散建模是離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)技術(shù)及IT技術(shù)應(yīng)用間的聯(lián)系橋梁。也是學(xué)習(xí)離散數(shù)學(xué)的根本目的。它有兩部分內(nèi)容組成:1.離散建模概念與方法2.離散建模應(yīng)用實(shí)例1第11章離散建模概念與方法

11.1.離散建模概念在客觀世界中往往需要有許多問(wèn)題等待人們?nèi)ソ鉀Q。而解決的方法很多，最為常見的方法是將客觀世界中的問(wèn)題域抽象成一種形式化的數(shù)學(xué)表示稱數(shù)學(xué)模型，從而將對(duì)問(wèn)題域的求解變成為對(duì)數(shù)學(xué)表示式的求解。而由于人們對(duì)數(shù)學(xué)的研究已有數(shù)千年歷史，并已形成了一整套行之有效的對(duì)數(shù)學(xué)求解的理論與方法，因此用這種數(shù)學(xué)方法去解決實(shí)際問(wèn)題可以取得事倍功半的作用。而采用這種方法的關(guān)鍵之處是數(shù)學(xué)模型的建立，它稱為數(shù)學(xué)建模，而當(dāng)這種數(shù)學(xué)模型是建立在有限集或可列集之上時(shí)，此種模型的建立稱離散建模。2第11章離散建模概念與方法

11.2.離散建模方法（1）兩個(gè)世界理論在離散建模中有兩個(gè)世界，一個(gè)是現(xiàn)實(shí)世界另一個(gè)是離散世界?，F(xiàn)實(shí)世界是問(wèn)題域產(chǎn)生的世界，離散世界則是一種數(shù)學(xué)世界，它有三個(gè)特性：

離散世界采用離散數(shù)學(xué)語(yǔ)言，該語(yǔ)言具有簡(jiǎn)潔性且表達(dá)力豐富。

離散世界所表示的是一種抽象符號(hào)，它是一種形式化符號(hào)體系。

離散世界中的環(huán)境簡(jiǎn)單，它在離散建模時(shí)設(shè)立，可以屏蔽大量無(wú)關(guān)信息對(duì)問(wèn)題求解的干擾。為求解問(wèn)題須將問(wèn)題域轉(zhuǎn)換成離散模型,然后對(duì)離散模型求解,再逆向轉(zhuǎn)換成現(xiàn)實(shí)世界中的解.3第11章離散建模概念與方法

（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)換作介紹：

1現(xiàn)實(shí)世界到離散世界的轉(zhuǎn)換該轉(zhuǎn)換又稱離散建?；蚝?jiǎn)稱轉(zhuǎn)換。這種轉(zhuǎn)換是離散建模方法的核心。它實(shí)際上是將現(xiàn)實(shí)世界中的問(wèn)題轉(zhuǎn)換成離散世界中的離散模型。這種過(guò)程是將問(wèn)題域中問(wèn)題采取屏蔽語(yǔ)義、簡(jiǎn)化環(huán)境、強(qiáng)化關(guān)系所形成的一種抽象化、形式化過(guò)程，在轉(zhuǎn)換時(shí)所要采用下面幾種手段：4第11章離散建模概念與方法

選取一種離散語(yǔ)言，亦即是選擇一個(gè)離散數(shù)學(xué)學(xué)科門類，（如圖論，代數(shù)系統(tǒng)，數(shù)理邏輯及關(guān)系等，也可以選擇其中的一些子門類如圖論中的樹，代數(shù)系統(tǒng)中的群論等等），以此學(xué)科的符號(hào)體系作為一種形式語(yǔ)言稱離散語(yǔ)言。

從問(wèn)題域中確定離散模型的基本對(duì)象集合。

從問(wèn)題域中確定離散模型的靜態(tài)結(jié)構(gòu)、動(dòng)態(tài)行為以及約束規(guī)則。

用離散語(yǔ)言描述這些集合、結(jié)構(gòu)，行為與規(guī)則并組成離散模型。在轉(zhuǎn)換過(guò)程中要注意如下幾點(diǎn)：

所選用的離散語(yǔ)言并不是唯一的，有時(shí)可以有多種選擇。5第11章離散建模概念與方法

所建的離散模型有時(shí)可能與傳統(tǒng)的數(shù)學(xué)結(jié)構(gòu)不完全一致，此時(shí)須構(gòu)造新的數(shù)學(xué)結(jié)構(gòu)以適應(yīng)建模的需要。

問(wèn)題域中的環(huán)境與平臺(tái)一般可用離散模型中的約束規(guī)則實(shí)現(xiàn)。2從離散世界到現(xiàn)實(shí)世界的轉(zhuǎn)換該轉(zhuǎn)換是一種語(yǔ)義化的轉(zhuǎn)換，它是一種逆向轉(zhuǎn)換，因此又稱逆轉(zhuǎn)換，在該轉(zhuǎn)換中是將離散模型的解轉(zhuǎn)換成問(wèn)題域中的解。由于離散世界中解的形式是一種抽象的形式化符號(hào)體系，沒有任何語(yǔ)義，只有賦予問(wèn)題域中語(yǔ)義后才成為問(wèn)題域中的解。6第11章離散建模概念與方法

兩個(gè)世界理論與兩個(gè)世界轉(zhuǎn)換構(gòu)成了完整的離散建模方法，它可以用下面的圖表示。圖11.1離散建模示意圖現(xiàn)實(shí)世界問(wèn)題域問(wèn)題域解轉(zhuǎn)換（抽象化）逆轉(zhuǎn)換（語(yǔ)義化）離散世界離散模型離散模型解求解7第11章離散建模概念與方法而離散建模方法的整個(gè)過(guò)程可以用下面幾個(gè)步驟表示：

在現(xiàn)實(shí)世界中給出問(wèn)題域；

將問(wèn)題域抽象成離散模型；

離散模型求解；

解的語(yǔ)義化；

問(wèn)題域的解。8第11章離散建模概念與方法11.3.離散建模的步驟在離散建模實(shí)際操作中須有若干個(gè)步驟的操作過(guò)程，它們是：

需求描述—問(wèn)題域形成；

離散模型形成；

離散模型檢驗(yàn)與修改；

離散模型求解；

解的語(yǔ)義化及問(wèn)題域解的獲得。9第12章離散建模應(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ī)等），通道資源等多種。10第12章離散建模應(yīng)用實(shí)例

（2）進(jìn)程：在一臺(tái)計(jì)算機(jī)中往往可以運(yùn)行多個(gè)程序，而一般運(yùn)行的程序稱為進(jìn)程。在資源與進(jì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)行過(guò)程中還不斷申請(qǐng)資源以獲得繼續(xù)運(yùn)行的權(quán)力，同時(shí)也不斷釋放資源，使資源能得以充分利用；而當(dāng)進(jìn)程所申請(qǐng)的資源無(wú)法得到時(shí)（即表示此資源被它進(jìn)程所占有），它必須等待，直到它進(jìn)程對(duì)該資源使用完畢并釋放后此進(jìn)程才能獲得該資源并繼續(xù)運(yùn)行直至進(jìn)程結(jié)束。因此，進(jìn)程與資源的關(guān)系是一種動(dòng)態(tài)關(guān)系，其演化過(guò)程可以用下面的圖12.1表示之。11第12章離散建模應(yīng)用實(shí)例進(jìn)程獲得資源進(jìn)程運(yùn)行進(jìn)程等待進(jìn)程結(jié)束申請(qǐng)資源繼續(xù)申請(qǐng)資源獲得獲得完成未獲得圖12.1進(jìn)程演化圖12第12章離散建模應(yīng)用實(shí)例

而死鎖的產(chǎn)生則是進(jìn)程演化中的一種特殊現(xiàn)象。如進(jìn)程甲占有資源A同時(shí)又申請(qǐng)資源B，與此同時(shí)進(jìn)程乙占有資源B同時(shí)又申請(qǐng)資源A，此時(shí)兩進(jìn)程都無(wú)法申請(qǐng)到所需資源，因此只能等待，而等待是無(wú)期限的，因而稱為死鎖。推而廣之，對(duì)多個(gè)進(jìn)程與多個(gè)資源可能還會(huì)出現(xiàn)循環(huán)等待的現(xiàn)象，這就是一般意義上的死鎖。2.離散建模及模型建立（1）選擇一種離散語(yǔ)言：根據(jù)問(wèn)題域描述，該項(xiàng)死鎖檢測(cè)主要研究資源間的一種特殊關(guān)系，因此用關(guān)系或圖論較為合適，而考慮到圖的方法結(jié)構(gòu)性好，直觀性強(qiáng)，因而以圖論作為建模工具較為合理。13第12章離散建模應(yīng)用實(shí)例

（2）確定研究對(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。（4）模型的建立：以R為結(jié)點(diǎn)以S為邊可以構(gòu)成一個(gè)有向圖G=（R，S）。它組成了進(jìn)程資源申請(qǐng)的圖模型。在這個(gè)圖中的每個(gè)邊均有權(quán)Pi，它表示申請(qǐng)資源的進(jìn)程。14第12章離散建模應(yīng)用實(shí)例

例:設(shè)有操作系統(tǒng)在時(shí)刻t有4個(gè)進(jìn)程與4個(gè)資源，它們分別是：R={R1，R2，R3，R4}P={P1，P2，P3，P4}在該時(shí)刻的資源分配狀況是：P1占有資源R4且申請(qǐng)資源R1；P2占有資源R1且申請(qǐng)資源R2

與R3；P3占有資源R2且申請(qǐng)資源R3；P4占有資源R3且申請(qǐng)資源R1

與R4。它們可構(gòu)成一個(gè)有權(quán)、有向圖G=（R，S）如圖12.2所示。

15第12章離散建模應(yīng)用實(shí)例

3.模型檢驗(yàn)與修改:略4.模型求解在問(wèn)題域中死鎖檢驗(yàn)的解是資源循環(huán)等待，而在圖論模型中資源循環(huán)等待相當(dāng)于圖中存在回路。進(jìn)一步，可以用可達(dá)性矩陣計(jì)算方法判別是否出現(xiàn)回路，即可達(dá)性矩陣的對(duì)角線中出現(xiàn)有“1”。R3圖12.2資源申請(qǐng)圖R1R2R4P1P2P3P4P4P216第12章離散建模應(yīng)用實(shí)例

如設(shè)可達(dá)性矩陣為如圖12.3所示，則判別產(chǎn)生回路的計(jì)算公式為D’=d11（+）d22（+）…（+）dnn=1.

5.解的語(yǔ)義化最后在模型中所產(chǎn)生的判別公式D’，可將其語(yǔ)義化為：當(dāng)D’為1時(shí)表操作系統(tǒng)已產(chǎn)生死鎖；當(dāng)D’為0時(shí)表操作系統(tǒng)未產(chǎn)生死鎖。D=d11d12………..

。。。。。d1nd21d22。。。。。。。。。d2n。。。。。。。。。。。。。。dn1dn2。。。。。。。。。dnn圖12.3可達(dá)性矩陣表示式17第12章離散建模應(yīng)用實(shí)例

在例中我們有該圖的可達(dá)性矩陣為：

從而有D’=1，這表明在時(shí)刻t時(shí)系統(tǒng)產(chǎn)生死鎖。6.點(diǎn)評(píng)死鎖檢測(cè)的離散建模特點(diǎn)是：（1）該離散建模所建模型簡(jiǎn)單，可計(jì)算且效果好。（2）該離散建?？梢酝瑫r(shí)用圖論與關(guān)系實(shí)現(xiàn)，但由于在圖論中對(duì)回路的研究與表示都優(yōu)于關(guān)系，因此用圖論較為合適。（3）在該離散模型中運(yùn)用圖論中的通路與回路以及相應(yīng)的矩陣計(jì)算方法較為方便的解決了死鎖問(wèn)題。

1111111111111111D=18第12章離散建模應(yīng)用實(shí)例12.3數(shù)據(jù)庫(kù)中關(guān)系數(shù)據(jù)模型的離散建模1.需求描述關(guān)系數(shù)據(jù)理論就是用關(guān)系理論研究數(shù)據(jù)模型，在這里涉及到兩方面的問(wèn)題，它們是：

數(shù)據(jù)模型

關(guān)系模型（1）數(shù)據(jù)模型數(shù)據(jù)模型是對(duì)數(shù)據(jù)存儲(chǔ)與操縱的抽象表示。其主要內(nèi)容是用于存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)表示以及建立在該結(jié)構(gòu)上的數(shù)據(jù)操作表示。（2）關(guān)系數(shù)據(jù)模型關(guān)系數(shù)據(jù)模型是一種以二維表的形式表示數(shù)據(jù)結(jié)構(gòu)又以二維表上的數(shù)據(jù)操作為特點(diǎn)的數(shù)據(jù)模型。19第12章離散建模應(yīng)用實(shí)例

1）首先介紹二維表。二維表又稱表，它由表框架及表元組兩部分組成。表框架由表名及n個(gè)命名屬性列所構(gòu)成。表12.1給出了一個(gè)表名為student的表框架。

表12.1表名為student的表框架

其中sno，sn，sd及sa分別表示屬性學(xué)號(hào)、學(xué)生姓名，學(xué)生系別及學(xué)生年齡等。在表框架中可以按行存放數(shù)據(jù)，表中每個(gè)數(shù)據(jù)稱元組。元組由若干個(gè)分量組成，其每個(gè)分量對(duì)應(yīng)表框架中的一個(gè)屬性值，如在表框架student中可以有如下的元組：

studentsnosnsdsa20第12章離散建模應(yīng)用實(shí)例（07001張曼英SC18）

它表示一個(gè)學(xué)生的相應(yīng)信息，該學(xué)生學(xué)號(hào)為07001，姓名為張曼英，計(jì)算機(jī)系，年齡為18歲，它們分別是一個(gè)元組中的四個(gè)元組分量。一個(gè)表框架可以存儲(chǔ)若干個(gè)元組。它們構(gòu)成了一個(gè)完整的二維表。表12.2給出了二維表的例。表12.2二維表student的例studentsnosnsdsa07001張曼英CS1907002丁一明CS201818CSCS王愛國(guó)李強(qiáng)070030700421第12章離散建模應(yīng)用實(shí)例

2）接下來(lái)，我們介紹建立在二維表上的數(shù)據(jù)操作:

查詢操作

刪除操作

插入操作

修改操作關(guān)系數(shù)據(jù)模型中的基本邏輯操作共六種：

表的列指定

表的行選擇

兩表的合并

查詢操作（該操作不含邏輯成份僅是一種物理操作因此在模型中可省略）。

刪除操作

插入操作22第12章離散建模應(yīng)用實(shí)例

3）關(guān)系數(shù)據(jù)模型的基本面貌：關(guān)系數(shù)據(jù)模型是以二維表為數(shù)據(jù)結(jié)構(gòu)，以元組為基本數(shù)據(jù)單位，在它的上面可以有六種基本操作。它構(gòu)成了一個(gè)數(shù)據(jù)庫(kù)系統(tǒng)的基本面貌。3.關(guān)系數(shù)據(jù)模型離散建模之一—關(guān)系代數(shù)模型關(guān)系代數(shù)模型以關(guān)系與代數(shù)系統(tǒng)為工具研究關(guān)系數(shù)據(jù)模型。（1）首先從二維表討論起，二維表實(shí)際上是元組的集合，而元組則可視為n元有序組，因此二維表是n元有序組的集合亦即二維表即是n元關(guān)系。（2）其次，二維表上的操作即是關(guān)系的運(yùn)算。二維表上的六種基本操作可對(duì)應(yīng)關(guān)系的五種運(yùn)算。

23第12章離散建模應(yīng)用實(shí)例1）插入：R∪R’2）刪除R－R’3）兩表合并R×S4）列指定：∏Ai1,Ai2,…,Aim(R)5）行選擇σF（R）24第12章離散建模應(yīng)用實(shí)例

（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ù)。25第12章離散建模應(yīng)用實(shí)例（4）關(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無(wú)關(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無(wú)關(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)26第12章離散建模應(yīng)用實(shí)例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無(wú)關(guān)，此時(shí)有：σFR=R，因此有：若F僅涉及R1有：σF（R1×R2）=σF（R1）×R2若F僅涉及R2有：σF（R1×R2）=R1×σF（R2）若F=

F1∧F2，而F1僅涉及R1；F2僅涉及R2，有：σF（R1×R2）=σF1（R1）×σF2（R2）27第12章離散建模應(yīng)用實(shí)例

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ù)庫(kù)中的數(shù)據(jù)結(jié)構(gòu)表示，數(shù)據(jù)操作表示及其優(yōu)化，最后并可構(gòu)造規(guī)范化表達(dá)式。（1）數(shù)據(jù)結(jié)構(gòu)表示可以用n元關(guān)系表示關(guān)系模型中的二維表。28第12章離散建模應(yīng)用實(shí)例例:有如表12.3所示的學(xué)生數(shù)據(jù)庫(kù)由學(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）}29第12章離散建模應(yīng)用實(shí)例表12.3學(xué)生數(shù)據(jù)庫(kù)SCsnocnogS101C014S101C0254C03S102S103S103C01C0335（b）選課表SsnosnsdsaS101JhonCS18S102ArisCS1920CSMaryS103（a）學(xué)生表CcnocnpcnoC01DBC02C02OSC02C02AIC03（c）課程表30第12章離散建模應(yīng)用實(shí)例

（2）數(shù)據(jù)操作表示可以用關(guān)系代數(shù)表達(dá)式表示數(shù)據(jù)操作。例:對(duì)學(xué)生數(shù)據(jù)庫(kù)用關(guān)系代數(shù)公式表示查詢及增、刪、改操作如下：

查詢學(xué)生年齡大于18歲的學(xué)生姓名：∏sn(σsa＞18(S)）

查詢John所修讀的課程的課程號(hào)：∏cnoσSn=Jhon（s×SC）

在選課表中增加學(xué)生S102選讀C03分?jǐn)?shù)為5分的元組。SC∪{（S102，C03，5）}31第12章離散建模應(yīng)用實(shí)例