程玉勝 程樹林 龐淑芳

摘要:本文結(jié)合“數(shù)據(jù)結(jié)構(gòu)”實踐教學,探討了高等教育大眾化教育背景下計算機專業(yè)人才培養(yǎng)模式。通過介紹近年來我校參加的計算機專業(yè)競賽,說明改革實踐教學模式的必要性。

關(guān)鍵詞:實踐教學;競賽;基數(shù)排序;最小生成樹;哈希函數(shù)

中圖分類號:G642 文獻標識碼:A

1引言

近年來,隨著高等教育規(guī)模的不斷擴大,我國高等教育已經(jīng)進入大眾化發(fā)展階段,社會對計算機專業(yè)人才的需求呈現(xiàn)多樣化的特點。在這種背景下,教育部高等學校計算機科學與技術(shù)教學指導委員會制定了專業(yè)規(guī)范的“三種類型、四個方向”,其中計算機工程方向是工程型人才培養(yǎng)模式之一。根據(jù)這樣的專業(yè)規(guī)范,探索大眾化高等教育階段如何培養(yǎng)高質(zhì)量的計算機專業(yè)人才,是計算機教育者面臨的一大課題。根據(jù)教育部質(zhì)量工程建設的指導思想以及計算機工程方向人才建設的需求,結(jié)合“數(shù)據(jù)結(jié)構(gòu)”課程,本文主要探討了專業(yè)競賽對計算機工程方向人才培養(yǎng)的促進作用。

近五年來,我們按照“以學生為主體,注重對學生綜合能力的培養(yǎng)”為教學思路,在幫助學生掌握計算機程序設計基本理論和方法的基礎上,為了充分利用有限的教學時間,組織好實驗課堂教學,完成教學目標,課程組在實驗教學中引入了應用背景驅(qū)動的學習策略和方法,探討和實踐了“數(shù)據(jù)結(jié)構(gòu)”應用背景驅(qū)動的課程實踐教學方法的改革。主要包括:(1)分層教學法,根據(jù)學生的接受能力,充分發(fā)揮不同層次學生能動性,循序漸進的開展實驗任務。(2)創(chuàng)造學習“情境”,將新知識點與實際應用聯(lián)系起來,建立學習者知識的內(nèi)外聯(lián)系。(3)將應用背景驅(qū)動的教學策略應用到組織部分優(yōu)秀學生參加計算機仿真,程序設計大賽等,在提高學生的理論學習成績與實際操作能力方面收到良好效果。

2數(shù)據(jù)結(jié)構(gòu)中的實踐教學

“數(shù)據(jù)結(jié)構(gòu)”課程是計算機科學的算法理論基礎和軟件設計的技術(shù)基礎,主要研究信息的邏輯結(jié)構(gòu)及其基本操作在計算機中的表示和實現(xiàn)。學習本課程的過程也是進行復雜程序設計的訓練過程,要求學生書寫的程序結(jié)構(gòu)清楚、正確易讀,符合軟件工程的規(guī)范。上機實習著眼于原理與應用的結(jié)合,使學生學會如何把書本知識用于解決實際問題,培養(yǎng)軟件工作所需要的動手能力;同時還能使書本知識變活,進一步深化理解和靈活掌握教學內(nèi)容。通過上機實驗可以培養(yǎng)學生分析具體問題、建立數(shù)學模型并解決實際問題的能力,培養(yǎng)學生創(chuàng)新意識和提高動手實踐的能力。

“數(shù)據(jù)結(jié)構(gòu)”課程算法很多,由于受到教學時間的限制,要求全部實現(xiàn)不大可能,我們共提煉出8個實驗,要求學生在實驗課時中必須完成,也是基礎層中設置的基本實驗。而為了進一步培養(yǎng)學生分析問題、解決實踐問題的能力,我們又構(gòu)思了一些知識點的應用“情境”,通過引導和分析,進一步提高學生的動手能力。最后通過選拔部分學生參加專業(yè)競賽,激發(fā)學生的創(chuàng)新思維。

因此,在“數(shù)據(jù)結(jié)構(gòu)”實踐教學中,主要采取以下步驟進行:

第一步:要求學生掌握基本算法及其實現(xiàn);

第二步:布置相應的“情境”,要求學生去分析問題,即“建?！O計算法→選擇存儲結(jié)構(gòu)”;

第三步:進行“性能分析→算法模擬→優(yōu)化模型”;

第四步:編程調(diào)試解決問題。

例如關(guān)于基數(shù)排序算法應用到數(shù)據(jù)分類中。在粗糙集理論中,對象的劃分求解是通過不可分辨關(guān)系實現(xiàn)的。例如表1中U/IND(a)={{x1,x3},{x2,x4,x5}}。

通過基數(shù)排序算法,可以求出U/IND(a,b,c),過程如下:

第1趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x4->x5<-End[2]

第1趟“收集”結(jié)果:

x1(111)-->x3(111)-->x2(222)-->x4(232)-->x5(222)

第2趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x5<-End[2]

Front[3]->x4<-End[3]

第2趟“收集”結(jié)果:

x1(111)-->x3(111)-->x2(222)-->x5(222)-->x4(232)

第3趟“分配”:

Front[1]->x1->x3<-End[1]

Front[2]->x2->x5->x4<-End[2]

第3趟“收集”結(jié)果:

x1(111)-->x3(111)-->x2(222)-->x5(222)-->x4(232)

數(shù)據(jù)分類結(jié)果(見圖1):{ x1 ,x3 },{ x2 ,x5 },{ x4 }

3專業(yè)競賽實例分析

我們組織了部分優(yōu)秀學生前后參加了兩屆全國計算機仿真大獎賽,均獲得好成績。在2004年“首屆全國計算機仿真大獎賽”中,針對競賽的內(nèi)容,我們將hash函數(shù)的方法,用計算機仿真的方法成功地解決了一元高次方程的求解,獲得了全國第二名的成績。在2006年“第二屆全國計算機仿真大獎賽”中,將數(shù)據(jù)結(jié)構(gòu)圖的優(yōu)化問題應用到關(guān)于控制理論中共振點的求解方法,獲得了全國二等獎,以及在成功利用數(shù)據(jù)結(jié)構(gòu)中表的查找操作后,關(guān)于信息檢索的體育館買票智能推薦系統(tǒng)獲得全國三等獎。另外,關(guān)于最短路徑的優(yōu)化問題在“第二屆全國計算機仿真大賽”中成功參賽。下面簡單介紹數(shù)據(jù)結(jié)構(gòu)中相關(guān)知識點“情境”構(gòu)造。

3.1哈希函數(shù)的“情境”構(gòu)造

下面是“第一屆全國計算機仿真大獎賽”參賽并獲得全國第二名作品(指導老師:程玉勝),問題描述如下:

已知一個n元高次方程: ,x1,x2,…,xn是未知數(shù),k1,k2,…,kn是系數(shù),p1,p2,…,pn是指數(shù),取值為正數(shù);且方程中的所有數(shù)均為整數(shù);假設未知數(shù)1≤ xi ≤M(i=1,2,……n),求這個方程整數(shù)解的個數(shù)(方程整數(shù)解的個數(shù)小于231)。其中約束條件1≤n≤6;1≤M≤150;

從方程的已知條件可知,此方程在最壞的情況下有6個未知數(shù),每個未知數(shù)xi的取值范圍最大為M。如果采用簡單的枚舉方法來實現(xiàn),那么它的時間復雜度是O(M6)。假設未知數(shù)個數(shù)為n,未知數(shù)的值不超過M,F(n)表示二分法后解的最大規(guī)模,因此該問題的時間復雜度主要集中在利用哈希技術(shù)存儲左表達式A所有可能取值到 數(shù)組對應位置,對應時間復雜度為O( )。而右表達式值B利用哈希查找方法進行定位,時間復雜度為O( )。因此總的時間復雜度T(n)為。考慮A式:的可能取值并利用哈希技術(shù)來存放A式的值s,考慮到s在最壞的情況下有1503=3375000個不同的取值,因此定義長度為3375000的線性表來構(gòu)造哈希表,并令哈希數(shù)取3375000。并且考慮到相同的s值可能出現(xiàn)多次,為了統(tǒng)計次數(shù)將線性表的存儲結(jié)構(gòu)定義為兩個域:一個存放s值,另一個統(tǒng)計這個值出現(xiàn)的次數(shù)。

在實驗中選擇“除余法”構(gòu)造了哈希函數(shù):由于哈希表的長度為3375000,因此可取p=3375000令h(k)= k mod p;當不同的s值具有相同的哈希值時,便會產(chǎn)生沖突,可采用線性重新散列技術(shù)解決沖突。令數(shù)組元素個數(shù)為p,則當h(k) 位置已存儲有元素時,依次探查(h(k)+i) mod p,i=1,2,3……,直到找到空的存儲單元為止。

例1給定n=4,M=150k1=k2=-1,k3=k4=1,pi=2(i=1,2,3),p4=3,該n元高次方程解的個數(shù)通過計算機仿真后,結(jié)果為5167,如圖2所示。表2給出該方程所有可能含對約束條件檢測的仿真結(jié)果:

3.2最短路徑算法“情境”構(gòu)造

下面是“第二屆全國計算機仿真大獎賽”成功參賽作品(指導老師:程樹林),問題描述如下:

某省的七個城市需要架設通信網(wǎng)絡系統(tǒng),以連接這七個城市,每兩個城市之間的距離如表3所示。考慮地理環(huán)境的影響,綜合考慮各城市之間的距離和每公里修建通信網(wǎng)絡的費用,各個城市之間修建網(wǎng)絡每公里的費用可用于10000元之間的比較如表4所示。試問如何架設通信網(wǎng)絡,使總費用最小?

在七個城市之間架設通信網(wǎng)絡系統(tǒng),要使任何兩個城市之間都能相互通信,最少需要6(7-1=6)條線路。總共有7*6/2=21條通信線路可供選擇,本題要求所架設的通信線路總費用最少,也就是在21條線路中選擇6條線路,所選擇的6條線路必須使七個城市之間可以相互通信,并且所消耗的費用是最小的?，F(xiàn)在要求架設通信網(wǎng)絡的最低耗費問題也就相應地轉(zhuǎn)化成求相對應的無向完全圖的最小生成樹的問題。另外,九個模糊詞:“完全是、可認為是、差不多是、非常接近、十分接近、很接近、比較接近、大致接近、相當接近”,我們并不能確定這些模糊詞的精確值,而且程序中并沒有約定它們具體的值,我們可以嘗試采取如下方案(圖3):

第一步:給這九個模糊詞指定一個大致的取值范圍,如(0.8～1);

第二步:用戶可以根據(jù)自己對模糊詞強弱的理解或者根據(jù)實際需要,給每個模糊詞輸入一個具體的范圍;

第三步:在每個模糊詞相應的范圍中選擇一個值;

第四步:根據(jù)上面所輸入的參數(shù)計算各邊的權(quán)值(每兩個城市之間線路的費用),即長度*模糊詞量化值。

4專業(yè)競賽對實踐教學的促進作用

2004年首屆全國計算機仿真大賽,我們選拔了最優(yōu)秀的學生參賽,通過15天的艱苦奮戰(zhàn),在大賽中取得了全國第二名的優(yōu)異成績。2006年,學生參賽熱情空前高漲,最后通過選拔,組成了5支參賽隊伍、每隊3人,并且為每支代表隊配了一名指導老師。我們邀請了部分優(yōu)秀老師對學生進行參賽前的集訓,這次集訓為大賽取得更好的成績打下了一定基礎。在老師的精心指導下,15天后學生完成了作品,最終程玉勝老師指導的作品獲得了全國二等獎。

計算機仿真大賽,不僅教會了學生集體攻關(guān)的能力,培養(yǎng)了學生的團隊精神,更重要的還培養(yǎng)了學生的創(chuàng)新思維和動手能力。同時,對實踐指導老師提出了更高的要求,要求把創(chuàng)新的思想、計算機工程方法加入對實踐教學模式和內(nèi)容的改革中。

5結(jié)論

通過專業(yè)競賽,充分調(diào)動了同學們學習的自覺性,激發(fā)了學生分析問題、解決問題能力。以上成果與我院近幾年來開展的一系列“要求培養(yǎng)學生動手能力和創(chuàng)新思維”活動是分不開的,是我院在高等教育大眾化背景下面向計

算機工程型人才培養(yǎng)模式的一次大探索。

致謝:感謝我校計算機系04屆葉敏、汪智華、齊樂,06屆劉偉、袁緒廣、劉玉龍,07屆吳萍,08屆瞿鵬和程樹林、錢萌老師等參與的專業(yè)競賽和相關(guān)“情境”材料的編寫和程序設計。

參考文獻:

[1] 程玉勝,龐淑芳,章曉良. Application-Driven Background Model about Hierarchical Practice Learning in Data Structure[C]. International Symposium On Education And Computer Science(ECS2009),Wuhan,2009:274-277.

[2] 錢萌,程玉勝,程樹林. 基于分治策略求解方程根的個數(shù)[J]. 計算機技術(shù)與發(fā)展,2006,16(9):41-43.

[3] 嚴蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學出版社,1997.

[4] 江效堯,江克勤.“協(xié)作式學習”理論在“數(shù)據(jù)結(jié)構(gòu)”實驗教學中的實踐[J]. 安慶師范學院學報,2006,12(04):25-27.

Discuss about Special Competition to Accelerate the Experiment Learning Reform

CHENG Yu-sheng, CHENG Shu-lin, PANG Shu-fang

(Dep. of Computer, Anqing Teachers College, Anqing 246011, China)

Abstract: This paper discusses the model of training professional man for computer under popular high education combined experiment learning of data structure. Our school takes an active part in some computer competition which shows that it is necessary to reform our experiment learning.

Key words: experiment learning; competition; radix sort; minimum cost spanning tree; hash function