計(jì)算機(jī)專業(yè)圖論課程教學(xué)改革探索

王桂平 馮 睿

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

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

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

1圖論及圖論教學(xué)

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

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

圖論的教學(xué)具有如下特點(diǎn):

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

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

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

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

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

2教學(xué)改革背景

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

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

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

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

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

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

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

3圖論課程教學(xué)改革

3.1改革思路

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

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

3.2以程序設(shè)計(jì)競賽激發(fā)學(xué)生的學(xué)習(xí)積極性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4教學(xué)方法

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

4.1課堂教學(xué)

課堂教學(xué)是教學(xué)的重點(diǎn),我們在教學(xué)中采取以下教學(xué)方法加強(qiáng)課堂教學(xué)效果。

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

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

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

4.2實(shí)踐教學(xué)

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

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

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

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