黃玉蕾

摘 要：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)一門重要的專業(yè)基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程中各種算法思想包含了數(shù)學(xué)思維方法，通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，培養(yǎng)數(shù)學(xué)分析能力，同時參與數(shù)學(xué)建模過程，訓(xùn)練數(shù)據(jù)結(jié)構(gòu)算法的編程能力，二者相輔相成。本文以數(shù)學(xué)建模的中研究生錄取問題和跟導(dǎo)師之間的雙向選擇問題作為主要討論對象，將其轉(zhuǎn)化為0-1數(shù)據(jù)結(jié)構(gòu)問題進(jìn)行分析討論。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)； 數(shù)學(xué)建模； 課程改革； 教學(xué)方法

【分類號】G633.6

1 數(shù)學(xué)建模的特點(diǎn)

數(shù)學(xué)建模用數(shù)學(xué)語言描述實(shí)際現(xiàn)象的過程[1]。數(shù)學(xué)建模是聯(lián)系數(shù)學(xué)與實(shí)際問題的橋梁，尤其在工程界格外重視，成為科技工作者的必備重要能力之一。數(shù)學(xué)建模的教學(xué)本身是一個不斷探索、不斷創(chuàng)新、不斷完善和提高的過程。改變了過去以教師為中心、以課堂知識講授為主的傳統(tǒng)教學(xué)模式，數(shù)學(xué)建模課程創(chuàng)建了一個新的指導(dǎo)思想——以實(shí)驗(yàn)室為基礎(chǔ)、以學(xué)生為中心、以問題為主線、以培養(yǎng)能力為目標(biāo)來組織教學(xué)工作，通過教學(xué)使學(xué)生了解利用數(shù)學(xué)理論和方法分析和解決問題的全程，提高他們分析問題和解決問題的能力。使學(xué)生經(jīng)常性的用數(shù)學(xué)去思考問題，利用計(jì)算機(jī)解決問題。

2 數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)建模

數(shù)學(xué)建模的基本思想方法是利用數(shù)學(xué)知識解決實(shí)際問題。而數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)專業(yè)的重要的專業(yè)基礎(chǔ)課程，有大量抽象的數(shù)學(xué)概念和理論知識[2]。在教學(xué)過程中，將數(shù)據(jù)結(jié)構(gòu)的算法融入到數(shù)學(xué)建模思想中，使學(xué)生將數(shù)學(xué)的理論和方法用計(jì)算機(jī)算法程序?qū)崿F(xiàn)，這樣既可以將培養(yǎng)學(xué)生的編寫程序的能力又能夠提供數(shù)學(xué)的邏輯關(guān)系，增強(qiáng)了學(xué)生的動手能力，教學(xué)效果十分明顯。

3 數(shù)學(xué)建模下數(shù)據(jù)結(jié)構(gòu)教學(xué)討論

本文根據(jù)研究生錄取問題和跟導(dǎo)師之間的雙向選擇問題作為主要討論對象，將此問題轉(zhuǎn)化為分別轉(zhuǎn)化成層次分析問題和線性規(guī)劃中的0-1 規(guī)劃問題[3]。

3.1 數(shù)學(xué)建模問題

首先建立研究生錄取遞階層分次結(jié)構(gòu)模型，定義權(quán)重比例為0.6：0.4，對每個學(xué)生的綜合評價分?jǐn)?shù)進(jìn)行歸納，從15名候選同學(xué)中選出10位研究生。其次，用0-1 規(guī)劃模型進(jìn)行學(xué)生和導(dǎo)師之間的雙向選擇。建立目標(biāo)函數(shù)和約束條件，用lingo軟件求得：導(dǎo)師6分別和學(xué)生2、學(xué)生5以及學(xué)生6和學(xué)生12配對，導(dǎo)師3分別和學(xué)生3、學(xué)生9以及學(xué)生15配對，導(dǎo)師4分別和學(xué)生1、學(xué)生8配對，導(dǎo)師9和學(xué)生4配對。

用0-1 規(guī)劃模型[3]學(xué)生和導(dǎo)師之間的雙向選擇。

1、導(dǎo)師的學(xué)術(shù)水平評價：

導(dǎo)師的學(xué)術(shù)水平是四個方面體現(xiàn)的，分別為發(fā)表論文數(shù)、論文檢索數(shù)、編（譯）著作數(shù)、科研項(xiàng)目數(shù)。通過查閱資料得出對研究生導(dǎo)師的考核標(biāo)準(zhǔn)的分析，對于導(dǎo)師的學(xué)術(shù)水平的衡量，以上四個方面的重視程度是不同的，其中最看重的是論文檢索數(shù)、其次是科研項(xiàng)目數(shù)、對發(fā)表論文數(shù)和編（譯）著作數(shù)看的相對較低。故權(quán)值設(shè)定為：

對于導(dǎo)師的學(xué)術(shù)水平各項(xiàng)指標(biāo) ， ， ， ，是通過具體數(shù)目給出的，在此同時采用極差變換法，即由下面公式得到各導(dǎo)師的相應(yīng)各指標(biāo)量化值：

記導(dǎo)師學(xué)術(shù)水平向量為 ，采用下面公式得到對第 個導(dǎo)師的綜合水平的評價 ，即：

2、導(dǎo)師對學(xué)生的滿意度：

根據(jù)8個專家對每一個學(xué)生的評價，轉(zhuǎn)換為相應(yīng)的數(shù)值4，3，2，1，然后用求算術(shù)平均的方法，得到每個學(xué)生的每項(xiàng)特長的綜合評分，用這個綜合評分與每位學(xué)生的五項(xiàng)特長的期望要求比較得出差異矩陣H，依據(jù)差異矩陣的數(shù)值 來劃分等級，具體做法為找出最大值和最小值確定長度區(qū)間，再除以欲劃分的等級數(shù)目，得到每個等級之間的等級長度：

用（很滿意，滿意，基本滿意，不滿意）來表示，由此得到每位導(dǎo)師對每位同學(xué)的各項(xiàng)特長的評價。

不滿意：數(shù)值介于區(qū)間：

基本滿意：數(shù)值介于區(qū)間：

滿意：數(shù)值介于區(qū)間：

很滿意：數(shù)值介于區(qū)間：

這四個等級就構(gòu)成模糊集，取其對應(yīng)的數(shù)值為1，2，3，4.

不考慮學(xué)生所報(bào)專業(yè)志愿前提下對學(xué)生的評價，考慮到導(dǎo)師選擇學(xué)生還是要看學(xué)生的志愿。所以得出專業(yè)、導(dǎo)師和學(xué)生之間的可分配關(guān)系如圖1所示。

3、學(xué)生對導(dǎo)師的滿意度

學(xué)生對導(dǎo)師的選擇，主要是根據(jù)學(xué)生自己的專業(yè)發(fā)展意愿，導(dǎo)師的基本情況和導(dǎo)師對學(xué)生的期望要求。集中體現(xiàn)在專業(yè)志愿和導(dǎo)師的學(xué)術(shù)水平上，導(dǎo)師的學(xué)術(shù)水平是客觀存在的，可以用導(dǎo)師的學(xué)術(shù)水平評價 來衡量，不同的學(xué)生對導(dǎo)師的滿意程度可以人為是取決于導(dǎo)師所從事的研究方向。類似的，可以通過加權(quán)方法來處理，即當(dāng)導(dǎo)師研究方向與自己的第一志愿相同時，賦權(quán)值為1；當(dāng)導(dǎo)師研究方向與自己的第二志愿相同是，賦權(quán)值為0.6；當(dāng)導(dǎo)師研究方向與自己的志愿全不相同是，賦權(quán)值為0，其計(jì)算公式為：

其中志愿權(quán)值 取法同上，這時得到第 個學(xué)生對第 個導(dǎo)師的滿意度

4、雙方滿意度的綜合評價

確定了被錄取的學(xué)生和導(dǎo)師雙方對彼此的滿意度，我們認(rèn)為學(xué)生和導(dǎo)師彼此的滿意度的和最大，兩者的差越少，兩者的相互選中的可能性越大，又有滿意度均為正，所以這里采用幾何平均的方法來綜合兩者的滿意度，定義導(dǎo)師和學(xué)生兩兩之間的相互滿意度為：

3.2 數(shù)據(jù)結(jié)構(gòu)解決方法

在各個導(dǎo)師所帶學(xué)生數(shù)量沒有限制而學(xué)生只能選擇一個導(dǎo)師的情況下，為了達(dá)到一種選擇方案使得師生雙方的滿意度達(dá)到最大，我們可以把原問題轉(zhuǎn)化成0-1整數(shù)規(guī)劃問題，設(shè)決策變量為 （ 代表導(dǎo)師， 代表錄取學(xué)生）

目標(biāo)函數(shù)：

約束條件：

其中：

應(yīng)用Lingo軟件對上面整數(shù)規(guī)劃問題求解得到目標(biāo)值為7.047270，此時導(dǎo)師與學(xué)生的選擇方案為如圖2所示。

其中：導(dǎo)師6有四位學(xué)生，分別為學(xué)生2和學(xué)生5以及學(xué)生6和學(xué)生12，導(dǎo)師3有三位學(xué)生，分別為學(xué)生3和學(xué)生9以及學(xué)生15，導(dǎo)師4有兩位學(xué)生，分別是學(xué)生1和學(xué)生8，導(dǎo)師9有一位學(xué)生，為學(xué)生4。

3.3 0-1問題數(shù)據(jù)結(jié)構(gòu)教學(xué)方法。

根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，將0-1問題設(shè)置為以下講解方法。

1、實(shí)驗(yàn)內(nèi)容：

設(shè)有一個背包可以放入的物品的重量為S，現(xiàn)有N件物品，重量分別為W1，W2，W3……Wn。問能否從這n件物品中選擇若干件放入此包中，使得放入的物品的重量之和正好為S。

2、實(shí)驗(yàn)的目的：

深入了解棧和隊(duì)列的特性，以便在實(shí)際問題背景下靈活應(yīng)用，同時還將鞏固對這兩中結(jié)構(gòu)的構(gòu)造方法的掌握，接觸較復(fù)雜問題的遞歸算法的設(shè)計(jì)。

3、實(shí)驗(yàn)設(shè)計(jì)思想：

（1）遞歸策略

在該問題中物品質(zhì)量W[n]和包所能承受的最大重量maxweight都是又用戶自己任意定義的，在遞歸實(shí)現(xiàn)的過程中用到一個棧來實(shí)現(xiàn)。

（2）非遞歸策略

非遞歸策略思想的實(shí)現(xiàn)與遞歸策略類似，只是直接用定義一個棧來實(shí)現(xiàn)，同樣的物品質(zhì)量W[n]和包所能承受的最大重量maxweight都是又用戶自己任意定義的。

4 總結(jié)

通過這道題，使我們鞏固了平時所學(xué)的知識，對數(shù)據(jù)結(jié)構(gòu)中遞歸與非遞歸的思想有了進(jìn)一步的理解和認(rèn)識，更重要的是通過這個題目使我們更多的了解到數(shù)據(jù)結(jié)構(gòu)在實(shí)際問題中的廣泛應(yīng)用，同時在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中融入數(shù)學(xué)建模思想方法，能夠很好地引導(dǎo)學(xué)生在學(xué)習(xí)的過程中善于發(fā)現(xiàn)問題、提出問題及解決問題，為后續(xù)課程打下堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)

[1] 溫長剛，數(shù)學(xué)建模與“數(shù)據(jù)結(jié)構(gòu)”課堂教學(xué)關(guān)系的探討與分析[J]電腦知識與技術(shù) 2014.8

[2] 景妮琴，淺談數(shù)學(xué)在數(shù)據(jù)結(jié)構(gòu)教學(xué)中的應(yīng)用[J]山西師范大學(xué)學(xué)報(bào) 2010.12

[3] 吳永輝，王建德，算法設(shè)計(jì)編程實(shí)驗(yàn)[M]北京：機(jī)械工業(yè)出版社 2013.6