文章編號(hào)：1672-5913(2008)18-0140-02

摘要：隨機(jī)過程與排對(duì)論課程屬于計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)研究生課程基礎(chǔ)課程。本文介紹了我院是如何將工程化教學(xué)思想應(yīng)用于課程教學(xué)中，從而對(duì)學(xué)生理解和掌握隨機(jī)過程與排隊(duì)論理論，并熟練運(yùn)用所學(xué)知識(shí)起到非常積極的作用。

關(guān)鍵詞：隨機(jī)過程；排隊(duì)論；工程應(yīng)用

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B

1引言

當(dāng)前計(jì)算機(jī)科學(xué)技術(shù)發(fā)展非常迅猛，而計(jì)算機(jī)科學(xué)的研究也是日新月異。在計(jì)算機(jī)科學(xué)研究中，一些最基本的研究工具必不可少，例如對(duì)算法的推導(dǎo)，優(yōu)化方案設(shè)計(jì)等。因此在計(jì)算機(jī)科學(xué)研究生教學(xué)階段，有必要將科學(xué)研究中需要的一些基礎(chǔ)知識(shí)開設(shè)為必修課程。在具體教學(xué)過程中，則體現(xiàn)為一門門的數(shù)學(xué)課程或基本的物理課程。

隨機(jī)過程與排隊(duì)論作為計(jì)算機(jī)科學(xué)研究必須的數(shù)學(xué)工具之一，通常被計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)列為研究生必修課程。它是學(xué)生進(jìn)一步科學(xué)研究或者前往公司負(fù)責(zé)重要的項(xiàng)目設(shè)計(jì)的理論基礎(chǔ)。除了作為數(shù)學(xué)課程能訓(xùn)練拔高邏輯思維之外，這門課程從本身理論價(jià)值的角度來看，它所涉及的概率知識(shí)、馬爾科夫過程知識(shí)、隱馬爾科夫過程、生滅過程、以及各類排隊(duì)模型和解決方法在信號(hào)處理、模式識(shí)別、通訊、計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)、管理科學(xué)等領(lǐng)域都有重要應(yīng)用價(jià)值。同時(shí)，課程所涉及的一些理論研究方法，證明過程也為學(xué)生將來進(jìn)一步的科學(xué)研究提供了范本。學(xué)生通過學(xué)習(xí)該門課程將能懂得如何設(shè)計(jì)排隊(duì)模型，如何設(shè)計(jì)以及分析算法性質(zhì)等。

在實(shí)際的教學(xué)過程中，許多院校多采用數(shù)學(xué)專業(yè)教師編寫的《隨即過程》和《排隊(duì)論》這兩本教材。由于數(shù)學(xué)專業(yè)教師比較重視嚴(yán)謹(jǐn)?shù)睦碚撟C明以及邏輯分析，在書中對(duì)這些知識(shí)是如何產(chǎn)生，以及在計(jì)算機(jī)科學(xué)中如何應(yīng)用卻涉及不多。計(jì)算科學(xué)與技術(shù)專業(yè)的學(xué)生學(xué)后多感覺目的性不強(qiáng)，也導(dǎo)致對(duì)知識(shí)理解不深。本文將通過若干具體例子，列舉結(jié)合工程應(yīng)用講述隨機(jī)過程與排隊(duì)論知識(shí)的方法，實(shí)際教學(xué)效果表明，結(jié)合工程化應(yīng)用將很大程度地幫助學(xué)生理解并應(yīng)用本門課程知識(shí)。

2結(jié)合信號(hào)處理講述隨機(jī)過程相關(guān)概念

在講述該概念過程中，大多人為構(gòu)造一些隨機(jī)過程的例子，計(jì)算相關(guān)函數(shù)和互相關(guān)函數(shù)。學(xué)生一般都能理解如何計(jì)算相關(guān)函數(shù)和互相關(guān)函數(shù)。此后，隨機(jī)課程教學(xué)將轉(zhuǎn)入馬爾科夫過程，此概念就未再涉及。學(xué)生學(xué)習(xí)后，并不了解這個(gè)概念的實(shí)際意義和如何應(yīng)用這個(gè)概念。在教學(xué)中，我們將討論運(yùn)用去相關(guān)的方法進(jìn)行盲信號(hào)分離。

給定觀察信號(hào)x(t)={x1(t)，x2 (t)，…，xn(t)，}，源信號(hào)s(t)={s1(t)，s2 (t)，…，sn(t)}和未知非奇異混合矩陣A∈Rnxn，其中x(t)=Rs(t)，盲信號(hào)分離即是找到矩陣W∈Rnxn，在未知矩陣A和源信號(hào)的情形下，使得y(t)=Wx(t)與源信號(hào)相似。盲信號(hào)分離在圖像分離、生物信號(hào)處理、軍事都有非常重要的應(yīng)用。在這里我們用去相關(guān)的方法從觀察信號(hào)中獲得源信號(hào)。此處假設(shè)信號(hào)自身具有較強(qiáng)相關(guān)性，而信號(hào)之間相關(guān)性不強(qiáng)。給定兩個(gè)時(shí)間s，t，如果矩陣E(y(s)y(t)T) 逼近對(duì)角型，則此時(shí)的y(t)即為恢復(fù)的源信號(hào)。注意到y(tǒng)(t)=Wx(t)，有

F(t)=WE(x(t)x(s) T)WT。

由上，問題轉(zhuǎn)化為對(duì)矩陣E(x(t)x(s) T)對(duì)角化，即是求矩陣E(x(t)x(s) T)特征值與特征向量。如果存在時(shí)間s，t，使得矩陣E(x(t)x(s) T)特征值互不相同，則特征向量矩陣即為我們所尋找的分離矩陣W。

在教學(xué)過程中，我們同時(shí)展示以信號(hào)處理的試驗(yàn)，通過工程化應(yīng)用加深了學(xué)生對(duì)概念的理解，也使他們更容易運(yùn)用所學(xué)概念于實(shí)際應(yīng)用之中。除此之外，隨機(jī)過程的一些基本概念還可以用其它信號(hào)處理和工程應(yīng)用講述，在這里不再贅述。

3結(jié)合信息安全講述馬爾科夫過程

例2在隨機(jī)過程中有一個(gè)重要的概念稱為馬氏鏈[1]。定義如下：設(shè){X(n)，n=0，1，2，…}為隨機(jī)序列，狀態(tài)空間E={0，1，2，…}。如果對(duì)于任意非負(fù)整數(shù)k、n1

P{X(m+k)=im+k|X(n1)=in1，X(n2)=in2，…，X(nj)=inj，X(m)=im}

=P{X(m+k)=im+k|X(m)=im}

成立，則稱{X(n)，n=0，1，2，…}為離散參數(shù)馬爾可夫鏈，簡稱馬氏鏈。設(shè){X(n)，n=0，1，2，…} 為馬氏鏈，E={0，1，2，…}，稱條件概率

pij(m，k)＝P{X(m+k)=j|X(m)=i}

為馬氏鏈{X(n)，n=0，1，…}在m時(shí)刻的k步轉(zhuǎn)移概率。特別地，k=1時(shí)，

pij(m，1)＝P{X(m+1)=j|X(m)=i}

稱為一步轉(zhuǎn)移概率，簡稱轉(zhuǎn)移概率。其中有一定理：齊次馬氏鏈的有限維分布由初始分布和轉(zhuǎn)移概率確定，且滿足

P{X(n1)=i1，X(n2)=i1，…，X(nk)=ik}

其中P{X(n1)=i1，X(n2)=i2，…，X(nk)=ik}為齊次馬氏鏈的k維概率分布。

在教學(xué)中，我們結(jié)合計(jì)算機(jī)主機(jī)入侵檢測(cè)來講述這個(gè)概念。通過觀察發(fā)現(xiàn)，正常系統(tǒng)調(diào)用跡中存在大量的有規(guī)律的、重復(fù)出現(xiàn)的系統(tǒng)調(diào)用序列，把這些重復(fù)出現(xiàn)的序列看成一個(gè)獨(dú)立的基本單位( 宏)可以更精確地刻畫程序的正常行為模式[2]。將每一個(gè)宏看成一種在馬爾科夫模型中的狀態(tài)假定在t時(shí)刻系統(tǒng)狀態(tài)的隨機(jī)狀態(tài)變量為Xt，建立如上所示馬爾可夫鏈模型。則狀態(tài)序列it-k，i2，…，it發(fā)生的概率可由上述定理計(jì)算獲得

P(it-k，i2，…，it)= 。

將系統(tǒng)軌跡根據(jù)獨(dú)立的基本單位(宏)，按對(duì)宏的編號(hào)重新組織為一新的序列L，概率P的計(jì)算方法如下： Pij= ，Pi= 。這里Nij為在L中觀察到在t處為狀態(tài)i和t+1處在狀態(tài)j的對(duì)的個(gè)數(shù)。Ni在L中觀察到狀態(tài)為i的個(gè)數(shù)，N表示L中所有觀察到的宏的個(gè)數(shù)。檢測(cè)的依據(jù)就是通過計(jì)算t時(shí)刻的15個(gè)連續(xù)的宏?duì)顟B(tài)出現(xiàn)的概率。概率越高者則它越可能屬于正常的宏?duì)顟B(tài)序列。

在結(jié)合信息安全中主機(jī)入侵檢測(cè)工程應(yīng)用講述馬爾科夫鏈后，許多學(xué)生舉一反三思考了將馬爾科夫鏈用于網(wǎng)絡(luò)入侵檢測(cè)，金融序列分類等等。從這里可以看出，結(jié)合工程應(yīng)用講述隨機(jī)過程，將對(duì)于學(xué)生掌握理論知識(shí)并靈活運(yùn)用這些知識(shí)有很重要的幫助。

4結(jié)合計(jì)算機(jī)網(wǎng)絡(luò)講述排隊(duì)論

研究排隊(duì)現(xiàn)象的目的是：通過對(duì)排隊(duì)系統(tǒng)中概率規(guī)律的研究，使系統(tǒng)達(dá)到最優(yōu)設(shè)計(jì)和最優(yōu)控制，以最小費(fèi)用實(shí)現(xiàn)系統(tǒng)的最大效益。

例3 在排隊(duì)論中講述了如下圖1所示M/M/c:N/∞/FCFS排隊(duì)系統(tǒng)[3]，

設(shè)系統(tǒng)容量為N(N≥c)，當(dāng)系統(tǒng)中的顧數(shù)n＜N時(shí)，到達(dá)的顧客就進(jìn)入系統(tǒng)；當(dāng)n=N時(shí)，到達(dá)的顧客就被拒絕。設(shè)顧客到達(dá)的速率為λ，每個(gè)服務(wù)臺(tái)服務(wù)的速率為μ，服務(wù)能力ρ=λ/cμ。由于系統(tǒng)不會(huì)無限止地接納顧客，對(duì)ρ不必加以限制。建立了該模型后，我們計(jì)算了系列參數(shù)如隊(duì)長概率

， .

相應(yīng)地我們能計(jì)算平均對(duì)長、平均等待對(duì)長、平均等待時(shí)間、 平均逗留時(shí)間等。在傳統(tǒng)的排隊(duì)論教材中，再講述了如何計(jì)算參數(shù)后，一般都舉一些簡單的例子計(jì)算相關(guān)參數(shù)。針對(duì)計(jì)算機(jī)科學(xué)專業(yè)學(xué)習(xí)排隊(duì)論重在應(yīng)用的特點(diǎn)，我們講述了該系統(tǒng)在計(jì)算機(jī)網(wǎng)絡(luò)流量控制模型設(shè)計(jì)中的應(yīng)用。

只要存在“Client/Server”的環(huán)境，就可以采用排隊(duì)模型進(jìn)行分析。在一個(gè)基于Client/Server模型的計(jì)算機(jī)應(yīng)用系統(tǒng)中，非常適合采用排隊(duì)論M/M/c:N/∞/FCFS模型來進(jìn)行流量控制，當(dāng)Client請(qǐng)求超過Server設(shè)計(jì)容量時(shí)，能避免Server的負(fù)荷惡性增長，確保系統(tǒng)能提供設(shè)計(jì)容量的服務(wù)。如圖2所示[4]。

這樣，當(dāng)業(yè)務(wù)請(qǐng)求書超過最大并發(fā)處理數(shù)c時(shí)，可將業(yè)務(wù)請(qǐng)求放入排隊(duì)隊(duì)列中進(jìn)行排隊(duì)，因排隊(duì)過程一般不消耗Server負(fù)荷，可以確保Server的平穩(wěn)運(yùn)行。近似認(rèn)為Client的請(qǐng)求服從Poisson分布，服務(wù)能力滿足負(fù)指數(shù)分布，則完全可以通過排隊(duì)論[M/M/c]:[N/∞/FCFS]模型計(jì)算出服務(wù)能力、業(yè)務(wù)請(qǐng)求流量、排隊(duì)隊(duì)列與接通率、平均排隊(duì)時(shí)間、平均逗留時(shí)間的關(guān)系。則：

(1) 在某種業(yè)務(wù)請(qǐng)求流量下，為獲得需要的接通率，我們可以計(jì)算出合適的隊(duì)列長度。

(2) 在大業(yè)務(wù)量情況下，如果限定逗留時(shí)長，可計(jì)算出一個(gè)合適的排隊(duì)隊(duì)列長度，當(dāng)排隊(duì)長度超過該值時(shí)，業(yè)務(wù)請(qǐng)求再繼續(xù)排隊(duì)就沒有意義。(比如設(shè)定超時(shí)退出機(jī)制的環(huán)境)

(3) 對(duì)于關(guān)鍵業(yè)務(wù)請(qǐng)求，可以通過增大排隊(duì)隊(duì)列長度來提高接通率。

在教學(xué)過程中，我們還結(jié)合其他更加復(fù)雜的通信網(wǎng)絡(luò)介紹排隊(duì)模型。學(xué)生學(xué)習(xí)后，不在感覺像學(xué)純數(shù)學(xué)一樣枯燥，并對(duì)排隊(duì)論應(yīng)用于實(shí)踐充滿興趣，同時(shí)也有同學(xué)嘗試將排隊(duì)論知識(shí)應(yīng)用于金融和優(yōu)化管理中，取得較好效果。

5小結(jié)

從本文的分析可以看出，在計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)研究生數(shù)學(xué)教學(xué)中，不能單純地講解數(shù)學(xué)證明和簡單地計(jì)算人為構(gòu)造的例子和習(xí)題。簡單的數(shù)學(xué)學(xué)習(xí)學(xué)生并不能很好地了解這些數(shù)學(xué)知識(shí)在工程上的來源以及所能解決的具體應(yīng)用問題。在教學(xué)中，我們嘗試將工程化應(yīng)用與數(shù)學(xué)教學(xué)相結(jié)合，一方面使學(xué)生對(duì)隨機(jī)過程與排隊(duì)輪本身知識(shí)體系和思維方式有了更深的理解，另一方面使他們更容易找到如何利用所學(xué)數(shù)學(xué)知識(shí)進(jìn)行科學(xué)研究的感覺。很多學(xué)生能做到舉一反三，將所學(xué)知識(shí)應(yīng)用到不同情形下的計(jì)算機(jī)應(yīng)用中。

參 考 文 獻(xiàn)

[1] 劉次華. 隨機(jī)過程(第2版)[M]. 武漢:華中科技大學(xué)出版社，2003:23，27.

[2] 徐明，丁宏，陳純. 基于系統(tǒng)調(diào)用宏的馬爾可夫鏈入侵檢測(cè)模型[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版)，2005，(2).

[3] 唐應(yīng)輝，唐小我. 排隊(duì)論-基礎(chǔ)與應(yīng)用[M]. 成都:電子科技大學(xué)出版社，1999:65，74.[4] 徐昌彪，鮮永菊. 計(jì)算機(jī)網(wǎng)絡(luò)中的擁塞控制與流量控制[M]. 北京:人民郵電出版社，2007:211，2

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文