信息與計(jì)算科學(xué)專業(yè)圖論教學(xué)改革研究

孔翔宇　王貞　孫瀅

【摘要】本文針對(duì)圖論的教學(xué)現(xiàn)狀，結(jié)合信息專業(yè)的特點(diǎn)，提出了建立課程群，講義編寫等教學(xué)改革措施。同時(shí)也提出了課堂教學(xué)和實(shí)踐教學(xué)的教學(xué)方法。

【關(guān)鍵詞】圖論 教學(xué)改革 教學(xué)方法

【基金項(xiàng)目】寧夏回族自治區(qū)高等學(xué)校教育教學(xué)改革項(xiàng)目：《神經(jīng)網(wǎng)絡(luò)計(jì)算》專題研究型教學(xué)模式探索與實(shí)踐（寧教高[2012]348號(hào)）。

【中圖分類號(hào)】G633.67 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2014）01-0140-01

圖論是組合數(shù)學(xué)和離散數(shù)學(xué)的重要組成部分。圖論起源于著名的哥尼斯堡七橋問題[1-2]。它以圖為研究對(duì)象，把研究的事物抽象成若干點(diǎn)，將事物間存在的關(guān)系用線來表示，如果兩事物間存在關(guān)系，就用一條邊將它們連接起來，經(jīng)過上述方法所做的圖形就是圖論中的圖。自然科學(xué)和社會(huì)科學(xué)中諸多領(lǐng)域的關(guān)系都可以用圖論中的圖來表示，對(duì)于這些問題建立相應(yīng)模型之后再去研究往往能夠得到良好的結(jié)果，故對(duì)于圖論中圖的研究就顯得特別重要，得到了眾多專家和學(xué)者的關(guān)注。

一、圖論課程的教學(xué)現(xiàn)狀

由于圖論在許多領(lǐng)域有著重要的應(yīng)用[3-4]，許多大學(xué)都把圖論作為一門專業(yè)課單獨(dú)開設(shè)，作為數(shù)學(xué)、計(jì)算機(jī)、電子、管理等專業(yè)高年級(jí)本科生和研究生的必修或選修課。圖論在教學(xué)過程中具有如下特點(diǎn)：

1.圖論中基本概念、定理非常多，概念不易理解，定理證明又特別難，這就在一定程度上使教學(xué)枯燥難懂。

2.圖論研究的許多問題都具有實(shí)際應(yīng)用背景，但往往很難轉(zhuǎn)化成圖論模型，不容易求解，從而造成了學(xué)生對(duì)圖論學(xué)習(xí)很有興趣，但因?yàn)椴荒芮蠼舛a(chǎn)生厭學(xué)心理。

3.圖論課程涉及的算法非常多，對(duì)于每個(gè)問題幾乎都有不同的算法。例如最小生成樹的求法就有克魯斯克爾算法，管梅谷的破圈法、Prim算法等十幾種算法，如果要求學(xué)生編程求解實(shí)際問題，那么對(duì)學(xué)生的算法分析能力以及程序設(shè)計(jì)能力就提出了很高的要求。

通過在本校講授該課程發(fā)現(xiàn)學(xué)生并不滿足于圖論算法的證明和紙上求解，迫切需要掌握如何利用計(jì)算機(jī)來實(shí)現(xiàn)算法并求解實(shí)際問題。這就促使我們探討圖論課程的教學(xué)改革。

二、圖論課程的教學(xué)改革

根據(jù)信息與計(jì)算科學(xué)專業(yè)人才培養(yǎng)要求以及圖論課程的教學(xué)現(xiàn)狀，提出如下教學(xué)改革措施。

1.建立課程群

任何一門課程都不是孤立的，總是存在一門或者若干門課程與它相關(guān)，因此很多高校通過建設(shè)課程群來構(gòu)建完整的知識(shí)體系，優(yōu)化課程安排，在較少的人力物力下達(dá)到最高的教學(xué)目標(biāo)。圖論課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生算法分析、設(shè)計(jì)和實(shí)際問題的應(yīng)用能力，而“程序設(shè)計(jì)”、“數(shù)據(jù)結(jié)構(gòu)”、“算法分析設(shè)計(jì)”等課程也是培養(yǎng)學(xué)生的算法分析、設(shè)計(jì)能力，這和圖論課程的教學(xué)目標(biāo)是相同的。所以，可以將這些課組合在一起建立課程群。通過課程學(xué)習(xí)，學(xué)生不但掌握了豐富的圖論知識(shí)，算法分析與設(shè)計(jì)能力也將會(huì)得到進(jìn)一步鞏固和加強(qiáng)。

2.做好教材建設(shè)，編寫適合教學(xué)目標(biāo)的圖論講義、教材

教材建設(shè)是任何一門課程建設(shè)的重中之重，教材主要包括教學(xué)中使用的教材或講義、輔導(dǎo)教材等。為適應(yīng)新的更高的教學(xué)目標(biāo)編寫課程講義。具體教材改革如下：

（1）將目前各大高校普遍使用的圖論教材中50%左右的定理證明略去，不再詳細(xì)證明，僅對(duì)一些經(jīng)典證明進(jìn)行詳細(xì)闡述，重點(diǎn)分析圖論課程所涉及的算法思想。

（2）在課程課時(shí)有限的條件下，如何發(fā)掘?qū)W生的自學(xué)能力是教師要思考的問題。這就要求教師為學(xué)生提供實(shí)例較多的參考書籍。

（3）對(duì)同一問題采用不同的算法，分析所得結(jié)果的差異。重點(diǎn)討論為什么會(huì)產(chǎn)生這種差異。

三、圖論課程的教學(xué)方法

一種新的課程教學(xué)思路必須有一套新穎的、行之有效的教學(xué)方法與之配套，所以必須重視探索恰到好處的教學(xué)方法。

1.課堂教學(xué)

課堂教學(xué)是教學(xué)過程的重中之重，在教學(xué)中可以采取如下方法加強(qiáng)課堂教學(xué)效果：

（1）上好圖論課程的第一次課。第一次課的教學(xué)效果往往會(huì)決定學(xué)生是否會(huì)對(duì)這門課程有興趣，是否愿意認(rèn)真學(xué)習(xí)這門課。對(duì)圖論課程的第一次課，可以從一些有趣的實(shí)際問題入手，如哥尼斯堡七橋問題、中國旅行商問題、中國郵路問題、圖的著色等。這些問題簡單易懂，清晰明了，十分有趣。更主要的是，這些實(shí)際問題可以把圖論中的主要研究內(nèi)容串聯(lián)在一起，從而讓使學(xué)生對(duì)圖論這門課程有直觀的了解。

（2）加強(qiáng)課堂互動(dòng)。圖論的很多問題來源于現(xiàn)實(shí)世界的生產(chǎn)生活，在學(xué)生的校園學(xué)習(xí)生活中也能找到相應(yīng)的例子。在課堂上，使學(xué)生成為課堂教學(xué)的主體，讓學(xué)生在黑板上演示問題相應(yīng)算法的求解步驟，這對(duì)學(xué)生理解算法思想和求解過程將起到重要作用。

（3）加強(qiáng)算法的分析對(duì)比實(shí)驗(yàn)。為了使學(xué)生對(duì)圖論中的算法復(fù)雜度有直觀認(rèn)識(shí)，通常在分析完圖論算法復(fù)雜度之后，對(duì)部分問題進(jìn)行計(jì)算機(jī)仿真實(shí)驗(yàn)，通過反饋回來的算法運(yùn)行時(shí)間來驗(yàn)證算法的復(fù)雜度。

2.實(shí)踐教學(xué)

為了促進(jìn)學(xué)生對(duì)圖論的學(xué)習(xí)興趣，要積極引導(dǎo)學(xué)生閱讀論文和文獻(xiàn)綜述，為今后的專業(yè)發(fā)展夯實(shí)基礎(chǔ)，在教學(xué)中要開展豐富的實(shí)踐教學(xué)內(nèi)容。這里討論的實(shí)踐教學(xué)不單指實(shí)驗(yàn)課。具體在實(shí)踐教學(xué)中可以采取如下方法：

（1）在求解問題時(shí)，通過培養(yǎng)學(xué)生查閱文獻(xiàn)的能力，指導(dǎo)學(xué)生閱讀相關(guān)論文。

（2）圖論中有許多至今仍沒得到解決的問題或者是解決得不好的問題，國內(nèi)外相關(guān)專家和學(xué)者對(duì)這些問題的研究一直沒有中斷，可以向?qū)W生介紹相關(guān)問題，一起探討，培養(yǎng)學(xué)生產(chǎn)生濃厚的學(xué)習(xí)興趣。

（3）在學(xué)習(xí)完一章或者一部分內(nèi)容之后，可以對(duì)這些教學(xué)內(nèi)容以小論文的形式提交作業(yè)，作為考試成績的一部分。

四、結(jié)束語

通過對(duì)圖論課程的一系列教學(xué)改革，提高了學(xué)生的學(xué)習(xí)熱情，更好的實(shí)現(xiàn)了教學(xué)目標(biāo)。如何更深層次的解決圖論課程改革問題是進(jìn)一步需要解決的問題。

參考文獻(xiàn)：

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

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

[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.

作者簡介：

孔翔宇（1982-），男，吉林榆樹人，在讀博士，講師，主要研究方向最優(yōu)化理論、智能算法、高等教育學(xué)。