梁 冰，馮 林，杜 猛，李 航

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 講授例題來(lái)源于在線評(píng)測(cè)系統(tǒng)中經(jīng)典題目

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

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

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

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

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

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

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

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

2.2 引導(dǎo)學(xué)生主動(dòng)學(xué)習(xí)與自學(xué)

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

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

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

2.4 答疑與探討

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

3 基于在線評(píng)測(cè)系統(tǒng)的實(shí)驗(yàn)平臺(tái)建設(shè)與實(shí)驗(yàn)教學(xué)開展

3.1 在線評(píng)測(cè)系統(tǒng)的課程實(shí)驗(yàn)平臺(tái)建設(shè)的必要性

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

3.2 在線評(píng)測(cè)系統(tǒng)的特點(diǎn)和性能

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

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

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

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

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

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

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

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

Compile Error（CE），程序編輯錯(cuò)誤。

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

3.3 基于在線評(píng)測(cè)系統(tǒng)的實(shí)驗(yàn)課程開展方法

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

評(píng)測(cè)系統(tǒng)對(duì)程序及時(shí)詳細(xì)的反饋，對(duì)學(xué)生的學(xué)習(xí)是一種積極的鼓勵(lì)與促進(jìn)，更是杜絕了學(xué)生在學(xué)習(xí)算法時(shí)的淺嘗輒止，因?yàn)橐恢虢鈱W(xué)習(xí)所得到的結(jié)果不會(huì)是最優(yōu)的。在線評(píng)測(cè)系統(tǒng)返回給學(xué)生不同類型的判定結(jié)果，培養(yǎng)了學(xué)生對(duì)算法精益求精、深入研究、理解透徹的學(xué)習(xí)習(xí)慣，這對(duì)學(xué)生是受益終生的。

4 課程考核方式改革

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

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

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

5 結(jié)語(yǔ)

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

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