數(shù)據(jù)結(jié)構(gòu)與算法課程面向?qū)嵺`的教學方法研究

梁 冰，馮 林，杜 猛，李 航

（大連理工大學 創(chuàng)新創(chuàng)業(yè)學院，遼寧 大連 116024）

0 引言

數(shù)據(jù)結(jié)構(gòu)與算法作為計算機專業(yè)的核心課程，是計算機專業(yè)人才培養(yǎng)的基石，從事計算機學科的信息處理、人工智能、數(shù)據(jù)庫、操作系統(tǒng)、圖形圖像等方面的研究，都離不開數(shù)據(jù)結(jié)構(gòu)和算法的應(yīng)用[1]。隨著計算機處理的數(shù)據(jù)量越來越大，對處理數(shù)據(jù)的程序效率也提出了更高的需求，計算機專業(yè)人才應(yīng)具有扎實的編碼能力和算法知識，并通過程序?qū)崿F(xiàn)能夠讓計算機高效、準確地執(zhí)行人們的想法和構(gòu)思，這是計算機專業(yè)培養(yǎng)的重要目標[2-4]。

數(shù)據(jù)結(jié)構(gòu)與算法作為一門實踐性很強的專業(yè)技術(shù)基礎(chǔ)課程，是培養(yǎng)學生計算思維、算法設(shè)計與實現(xiàn)能力的重要課程，包括C語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計等。采用筆試的傳統(tǒng)方式考核學生的知識掌握能力，考試能得高分的學生卻不能編寫一條簡單的程序，這完全背離計算機專業(yè)對人才培養(yǎng)的目標，授課教師在理論與實踐教學的探索中不斷改革創(chuàng)新，培養(yǎng)學生理論素養(yǎng)與實踐能力[5-7]。

熟練掌握計算機的經(jīng)典算法是學生今后從事各方面工作和研究的專業(yè)基礎(chǔ)[8-10]。IT公司在招聘時，無不把考察學生的算法知識作為重點，尤其在人工智能和大數(shù)據(jù)的時代，算法在提高程序效率方面起著舉足輕重的作用。計算機的經(jīng)典算法體現(xiàn)著科學家的智慧和思維，通過對經(jīng)典算法的學習可以培養(yǎng)學生的思維能力和解決問題的能力。更重要的是，對于算法的學習，不僅僅要理解算法的理論，更要能夠?qū)⑺惴▽崿F(xiàn)并應(yīng)用于解決實際問題當中，這才算達到了熟練掌握算法的培養(yǎng)目標[11-12]。

1 理論教學內(nèi)容與實踐教學緊密相連

1.1 按專題講授經(jīng)典算法

講授經(jīng)典算法時按專題劃分，可以較為全面地講授各類別的經(jīng)典算法，擴展學生的知識面，培養(yǎng)學生計算機思維，為今后學習與研究打下堅實基礎(chǔ)。

數(shù)據(jù)結(jié)構(gòu)專題，包括棧、隊列、二叉樹、二叉搜索樹、堆、優(yōu)先隊列、圖、并查集、線段樹、樹狀數(shù)組。

排序算法專題，包括冒泡排序選擇排序、插入排序、歸并排序、快速排序、計數(shù)排序、基數(shù)排序。

算法設(shè)計類型專題，包括枚舉、遞推、遞歸、貪心、分治、模擬、哈希、二分。

搜索算法專題，包括寬度優(yōu)先搜索、深度優(yōu)先搜索、剪枝（A*、IDA*）算法。

動態(tài)規(guī)劃（Dynamic Programming，DP）專題，包括背包DP、狀態(tài)壓縮DP、樹狀DP、概率DP。

圖論專題，包括圖的最短路算法（Dijkstra、SPFA、Floyd_warshall）、最小生成樹算法（Prime、Kruskal）、圖的最大流算法（Ford-Fulkerson、Dinic）、二分圖匹配算法、最小費用流算法、圖的強連通分量分解算法。

字符串專題，包括字符串匹配算法、后綴數(shù)組、AC自動機、后綴自動機。

數(shù)論專題，包括最大公約數(shù)、擴展歐幾里得算法、線性方程與同余方程、乘法逆元、中國剩余定理、質(zhì)數(shù)篩法、歐拉函數(shù)、高斯消元。

計算幾何專題，包括點線形的數(shù)據(jù)結(jié)構(gòu)表示、線段相交問題、多邊形求面積、點與多邊形的位置關(guān)系、圓、凸包、半平面交。

組合數(shù)學專題，包括排列組合母函數(shù)、整數(shù)拆分、Stirling數(shù)和Catalan、容斥原理和莫比烏斯反演、群論和polya定理。

1.2 講授例題來源于在線評測系統(tǒng)中經(jīng)典題目

課上每個算法所講解的例題來自在線評測系統(tǒng)（Online Judge），在線評測系統(tǒng)上的題目一般會綜合多個算法知識，從中精選例題進行講解，有助于學生溫故知新、融會貫通。通過可執(zhí)行C++、Java等代碼對算法實現(xiàn)進行講解，經(jīng)過課上的學習，課后學生也有興趣通過在線評測系統(tǒng)實現(xiàn)課上的例題，并在系統(tǒng)上提交。在線評測系統(tǒng)所返回結(jié)果可以幫助學生更深入地理解算法的思想，并達到熟練掌握算法的學習目標。

1.3 講解算法使用C++、Java等語言描述的可執(zhí)行代碼

講解算法實現(xiàn)時，使用編譯通過的可執(zhí)行代碼，可以培養(yǎng)學生讀寫代碼的能力。確保學生能夠通過計算機語言將算法原理描述出來，并能夠順利通過編譯，使計算機正確的執(zhí)行。教師應(yīng)強調(diào)只有通過計算機語言正確實現(xiàn)了經(jīng)典算法的思想，才算真正地掌握算法，完成了算法學習的目標。

1.4 注重講解算法復(fù)雜度的分析以及算法的優(yōu)化方法

圖論中很多經(jīng)典算法的講授需要詳細講解復(fù)雜度，比如同樣是圖的最短路算法，Bellman-Ford算法的復(fù)雜度是O(|V||E|)，而Dijkstra算法的復(fù)雜度是O(|E|log|V|)，后者更高效地計算最短路的長度；圖中的網(wǎng)絡(luò)流算法，F(xiàn)ord-Fulkerson算法的復(fù)雜度為O(F|E|)，而Dinic算法復(fù)雜度為O(|E||V|2)，后者在實際應(yīng)用中速度非?？臁Ｈ绻鉀Q問題的算法不是最優(yōu)的，那么在線評測系統(tǒng)是不會通過的，系統(tǒng)會返回Time Limit Exceeded（TLE）：程序運行時間超出了題目的規(guī)定。對于解決問題的算法只有滿足時間復(fù)雜度和空間復(fù)雜度的情況，系統(tǒng)才會返回通過：“Accepted（AC）：在規(guī)定的時間內(nèi)不超出內(nèi)存限制的條件下得出滿足題目要求的結(jié)果”。

2 面向?qū)嵺`的教學方法

2.1 講授算法時以現(xiàn)實中遇到的實際問題為切入點

教師鼓勵學生在課后閱讀相關(guān)的算法在實際生產(chǎn)和生活中應(yīng)用的文獻資料，學生能夠更好地理解算法的功能和意義，加深理解算法，提升學生學習算法的熱情。如，將快速冪求模算法運用于著名的RSA公鑰加密方法中，鼓勵學生課后查找RSA公鑰加密方法的相關(guān)資料進行學習。最大流最小割算法應(yīng)用于優(yōu)化圖像分割方法，像Photoshop、美圖秀秀等基于交互式分割得到目標的功能基本源于圖像分割。字符串匹配算法Boyer-Moore用于文本編輯器的“查找”功能、論文查重等。

2.2 引導(dǎo)學生主動學習與自學

計算機領(lǐng)域需要學習的經(jīng)典算法非常多，如果不能引導(dǎo)學生自己深入的學習，教師在有限的課堂時間內(nèi)是無法將所有的經(jīng)典算法傳授給學生的，并且單一的講授效果并不好，不能調(diào)動學生積極的思考。因此，提綱挈領(lǐng)地講授經(jīng)典算法的思想和精髓，調(diào)動起學生的興趣，通過主動學習與實現(xiàn)更多的相關(guān)算法是有限課堂時間內(nèi)的首要任務(wù)。如棧和隊列的應(yīng)用和實現(xiàn)方式上有很多相似的原理，可以講授棧的實現(xiàn)方式，而隊列的實現(xiàn)方式留給學生自學，一是提升學生學習的主動性，積極思考；二是避免相似內(nèi)容講解時學生精神不集中。

2.3 采用引導(dǎo)式及互動式教學

在授課時，教師準備好可以和學生積極互動的知識點，調(diào)動學生積極思考，調(diào)動起學生學習的興趣。一些知識點的講解也很合適與學生互動，如在講解算法的時間復(fù)雜度時，教師以快速冪運算算法為例，對于逐次相乘的算法，需要循環(huán)n次，才能獲得結(jié)果，因此算法復(fù)雜度是O(n)，而將n次冪用二進制表示之后，算法又需要循環(huán)多少次便可以得到計算結(jié)果？有了這樣的啟發(fā)，可以激發(fā)學生思考、師生進行互動。

2.4 答疑與探討

教師將每一個經(jīng)典算法介紹之后，會給學生一個提問和探討的機會：學生有什么知識點沒有聽明白，這樣可以了解學生理解問題困難的點，下次授課可以詳細介紹；學生也會提出教師沒有深入講授的知識點，完善教學講授的要點，實現(xiàn)教學相長。

3 基于在線評測系統(tǒng)的實驗平臺建設(shè)與實驗教學開展

3.1 在線評測系統(tǒng)的課程實驗平臺建設(shè)的必要性

建設(shè)在線評測系統(tǒng)（Online Judge，OJ）實驗平臺對提升程序設(shè)計類課程的實驗效果是非常有效的。在沒有在線評測系統(tǒng)之前，對數(shù)據(jù)結(jié)構(gòu)與算法實驗課程中學生實驗結(jié)果的可行性考核是不強的，編譯系統(tǒng)對程序的考察只是編譯結(jié)果是否正確，對于算法的時間復(fù)雜度和空間復(fù)雜度的考核沒有一個嚴格的標準，教師對班級每位學生程序的驗證所耗費的時間是不可估量的。

3.2 在線評測系統(tǒng)的特點和性能

在線評測系統(tǒng)是ACM-ICPC國際大學生程序設(shè)計競賽的比賽系統(tǒng)，OJ系統(tǒng)的應(yīng)用使比賽結(jié)果公平、公正、公開，不受人為因素影響，這項賽事吸引了全球大學生的積極參與，也使得ACM國際大學生程序設(shè)計競賽成為全球最具影響力的大學生程序設(shè)計競賽[13-14]。在線評測系統(tǒng)能夠自動評判代碼的正確性，并將評判結(jié)果返回參賽選手。自動評測系統(tǒng)只反饋以下結(jié)果。

Accepted（AC），在規(guī)定的時間內(nèi)不超出內(nèi)存限制的條件下得出滿足題目要求的結(jié)果。

Presentation Error（PE），在規(guī)定的時間內(nèi)不超出內(nèi)存限制的條件下得出結(jié)果，但是同正確的結(jié)果相比結(jié)果的格式存在問題。

Time Limit Exceeded（TLE），程序運行時間超出了題目的規(guī)定。

Memory Limit Exceeded（MLE），程序在編譯或者運行期間向操作系統(tǒng)申請的內(nèi)存超出了題目的規(guī)定。

Wrong Answer（WA），在規(guī)定的時間內(nèi)不超出內(nèi)存限制的條件下得出結(jié)果，但是同正確的結(jié)果相比存在較大差別。

Runtime Error（RE），程序運行期間訪問非法內(nèi)存。

Output Limit Exceeded（OLE），程序輸出結(jié)果文件過大，超出評測系統(tǒng)限制。

Compile Error（CE），程序編輯錯誤。

評測系統(tǒng)不僅能夠評測程序的正確性，更重要的是可以對程序的時間復(fù)雜度和空間復(fù)雜度進行評測，如果程序雖然能夠通過編譯，但時間復(fù)雜度或空間復(fù)雜度高于題目要求，是不能通過的。正是評測系統(tǒng)這一功能的設(shè)定使學生對算法的復(fù)雜度有了前所未有的重視，加強了學生對算法的理解和學習的深度。

3.3 基于在線評測系統(tǒng)的實驗課程開展方法

按照課堂教學中講授的每個算法，為學生在OJ中設(shè)定相應(yīng)的經(jīng)典題目作為實驗內(nèi)容。教師可以根據(jù)OJ對學生提交題目的判定結(jié)果總結(jié)出學生在代碼編寫中常常出現(xiàn)的錯誤，從而重點講解，及時糾正學生常犯的錯誤。

評測系統(tǒng)對程序及時詳細的反饋，對學生的學習是一種積極的鼓勵與促進，更是杜絕了學生在學習算法時的淺嘗輒止，因為一知半解學習所得到的結(jié)果不會是最優(yōu)的。在線評測系統(tǒng)返回給學生不同類型的判定結(jié)果，培養(yǎng)了學生對算法精益求精、深入研究、理解透徹的學習習慣，這對學生是受益終生的。

4 課程考核方式改革

在總成績中加大編碼和算法實現(xiàn)成績所占的比例，引導(dǎo)學生重視編碼能力的鍛煉：①將實驗課程的成績和課后OJ系統(tǒng)中所留的作業(yè)成績納入到期末總成績；②期中考試采取線上OJ題目考核的方式，考核學生的實踐編碼能力；③期末考試采用筆試的方式。

課程總成績各項所占比例：①實驗成績15%；②作業(yè) 15%；③期中線上考試1成績20%；期中線上考試2成績20%；④期末成績，期末采用筆試的方式，占30%。其中，實驗、作業(yè)、期中競賽在OJ上完成。

從課程總成績中實踐考核內(nèi)容所占的比例可以看出，計算機專業(yè)的學生如果不重視本課程的實踐特性，不能一點一滴的提升自己的編程能力，課程是很難獲得高分的。課程的最終成績能夠客觀反映學生的編碼能力和程序設(shè)計能力，避免出現(xiàn)試卷能夠獲得高分卻無法實現(xiàn)一些簡單算法的現(xiàn)象。學生在學習這門實踐性很強的課程時，單純的筆試考核方式容易造成學生學習方法和學習重點的方向上的錯誤，因此，通過在線評測系統(tǒng)加大客觀評估學生實際編程能力的上機考核方式，使學生在課程學習中，重視上機調(diào)試程序和算法的實現(xiàn)與應(yīng)用。

5 結(jié)語

數(shù)據(jù)結(jié)構(gòu)與算法課程講授了非常重要和實用的計算機算法，能將算法靈活應(yīng)用的基礎(chǔ)就是不僅能夠掌握算法的思想，更要能夠編碼實現(xiàn)算法。筆者提出的面向?qū)嵺`的教學方法，引導(dǎo)學生在學習這門課時重視理論與實踐相結(jié)合，不僅是學習算法的理論，更重要的是編碼實現(xiàn)算法及算法在解決實際問題中的應(yīng)用，而且算法在實踐中應(yīng)用更能加深學生對算法思想的理解，相輔相成。

面向?qū)嵺`的教學方法經(jīng)過多年在理論教學和實驗教學的應(yīng)用，在計算機人才培養(yǎng)上取得了明顯的效果，學生具有編程能力強、算法知識面廣且扎實、專業(yè)素質(zhì)高的特點，因此在保研和就業(yè)中具有很強的競爭力。知名高校和企業(yè)越來越看重學生的算法能力，考核學生的算法能力是很重要的一項。在目前大數(shù)據(jù)和人工智能的環(huán)境下，沒有算法的程序已不能滿足實際應(yīng)用的需求了，學生的編程能力和算法實現(xiàn)能力，無時無刻不在科研和研發(fā)中發(fā)揮著重要的作用。因此，具有編程能力強、算法基礎(chǔ)扎實的計算機專業(yè)學生成為名校和名企的搶手人才，大連理工大學的畢業(yè)生獲得了來自清華、北大、上海交通大學、美國加州大學等名校的保研資格以及來自谷歌、微軟等知名IT企業(yè)的Offer。