談專業(yè)競賽對教學(xué)實(shí)踐改革的促進(jìn)作用

程玉勝 程樹林 龐淑芳

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

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

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

1引言

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

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

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

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

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

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

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

第二步:布置相應(yīng)的“情境”,要求學(xué)生去分析問題,即“建模→設(shè)計(jì)算法→選擇存儲(chǔ)結(jié)構(gòu)”;

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

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

例如關(guān)于基數(shù)排序算法應(yīng)用到數(shù)據(jù)分類中。在粗糙集理論中,對象的劃分求解是通過不可分辨關(guān)系實(shí)現(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è)競賽實(shí)例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

第三步:在每個(gè)模糊詞相應(yīng)的范圍中選擇一個(gè)值;

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

4專業(yè)競賽對實(shí)踐教學(xué)的促進(jìn)作用

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

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

5結(jié)論

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

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

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

參考文獻(xià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] 錢萌,程玉勝,程樹林. 基于分治策略求解方程根的個(gè)數(shù)[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(9):41-43.

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

[4] 江效堯,江克勤.“協(xié)作式學(xué)習(xí)”理論在“數(shù)據(jù)結(jié)構(gòu)”實(shí)驗(yàn)教學(xué)中的實(shí)踐[J]. 安慶師范學(xué)院學(xué)報(bào),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