王桂平 馮 睿

摘要:本文分析了圖論教學的重要性及圖論課程教學現(xiàn)狀,針對應(yīng)用型人才培養(yǎng)目標和計算機專業(yè)的特點,對圖論課程教學提出了一些改革思路,主要思想是通過程序設(shè)計競賽激發(fā)學生的學習興趣和積極性,并通過在線程序?qū)嵺`理解和實現(xiàn)圖論算法,讓學生掌握圖論算法及其應(yīng)用。最后總結(jié)了一些有效的課堂教學和實踐教學方法。

關(guān)鍵詞:圖論;計算機專業(yè);程序設(shè)計競賽;在線實踐

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

1圖論及圖論教學

圖論(Graph Theory)是數(shù)學的一個重要分支,以“圖”為研究對象。圖論中的圖是由若干個給定的頂點及若干條連接兩個頂點的邊所構(gòu)成的圖形。這種圖形通常用來描述某些事物之間的某種特定關(guān)系:用頂點代表事物,用連接兩個頂點的邊表示相應(yīng)兩個事物間具有這種關(guān)系。這種圖提供了一個很自然的數(shù)據(jù)結(jié)構(gòu),可以對自然科學和社會科學中許多領(lǐng)域的問題進行恰當?shù)拿枋龌蚪?因此圖論研究越來越得到這些領(lǐng)域的專家和學者的重視。

基于圖論的重要性,目前很多高校課程都涉及到圖論知識,如離散數(shù)學、數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計、運籌學、組合數(shù)學、拓撲學、網(wǎng)絡(luò)優(yōu)化等。越來越多的大學將圖論單獨作為一門課程來開設(shè),作為數(shù)學、計算機科學與技術(shù)、電子科學與技術(shù)、管理學等專業(yè)本科生和研究生的必修課或選修課。

圖論的教學具有如下特點:

(1) 概念、定理特別多,定理的證明通常都很難,在一定程度上造成教學比較難而且枯燥。

(2) 圖論里很多問題都有具體的應(yīng)用背景,但通常難以轉(zhuǎn)換成圖論中的模型,從而求解比較難,所以學生對圖論課程有一定的興趣,但往往會望而卻步。

(3) 圖論中的算法豐富,幾乎每個應(yīng)用問題都有不同復雜度的算法。例如,最短路徑問題常用的算法有Dijkstra算法、Bellman-Ford算法、SPFA算法、Floyd算法,如果要用程序?qū)崿F(xiàn)這些算法并求解實際問題,對學生的程序設(shè)計和算法分析能力有比較高的要求。

(4) 圖論課程對鍛煉計算機科學與技術(shù)等專業(yè)學生的算法分析與設(shè)計能力有很好的作用。

作者調(diào)查發(fā)現(xiàn),國內(nèi)高校圖論課程的教學或者是側(cè)重于完整的圖論知識體系介紹、復雜的圖論定理證明,或者是側(cè)重于從應(yīng)用數(shù)學的角度介紹圖論在各領(lǐng)域的應(yīng)用。我們在教學中發(fā)現(xiàn),許多學生(特別是計算機專業(yè)的學生)在學習圖論時,都不滿足于圖論算法的手工和草稿紙演算,迫切地想知道如何用程序來實現(xiàn)圖論中的算法,以及如何用這些算法思想求解實際問題,這就對計算機專業(yè)的圖論教學提出了新的要求。

2教學改革背景

隨著我國的高等教育進入大眾化階段,許多高校將人才培養(yǎng)目標定位成應(yīng)用型人才的培養(yǎng)。這就要求高校培養(yǎng)的學生不僅具備扎實的專業(yè)知識,還要有過硬的應(yīng)用性知識。

對計算機科學與技術(shù)專業(yè)來說,應(yīng)用型人才的培養(yǎng)目標要求注重培養(yǎng)學生軟硬件系統(tǒng)的研發(fā)能力,強調(diào)學生對非計算機學科(專業(yè))知識的融會貫通,學生應(yīng)具備扎實的計算機基礎(chǔ)理論知識和較強的實踐能力。

發(fā)展應(yīng)用型教育,培養(yǎng)應(yīng)用型人才,應(yīng)該貫穿于整個教學活動中,包括專業(yè)設(shè)置、教學管理、課程設(shè)計、教學手段和方法以及教學制度建設(shè)等方面。

在這樣的背景下,我們在圖論教學中一直在思考以下幾個問題:

(1)“圖論算法實現(xiàn)及應(yīng)用”在我校是作為一門選修課開設(shè)的,如何讓學生在感受到圖論知識魅力的同時提高學習興趣,調(diào)動學生的學習積極性。

(2) 如何針對計算機專業(yè)學生設(shè)計合適的教學方法,以適應(yīng)他們的專業(yè)特點和專業(yè)發(fā)展方向。

(3) 如何設(shè)計新穎的實踐教學形式和內(nèi)容,引導和加強實踐教學,讓學生真正理解圖論算法思想并能編程實現(xiàn),靈活運用圖論算法求解各種應(yīng)用問題,以適應(yīng)應(yīng)用型人才培養(yǎng)的要求。

3圖論課程教學改革

3.1改革思路

針對圖論課程的教學現(xiàn)狀和應(yīng)用型人才培養(yǎng)的要求,我們嘗試按以下思路進行教學改革:以培養(yǎng)學習興趣入手,引導學生進入豐富的圖論知識領(lǐng)域;向?qū)W生闡述有具體應(yīng)用背景的圖論算法思想;側(cè)重圖論算法的復雜度分析和程序?qū)崿F(xiàn);通過在線實踐引導學生運用圖論算法求解問題。

為此,我們在充分調(diào)研和積極探索的基礎(chǔ)上,提出以下教學改革措施:(1)以大學生程序設(shè)計競賽這一學科競賽為驅(qū)動,激發(fā)學生的學習熱情和積極性。(2)以“在線實踐”這種新穎的實踐方式為導向,豐富課程的實踐教學并提高學生的實踐能力。(3)加強“程序與算法設(shè)計”課程群的建設(shè),構(gòu)建完整的、系統(tǒng)的知識體系。(4)做好教材建設(shè),編寫適合這種教學思路的圖論講義、教材和實驗指導書。

3.2以程序設(shè)計競賽激發(fā)學生的學習積極性

由美國計算機協(xié)會組織的ACM/ICPC國際大學生程序設(shè)計競賽已經(jīng)有30年的歷史了,中國大陸的高校在上世紀90年代中期陸續(xù)參賽,很多高校在總決賽中取得了優(yōu)異的成績。ACM/ICPC競賽在公平競爭的前提下,提供了一個讓大學生充分展示用計算機分析問題、解決問題的能力與才華的平臺。ACM/ICPC競賽鼓勵創(chuàng)造性和團隊協(xié)作精神,鼓勵在編寫程序時的開拓與創(chuàng)新。

近十年來,很多高校開始舉辦全校性的程序設(shè)計競賽,并逐漸發(fā)展成為全省(市)性質(zhì)的比賽,這極大地推動了這項學科競賽在中國大陸高校的開展。

圖論是這項程序設(shè)計競賽中重要的題目類型之一。圖的遍歷、活動網(wǎng)絡(luò)、最小生成樹、最短路徑、圖的行遍性問題、網(wǎng)絡(luò)流問題、匹配問題、圖的連通性、圖的著色等都有大量經(jīng)典的題目,幾乎涵蓋了圖論完整的知識體系。

例如,我們在舉辦競賽時曾經(jīng)出了這樣一道題:由M×N個方格組成的網(wǎng)格表示敵占區(qū),通訊員要從初始方格S出發(fā),送情報到達目標方格T,其他符號的含義如圖1所示。初始時,通訊員具有一定的體力。通訊員從某個方格出發(fā),到達上、右、下、左4個方向上的相鄰方格需要花費的時間和消耗的體力如圖1所示。另外,從目標方格的相鄰方格到達目標方格,花費時間1,消耗體力1。本題要求解的是:通訊員能否到達目標方格?如果能到達,所需最少的時間是多少(只需要保證到達目標方格時,通訊員的體力>0即可)。本題的求解要用到廣度優(yōu)先搜索算法。圖1中給出了一條花費時間最少為13的路線(初始體力為8),到達目標方格時剩余體力為1。

我們在教學中以這些題目為例闡述圖論算法思想、分析算法的復雜度并用程序?qū)崿F(xiàn),讓學生切實地理解算法思想、直觀地體會到算法的具體應(yīng)用,同時我們也布置相應(yīng)的題目作為練習題。這些題目的趣味性和挑戰(zhàn)性能吸引學生投入較多的時間和精力去完成,在豐富知識結(jié)構(gòu)的同時提高學生的程序設(shè)計和算法分析實踐能力。

3.3以在線實踐提升學生的程序?qū)嵺`能力

隨著ACM/ICPC程序設(shè)計競賽的推廣,各種在線程序評判(Online Judge,簡寫為OJ)網(wǎng)站也應(yīng)運而生,這為程序設(shè)計愛好者提供了一種新的程序?qū)嵺`方法:在線程序?qū)嵺`。

在線程序?qū)嵺`是指由OJ網(wǎng)站提供題目,學生在線提交程序,OJ網(wǎng)站的在線評判系統(tǒng)實時評判并反饋評判結(jié)果。這些題目一般具有較強的趣味性和挑戰(zhàn)性,評判過程和結(jié)果也公正及時,因此能引起學生的極大興趣。

學生可以根據(jù)OJ系統(tǒng)反饋回來的評判結(jié)果反復修改程序,直到最終收獲Accept(程序正確)。這不僅能培養(yǎng)學生獨立分析問題、解決問題的能力,而且每成功解決一道題目都能給學生帶來極大的成就感。

在教學中,我們以組織學生開發(fā)的OJ系統(tǒng)作為實踐教學平臺,該平臺主要起到了以下作用:(1)作為教學演示平臺。對課程中涉及到的算法都盡量用程序?qū)崿F(xiàn),并提交到OJ系統(tǒng)進行驗證和演示。(2)作為算法分析平臺。針對圖論算法豐富的特點,我們在教學中對同一個應(yīng)用問題采用不同算法實現(xiàn),并提交到OJ系統(tǒng),以測試程序的運行時間,讓學生直觀觀察到算法的優(yōu)劣。(3)作為實驗教學的平臺。在實驗課上,學生可以用程序求解練習題并提交到OJ系統(tǒng)驗證。(4)作為課程考核平臺。對圖論課程進行教學改革后,我們認為不適合采用筆試方式考核,因此采用在OJ系統(tǒng)上機考試的形式。這種考核方式過程更直觀、結(jié)果更客觀。

3.4以課程群建設(shè)推動知識體系的系統(tǒng)性構(gòu)建

教學改革后,圖論課程的教學目標定位為培養(yǎng)學生圖論算法分析、設(shè)計和應(yīng)用能力。這跟我們建設(shè)的“程序與算法設(shè)計”課程群的知識體系、知識目標、能力目標是吻合的,因此我們將圖論課程納入該課程群。

“程序與算法設(shè)計”課程群的知識體系設(shè)計為:程序設(shè)計思想和方法、數(shù)據(jù)結(jié)構(gòu)設(shè)計與運用、算法分析與設(shè)計、面向?qū)ο蟮能浖_發(fā)、圖論算法分析與應(yīng)用。為此,我們精選了6門課程組成該課程群,如圖2所示。

課程群的知識目標為:通過課程群中各門課程的學習,掌握基本的程序設(shè)計思想和方法;理解面向?qū)ο蟪绦蛟O(shè)計的思想并能熟練運用;理解各種數(shù)據(jù)結(jié)構(gòu)的原理和使用方法;熟練掌握常用算法分析和設(shè)計技巧,掌握常用算法的綜合運用;掌握系統(tǒng)分析與設(shè)計的基本方法。

課程群的能力目標為:掌握基本的程序設(shè)計、測試、調(diào)試能力;能運用面向?qū)ο蟪绦蛟O(shè)計思想和方法開發(fā)較大規(guī)模的軟件;能綜合運用各種數(shù)據(jù)結(jié)構(gòu)對軟件功能進行描述和建模;具備基本的數(shù)據(jù)結(jié)構(gòu)和算法分析和設(shè)計能力;能針對各種圖論應(yīng)用問題設(shè)計合理的算法并用程序?qū)崿F(xiàn);在軟件開發(fā)中運用系統(tǒng)觀點,對應(yīng)用問題進行初步的分析和設(shè)計;在實踐活動中鍛煉毅力,樹立克服困難的信心,培養(yǎng)競爭和創(chuàng)新的意識。

圖論算法實現(xiàn)及應(yīng)用課程是第四學期作為選修課開設(shè)的。在此之前,學生通過前期課程的學習,已經(jīng)掌握了基本的程序設(shè)計思想、方法以及基本的數(shù)據(jù)結(jié)構(gòu)使用,該課程與算法分析與設(shè)計課程同步開設(shè)。

圖論課程在課程群中利用其算法豐富、應(yīng)用問題多而廣的特點,給學生提供算法分析與設(shè)計的實踐機會。通過圖論課程的學習,學生不僅能掌握豐富的圖論知識,程序設(shè)計、算法分析能力也將得到進一步鞏固和提高。

3.5完善教材建設(shè),適應(yīng)新的教學思路

教材建設(shè)是課程建設(shè)的重要工作,教材包括課堂教學使用的教材或講義、實驗教學使用的實驗指導書、輔導教材等。為適應(yīng)新的教學思路和方法,我們編寫了講義和實驗指導教材。講義立足于圖論算法思想的描述及程序?qū)崿F(xiàn),并以大量的ACM/ICPC題目闡述圖論算法思想在求解這些題目中的應(yīng)用。該講義在內(nèi)容取材、描述上具有如下特點:(1)許多圖論教材對圖論概念的描述不一致,造成讀者的閱讀和使用困難,該講義試圖改變這一現(xiàn)狀。對每個概念的表述,我們查閱了大量的圖論著作并進行比較分析。在講義中,我們對每個概念采用大多數(shù)圖論教材采用的名詞和描述方式。(2)忽略所有圖論定理的證明,著重分析圖論算法的思想,重點在于這些圖論算法的程序?qū)崿F(xiàn)和應(yīng)用。對圖論算法的程序?qū)崿F(xiàn)是以經(jīng)典的ACM/ICPC例題來闡述的。(3)分析每一個算法的復雜度,并對同一個問題不同算法的復雜度進行對比分析。(4)采用淺顯易懂的語言、豐富的圖表來描述圖論算法思想。

4教學方法

一種新的教學思路必須輔以一套新穎的、有效的教學方法,因此我們注重探索合適的教學方法。

4.1課堂教學

課堂教學是教學的重點,我們在教學中采取以下教學方法加強課堂教學效果。

(1) 上好第一堂課。第一堂課的教學效果會決定學生是否會認真聽這門課,特別是選修課。對圖論的第一堂課,我們往往從一些有趣的問題入手引入圖論的研究內(nèi)容,如哥尼斯堡七橋問題、中國郵遞員問題、周游世界問題、圖的著色等。這些問題通俗易懂,比較有趣,更重要的是,這些問題可以把圖論里的主要研究內(nèi)容串接起來,從而讓學生對圖論研究的概況有一定的了解。

(2) 加強課堂互動。圖論的很多問題來自于生產(chǎn)生活,在學生的學習生活中也能找到應(yīng)用的例子。在課堂上,我們經(jīng)常邀請學生在黑板上演示算法的求解過程,這能幫助學生理解算法的思想和求解過程。

(3) 加強算法的對比分析和演示。為了讓學生對圖論算法的復雜度有直觀的認識,我們通常在分析完算法的復雜度后,對一些例題進行程序?qū)崿F(xiàn),并提交到OJ系統(tǒng),通過反饋回來的運行時間來驗證算法的時間復雜度。

4.2實踐教學

這里談的實踐教學不局限于實驗課。為提高學生對圖論課程的興趣,并引導學生開展基礎(chǔ)的論文閱讀和文獻綜述,為今后的專業(yè)發(fā)展奠定基礎(chǔ),我們在教學中開展了豐富的實踐教學內(nèi)容。

(1) 在解題時,指導學生閱讀相關(guān)論文,啟迪他們的論文查閱意識和能力。比如學生在求解網(wǎng)絡(luò)最大流問題時指導他們閱讀文獻[3],這篇文獻綜述了網(wǎng)絡(luò)流算法的研究歷史和現(xiàn)狀。

(2) 圖論里有很多問題至今都沒有得到解決,比如漢密爾頓回路、圖的著色等,國內(nèi)外學者對這些問題的研究也一直沒有中斷。我們指導學生綜述這些研究,這對培養(yǎng)學生的探索性思維有很大的幫助。

(3) 指導學生定期對求解過的題目進行總結(jié),以解題報告或小論文的形式提交,作為平時成績的一部分。

(4) 為了豐富OJ系統(tǒng)的題庫,我們采取一系列措施鼓勵學生出題,比如在題目中對出題學生進行署名,組織學生的個人專場比賽等。學生出的題目大多來源于平時的學習和解題的積累,因此這些激勵措施也能提高學生的學習積極性。

5結(jié)束語

圖論是一門既有趣又具有較大難度的課程。對計算機專業(yè)的學生來說,圖論課程不僅豐富了他們的數(shù)學知識,更鍛煉了他們的算法分析與設(shè)計能力。采取新的教學思路后,選修這門課的學生逐年增多,許多學生的程序設(shè)計和算法設(shè)計能力得到了極大提升,并在程序設(shè)計競賽中取得了很好的成績。

參考文獻:

[1] 徐俊明. 圖論及其應(yīng)用[M]. 2版. 合肥:中國科學技術(shù)大學出版社,2004.

[2] 徐俊明. 《圖論及其應(yīng)用》課程建設(shè)探索[J]. 教育與現(xiàn)代化,1997(2):41-46.

[3] 張憲超,陳國良,萬穎瑜. 網(wǎng)絡(luò)最大流問題研究進展[J]. 計算機研究與發(fā)展,2003,40(9):1281-1292.

[4] 錢建國. 淺談算法實例在圖論教學中的作用[J]. 莆田學院學報,2004,11(3):70-71.

[5] 謝政,戴麗,陳摯. 關(guān)于圖論課教學的思考[J]. 數(shù)學理論與應(yīng)用,2005,25(4):139-140.

[6] 杜承銘. 本科應(yīng)用型人才培養(yǎng)目標的選擇、構(gòu)建及實現(xiàn)[J]. 教育與職業(yè),2006(32):20-22.