第五篇 離散建模講稿

第五篇離散建模

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

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

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

離散世界采用離散數(shù)學語言，該語言具有簡潔性且表達力豐富。

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

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

（2）兩個世界的轉(zhuǎn)換在離散建模方法中需要構(gòu)作兩種轉(zhuǎn)換，即由現(xiàn)實世界到離散世界的轉(zhuǎn)換以及由離散世界到現(xiàn)實世界的逆轉(zhuǎn)換，而其中第一種轉(zhuǎn)換尤為重要，這種轉(zhuǎn)換我們一般即稱之為離散建模。下面對兩種轉(zhuǎn)換作介紹：

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

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

從問題域中確定離散模型的基本對象集合。

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

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

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

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

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

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

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

將問題域抽象成離散模型；

離散模型求解；

解的語義化；

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

需求描述—問題域形成；

離散模型形成；

離散模型檢驗與修改；

離散模型求解；

解的語義化及問題域解的獲得。9第12章離散建模應用實例

1.需求描述死鎖檢測為操作系統(tǒng)中死鎖現(xiàn)象出現(xiàn)提供實時報警信號。操作系統(tǒng)是管理計算機資源，協(xié)調(diào)計算機用戶與資源間的關(guān)系，為用戶在計算機中順利運行提供支撐的一種軟件系統(tǒng)。而死鎖現(xiàn)象則是用戶間為爭奪資源而產(chǎn)生的一種矛盾，因此及時發(fā)現(xiàn)矛盾及化解矛盾是操作系統(tǒng)重要職能之一。在操作系統(tǒng)中有兩種重要的注視目標，它們是“資源”與“進程”：（1）資源：操作系統(tǒng)是管理計算機中資源的機構(gòu)，而計算機中的資源包括有CPU資源，內(nèi)存資源，外部設(shè)備資源（如打印機等），通道資源等多種。10第12章離散建模應用實例

（2）進程：在一臺計算機中往往可以運行多個程序，而一般運行的程序稱為進程。在資源與進程之間存在著緊密的關(guān)聯(lián)，其中主要的關(guān)聯(lián)是：進程需要資源，只有有了充足的資源，進程才能運行。在一般情況下，進程在運行前需申請資源，只有獲得資源后才能運行，在運行過程中還不斷申請資源以獲得繼續(xù)運行的權(quán)力，同時也不斷釋放資源，使資源能得以充分利用；而當進程所申請的資源無法得到時（即表示此資源被它進程所占有），它必須等待，直到它進程對該資源使用完畢并釋放后此進程才能獲得該資源并繼續(xù)運行直至進程結(jié)束。因此，進程與資源的關(guān)系是一種動態(tài)關(guān)系，其演化過程可以用下面的圖12.1表示之。11第12章離散建模應用實例進程獲得資源進程運行進程等待進程結(jié)束申請資源繼續(xù)申請資源獲得獲得完成未獲得圖12.1進程演化圖12第12章離散建模應用實例

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

（2）確定研究對象：在離散建模中，操作系統(tǒng)的基本研究對象集合為資源集合與進程集合，設(shè)有n個資源與m個進程，它們可表示為：資源集合：R={R1，R2，…，Rn}進程集合：P={P1，P2，…，Pm}（3）資源間的關(guān)系：進程P已占有資源Ri且申請資源Rj并處等待中，可用有序偶（Ri，Rj）表示。而它們的全體則構(gòu)成一個關(guān)系，稱資源申請關(guān)系S。（4）模型的建立：以R為結(jié)點以S為邊可以構(gòu)成一個有向圖G=（R，S）。它組成了進程資源申請的圖模型。在這個圖中的每個邊均有權(quán)Pi，它表示申請資源的進程。14第12章離散建模應用實例

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

與R3；P3占有資源R2且申請資源R3；P4占有資源R3且申請資源R1

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

15第12章離散建模應用實例

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

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

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

。。。。。d1nd21d22。。。。。。。。。d2n。。。。。。。。。。。。。。dn1dn2。。。。。。。。。dnn圖12.3可達性矩陣表示式17第12章離散建模應用實例

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

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

1111111111111111D=18第12章離散建模應用實例12.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ù)模型是對數(shù)據(jù)存儲與操縱的抽象表示。其主要內(nèi)容是用于存儲數(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ù)操作為特點的數(shù)據(jù)模型。19第12章離散建模應用實例

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

表12.1表名為student的表框架

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

studentsnosnsdsa20第12章離散建模應用實例（07001張曼英SC18）

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

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

查詢操作

刪除操作

插入操作

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

表的列指定

表的行選擇

兩表的合并

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

刪除操作

插入操作22第12章離散建模應用實例

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

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

（3）關(guān)系代數(shù)由關(guān)系所組成的集合A上的五種運算，它們分別是三種二元運算—并，差及笛卡爾運算，以及兩種一元運算—投影及選擇運算，且都是封閉的，從而構(gòu)成一個代數(shù)系統(tǒng)：（A，∏，σ，∪，－，×）

該代數(shù)系統(tǒng)稱關(guān)系代數(shù)。25第12章離散建模應用實例（4）關(guān)系代數(shù)的運算規(guī)則1）并運算滿足結(jié)合律與交換律：R1∪（R2∪R3）=（R1∪R2）∪R3R1∪R2=R2∪R12）投影運算滿足交換律、吸收律及歸零律當a1,a2,…,an與R無關(guān)時有∏a1,a2,…,am(R)=

∏a1,a2,…,am（∏b1,b2,…,bn(R)）=

∏b1,b2,…,bn（∏a1,a2,…,am(R)）當a1,a2,…,an與R無關(guān)而b1,b2,…,bm與R有關(guān)時，∏a1,a2,…,an,b1,b2,…,bmR=∏b1,b2,…,bmR∏a1,a2,…,am（∏b1,b2,…,bn(R)）=∏a1,a2,…,am(R)26第12章離散建模應用實例3）選擇運算滿足交換律、串接律：σF1（σF2(R)）=σF2（σF1(R)）σF1（σF2(R)）=σF1∧F2(R)4）選擇與投影運算滿足交換律：σF（∏a1,a2,…,am(R)）=∏a1,a2,…,am（σF（R））5）選擇對笛卡爾乘積滿足分配律：σF（R1×R2）=σFR1×σFR2當F與R無關(guān)，此時有：σ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章離散建模應用實例

6）投影對笛卡爾乘積滿足分配律：

∏a1,a2,…,an（R1×R2）=

∏a1,a2,…,anR1×∏a1,a2,…,anR2（5）關(guān)系代數(shù)模型

關(guān)系代數(shù)及其七組運算規(guī)則組成了關(guān)系代數(shù)模型。3.關(guān)系代數(shù)模型的求解關(guān)系代數(shù)模型可以用于數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)表示，數(shù)據(jù)操作表示及其優(yōu)化，最后并可構(gòu)造規(guī)范化表達式。（1）數(shù)據(jù)結(jié)構(gòu)表示可以用n元關(guān)系表示關(guān)系模型中的二維表。28第12章離散建模應用實例例:有如表12.3所示的學生數(shù)據(jù)庫由學生、選課及課程三張二維表組成，它可以用下面的三個關(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章離散建模應用實例表12.3學生數(shù)據(jù)庫SCsnocnogS101C014S101C0254C03S102S103S103C01C0335（b）選課表SsnosnsdsaS101JhonCS18S102ArisCS1920CSMaryS103（a）學生表CcnocnpcnoC01DBC02C02OSC02C02AIC03（c）課程表30第12章離散建模應用實例

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

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

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

在選課表中增加學生S102選讀C03分數(shù)為5分的元組。SC∪{（S102，C03，5）}31第12章離散建模應用實例