工程化教學思想在隨機過程與排隊論課程中的體現

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

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

關鍵詞：隨機過程；排隊論；工程應用

中圖分類號：G642 文獻標識碼：B

1引言

當前計算機科學技術發展非常迅猛，而計算機科學的研究也是日新月異。在計算機科學研究中，一些最基本的研究工具必不可少，例如對算法的推導，優化方案設計等。因此在計算機科學研究生教學階段，有必要將科學研究中需要的一些基礎知識開設為必修課程。在具體教學過程中，則體現為一門門的數學課程或基本的物理課程。

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

在實際的教學過程中，許多院校多采用數學專業教師編寫的《隨即過程》和《排隊論》這兩本教材。由于數學專業教師比較重視嚴謹的理論證明以及邏輯分析，在書中對這些知識是如何產生，以及在計算機科學中如何應用卻涉及不多。計算科學與技術專業的學生學后多感覺目的性不強，也導致對知識理解不深。本文將通過若干具體例子，列舉結合工程應用講述隨機過程與排隊論知識的方法，實際教學效果表明，結合工程化應用將很大程度地幫助學生理解并應用本門課程知識。

2結合信號處理講述隨機過程相關概念

在講述該概念過程中，大多人為構造一些隨機過程的例子，計算相關函數和互相關函數。學生一般都能理解如何計算相關函數和互相關函數。此后，隨機課程教學將轉入馬爾科夫過程，此概念就未再涉及。學生學習后，并不了解這個概念的實際意義和如何應用這個概念。在教學中，我們將討論運用去相關的方法進行盲信號分離。

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

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

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

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

3結合信息安全講述馬爾科夫過程

例2在隨機過程中有一個重要的概念稱為馬氏鏈[1]。定義如下：設{X(n)，n=0，1，2，…}為隨機序列，狀態空間E={0，1，2，…}。如果對于任意非負整數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，…}為離散參數馬爾可夫鏈，簡稱馬氏鏈。設{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時刻的k步轉移概率。特別地，k=1時，

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

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

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

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

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

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

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

在結合信息安全中主機入侵檢測工程應用講述馬爾科夫鏈后，許多學生舉一反三思考了將馬爾科夫鏈用于網絡入侵檢測，金融序列分類等等。從這里可以看出，結合工程應用講述隨機過程，將對于學生掌握理論知識并靈活運用這些知識有很重要的幫助。

4結合計算機網絡講述排隊論

研究排隊現象的目的是：通過對排隊系統中概率規律的研究，使系統達到最優設計和最優控制，以最小費用實現系統的最大效益。

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

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

， .

相應地我們能計算平均對長、平均等待對長、平均等待時間、 平均逗留時間等。在傳統的排隊論教材中，再講述了如何計算參數后，一般都舉一些簡單的例子計算相關參數。針對計算機科學專業學習排隊論重在應用的特點，我們講述了該系統在計算機網絡流量控制模型設計中的應用。

只要存在“Client/Server”的環境，就可以采用排隊模型進行分析。在一個基于Client/Server模型的計算機應用系統中，非常適合采用排隊論M/M/c:N/∞/FCFS模型來進行流量控制，當Client請求超過Server設計容量時，能避免Server的負荷惡性增長，確保系統能提供設計容量的服務。如圖2所示[4]。

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

(1) 在某種業務請求流量下，為獲得需要的接通率，我們可以計算出合適的隊列長度。

(2) 在大業務量情況下，如果限定逗留時長，可計算出一個合適的排隊隊列長度，當排隊長度超過該值時，業務請求再繼續排隊就沒有意義。(比如設定超時退出機制的環境)

(3) 對于關鍵業務請求，可以通過增大排隊隊列長度來提高接通率。

在教學過程中，我們還結合其他更加復雜的通信網絡介紹排隊模型。學生學習后，不在感覺像學純數學一樣枯燥，并對排隊論應用于實踐充滿興趣，同時也有同學嘗試將排隊論知識應用于金融和優化管理中，取得較好效果。

5小結

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

參 考 文 獻

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

[2] 徐明，丁宏，陳純. 基于系統調用宏的馬爾可夫鏈入侵檢測模型[J]. 浙江大學學報(工學版)，2005，(2).

[3] 唐應輝，唐小我. 排隊論-基礎與應用[M]. 成都:電子科技大學出版社，1999:65，74.[4] 徐昌彪，鮮永菊. 計算機網絡中的擁塞控制與流量控制[M]. 北京:人民郵電出版社，2007:211，2

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文