基于ACM-ICPC競賽模式的算法設(shè)計(jì)與分析教學(xué)改革實(shí)踐

王淼，董星星

1.河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191； 2.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000

0 引言

算法是一種具有創(chuàng)造性、邏輯性的思維活動(dòng)，算法設(shè)計(jì)與分析是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、物聯(lián)網(wǎng)工程等專業(yè)中一門非常重要的面向設(shè)計(jì)的課程[1]。該課程包括很多經(jīng)典算法，比如回溯算法、貪心算法、遞歸與分治、動(dòng)態(tài)規(guī)劃、分支界限法等。通過學(xué)習(xí)算法的設(shè)計(jì)原理、復(fù)雜性分析以及具體實(shí)現(xiàn)，培養(yǎng)學(xué)生獨(dú)立思考問題和解決問題的能力，為學(xué)生利用算法知識(shí)完成期末實(shí)訓(xùn)、畢業(yè)設(shè)計(jì)、公司實(shí)習(xí)以及開發(fā)出高效的系統(tǒng)奠定了堅(jiān)實(shí)的基礎(chǔ)。該課程的特點(diǎn)是理論性強(qiáng)，比較枯燥，必須通過大量實(shí)踐才能徹底掌握算法原理，課程內(nèi)容具有廣泛性、綜合性、系統(tǒng)性，需要比較扎實(shí)的數(shù)學(xué)基礎(chǔ)知識(shí)[2-3]。

ACM-ICPC（ACM International Collegiate Programming Contest，ACM-ICPC）是由國際計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的國際大學(xué)生程序設(shè)計(jì)競賽，要求每組參賽選手必須在五小時(shí)內(nèi)編寫完程序并進(jìn)行測試和調(diào)試，在線提交競賽題目到指定位置。ACM-ICPC競賽所涵蓋的知識(shí)面比較廣，需要參賽者在計(jì)算機(jī)編程、離散數(shù)學(xué)、計(jì)算幾何等方面具備一定的功底，并且分析處理問題的能力較強(qiáng)。參加競賽可以提高選手的邏輯計(jì)算能力、團(tuán)隊(duì)合作能力、創(chuàng)新能力以及計(jì)算機(jī)編程能力，通過區(qū)域賽和總決賽的角逐，最終挑選出最優(yōu)秀的程序設(shè)計(jì)人才[4]。

如何更好地講授算法設(shè)計(jì)與分析這門課程，是廣大教師所面臨的問題，在講授過程中，筆者發(fā)現(xiàn)了教學(xué)存在的問題，并嘗試做出了改革實(shí)踐，積累了一些經(jīng)驗(yàn)。如果教師將算法設(shè)計(jì)與分析的課程內(nèi)容與ACM-ICPC競賽結(jié)合起來，通過競賽題目引導(dǎo)學(xué)生分析問題，進(jìn)而展開課程內(nèi)容講解，將有利于調(diào)動(dòng)學(xué)生學(xué)習(xí)的積極性，使得學(xué)生深入理解算法原理。

1 算法設(shè)計(jì)與分析教學(xué)存在的問題

1.1 理論與實(shí)踐脫軌，教學(xué)方式單一

在教學(xué)方式上，傳統(tǒng)的教學(xué)重視理論教學(xué)，忽略實(shí)踐教學(xué)，教師大多通過PPT講解課程內(nèi)容，缺乏創(chuàng)新。算法設(shè)計(jì)與分析的課堂環(huán)節(jié)包括課程導(dǎo)入、講授新知、鞏固練習(xí)、課堂小結(jié)，教師主要利用講授法完成大部分環(huán)節(jié)，學(xué)生拿著課本聽講，缺少師生之間、生生之間的課堂討論，容易導(dǎo)致學(xué)生注意力不集中，聽課效果較差。

除此之外，雖然課程安排包括實(shí)驗(yàn)課，但實(shí)驗(yàn)課時(shí)間短、要求較低，學(xué)生對于實(shí)驗(yàn)課不夠重視，部分學(xué)生并未理解算法的設(shè)計(jì)原理和具體實(shí)現(xiàn)，沒有按照要求編寫程序，而是直接提交實(shí)驗(yàn)報(bào)告?？傮w來說，教師的教學(xué)方式比較單一，主要是通過PPT展示教學(xué)內(nèi)容，忽略了互動(dòng)環(huán)節(jié)，缺乏生動(dòng)形象的教學(xué)方式，并且沒有意識(shí)到實(shí)驗(yàn)課的重要性，一直以同樣的方式教學(xué)，學(xué)生容易注意力分散，學(xué)習(xí)效果差。

1.2 課程枯燥且難度大，學(xué)生缺乏興趣

在教學(xué)內(nèi)容上，與其他基礎(chǔ)課程相比，算法設(shè)計(jì)與分析課程本身所涉及的知識(shí)點(diǎn)難度較大，缺乏生動(dòng)形象的案例幫助理解，而且需要一定的數(shù)學(xué)基礎(chǔ)。為了后續(xù)能夠編寫程序，課程內(nèi)容中的很多經(jīng)典算法需要學(xué)生掌握，如果教師花費(fèi)大量的時(shí)間講授基礎(chǔ)知識(shí)，學(xué)生參與感不強(qiáng)，難免會(huì)感覺枯燥，缺少學(xué)習(xí)算法知識(shí)的興趣。

算法分析需要學(xué)生靜下心來思考問題，而學(xué)生自身分析問題和解決問題的能力不夠，使得難以理解算法原理和具體實(shí)現(xiàn)。想要真正理解算法設(shè)計(jì)與分析這門課程，并學(xué)會(huì)應(yīng)用算法設(shè)計(jì)與分析解決實(shí)際問題，機(jī)械地記憶算法的步驟是遠(yuǎn)遠(yuǎn)不夠的，需要冷靜、努力、認(rèn)真分析才可以，發(fā)現(xiàn)學(xué)習(xí)算法設(shè)計(jì)與分析課程的樂趣，慢慢激起學(xué)生學(xué)習(xí)算法的興趣。

1.3 實(shí)驗(yàn)要求過于形式，考核方式不當(dāng)

在考核方式上，傳統(tǒng)的算法設(shè)計(jì)與分析的課程考核分為期末考核、實(shí)驗(yàn)課考核兩部分。期末考核包括平時(shí)成績和期末考試試卷成績。期末考試的試卷內(nèi)容是課本上的理論知識(shí)，平時(shí)成績包括課堂出勤和課堂作業(yè)，側(cè)重考察理論知識(shí)的掌握情況。實(shí)驗(yàn)課考核包括經(jīng)典算法的程序?qū)崿F(xiàn)，側(cè)重考查學(xué)生操作能力。

看似合理的考核方式實(shí)際存在諸多問題。期末考核以期末考試試卷成績?yōu)橹?，平時(shí)成績作為參考。由于期末考試試卷的成績所占比重較大，很多學(xué)生在考試前幾周開始復(fù)習(xí)考試內(nèi)容，前期并沒有投入學(xué)習(xí)，只是“為了考試而考試”，失去了考試的真正意義。

實(shí)驗(yàn)課考核大多是教師提供題目和參考代碼，學(xué)生按照參考代碼調(diào)試程序，運(yùn)行出結(jié)果，將運(yùn)行結(jié)果整理成實(shí)驗(yàn)報(bào)告提交給老師。對于簡單的題目，學(xué)生通過參考代碼實(shí)現(xiàn)，并沒有自己思考的過程，而對于復(fù)雜的題目，學(xué)生無從下手，大部分學(xué)生直接網(wǎng)上搜索，下載源程序，失去了鍛煉自己的過程。而且實(shí)驗(yàn)作業(yè)是一個(gè)比較簡單的實(shí)驗(yàn)報(bào)告，無法考核學(xué)生對于算法原理的具體掌握情況。

2 基于ACM-ICPC競賽模式的教學(xué)改革

2.1 教學(xué)內(nèi)容改革，與競賽試題結(jié)合

ACM-ICPC競賽題目具有創(chuàng)造性、難度較大、考察范圍廣、與生活中的實(shí)際問題聯(lián)系緊密。為了解決算法設(shè)計(jì)與分析的教學(xué)內(nèi)容與實(shí)踐脫軌、學(xué)生缺乏興趣的問題，針對教學(xué)內(nèi)容進(jìn)行改革，與競賽試題相結(jié)合。該教學(xué)模式著重培養(yǎng)學(xué)生分析問題和解決問題的能力，比如在競賽中無法將實(shí)際的問題轉(zhuǎn)化為利用相關(guān)算法實(shí)現(xiàn)。

課堂的導(dǎo)入環(huán)節(jié)以競賽題目的形式呈現(xiàn)，讓學(xué)生分組討論題目，發(fā)現(xiàn)自己疑惑的知識(shí)，然后教師針對學(xué)生提出的問題進(jìn)行解答，并展開新知識(shí)的講解。這樣將有利于激發(fā)學(xué)生的學(xué)習(xí)興趣，培養(yǎng)學(xué)生的團(tuán)隊(duì)協(xié)作能力。

除此之外，課堂的鞏固練習(xí)和布置作業(yè)環(huán)節(jié)同樣與ACM-ICPC競賽題目結(jié)合，利用ACMICPC競賽變式題考查學(xué)生對于知識(shí)的具體掌握情況。ACM-ICPC競賽變式題的題型分為基礎(chǔ)型和挑戰(zhàn)型，基礎(chǔ)題型主要涉及排序、遞歸、分治法、動(dòng)態(tài)規(guī)劃、貪心算法、分支界限法等基礎(chǔ)知識(shí)，鍛煉學(xué)生的基礎(chǔ)編程能力；挑戰(zhàn)題型主要涉及算法的綜合應(yīng)用，可以適當(dāng)設(shè)置ACM-ICPC競賽真題，培養(yǎng)學(xué)生的凝聚力和創(chuàng)造力?？傮w來說，通過教學(xué)內(nèi)容和競賽試題的結(jié)合，引導(dǎo)學(xué)生深入思考，培養(yǎng)學(xué)生的創(chuàng)新思維，從而達(dá)到改善教學(xué)效果的目的。

2.2 教學(xué)方式改革，重視互動(dòng)式教學(xué)

傳統(tǒng)的教學(xué)方式以教師講授為主，學(xué)生往往被動(dòng)學(xué)習(xí)，教學(xué)效果不佳。為了增強(qiáng)課堂的互動(dòng)性，嘗試引入“對分課堂”模式進(jìn)行教學(xué)，“對分課堂”是一種傳統(tǒng)課堂與自主課堂的融合，其核心理念是將課堂時(shí)間一分為二，一半時(shí)間留給教師講授知識(shí)，另一半時(shí)間留給學(xué)生自主討論學(xué)習(xí)，重視互動(dòng)式教學(xué)[5]。學(xué)生吸收了課堂知識(shí)以后，了解到自己不理解的知識(shí)點(diǎn)，帶著問題進(jìn)行討論，這樣達(dá)到的效果是比較好的，不僅可以提高教學(xué)質(zhì)量，也加深了學(xué)生對于知識(shí)點(diǎn)的理解。

課堂的新授環(huán)節(jié)從分析問題入手，教師講授算法的實(shí)現(xiàn)原理，學(xué)生帶著問題討論，最終利用ACM-ICPC競賽變式題考查學(xué)生對于知識(shí)的具體掌握情況。這樣的課堂教學(xué)不僅僅強(qiáng)調(diào)了算法理論知識(shí)的學(xué)習(xí)，更重要的是讓學(xué)生掌握算法的具體實(shí)現(xiàn)?？傮w來說，通過互動(dòng)式教學(xué)，增強(qiáng)教學(xué)過程中的師生互動(dòng)、生生互動(dòng)，貫徹了“以人為主”的教學(xué)理念。

2.3 考核方式改革，多方面綜合考察

考核作為教學(xué)過程中的一個(gè)檢驗(yàn)環(huán)節(jié)，科學(xué)的評(píng)價(jià)方式對促進(jìn)學(xué)生的學(xué)習(xí)具有重要的導(dǎo)向作用[6-7]。傳統(tǒng)的考核方式包括期末考核、實(shí)驗(yàn)課考核。期末考核以期末考試試卷成績?yōu)橹鳎綍r(shí)成績作為參考，過于強(qiáng)調(diào)結(jié)果而忽略學(xué)習(xí)過程，實(shí)驗(yàn)課考核存在同樣的問題，學(xué)生在平時(shí)學(xué)習(xí)比較松懈，這樣的考核方式無法反映出學(xué)生對于這門課程的真實(shí)掌握情況。

考核方式應(yīng)當(dāng)重視教學(xué)過程的考核，比如：課前預(yù)習(xí)、課堂回答問題、課后作業(yè)題、實(shí)踐考核等，多方面綜合考察。具體來說，算法設(shè)計(jì)與分析課程考核分為理論考核和實(shí)踐考核兩部分。理論考核包括平時(shí)出勤、課堂回答問題、課后作業(yè)以及期末考試。平時(shí)出勤是指學(xué)生每節(jié)課按時(shí)上課的次數(shù)，課堂回答問題是指學(xué)生個(gè)人回答問題次數(shù)和小組回答問題次數(shù)的累加，側(cè)重考查學(xué)生上課的積極性。課后作業(yè)是ACM-ICPC競賽題，激發(fā)學(xué)生的學(xué)習(xí)興趣。期末考試側(cè)重考查學(xué)生分析問題解決問題的能力；實(shí)踐考核是在傳統(tǒng)實(shí)驗(yàn)課考核的基礎(chǔ)上增加了ACM-ICPC競賽題目的練習(xí)，以課堂鞏固和布置作業(yè)的形式呈現(xiàn)，通過自動(dòng)判題平臺(tái)加強(qiáng)訓(xùn)練，綜合考查學(xué)生的實(shí)踐能力。其中，理論考核和實(shí)踐考核各占50%，解決了傳統(tǒng)教學(xué)存在的理論與實(shí)踐脫鉤的問題，豐富了考核方式，不再以單一化的教學(xué)方式進(jìn)行授課。通過這樣全方位的考核，提高學(xué)生編程實(shí)踐能力，督促學(xué)生邊實(shí)踐邊學(xué)習(xí)，鍛煉自己解決實(shí)際問題的能力。

2.4 加強(qiáng)經(jīng)典算法的綜合分析

算法設(shè)計(jì)與分析課程有很多經(jīng)典問題，可以采用不同的算法實(shí)現(xiàn)。教師在講解過程中，對各算法的復(fù)雜度進(jìn)行分析比較，總結(jié)各算法的優(yōu)缺點(diǎn)，重點(diǎn)是分析算法之間的聯(lián)系，圖1展示了分治法、動(dòng)態(tài)規(guī)劃法、貪心法之間的聯(lián)系，使得學(xué)生可以理解典型算法的核心思想。通過這些經(jīng)典問題的綜合分析，引導(dǎo)學(xué)生深入思考問題，培養(yǎng)學(xué)生的邏輯分析能力和獨(dú)立思考能力。

圖1 經(jīng)典算法之間的聯(lián)系

綜上所述，教學(xué)改革后的教學(xué)流程分為課前準(zhǔn)備、課堂學(xué)習(xí)、課程考核三大部分如圖2所示。課前準(zhǔn)備是指課前預(yù)習(xí)，完成預(yù)習(xí)內(nèi)容。課堂學(xué)習(xí)包括導(dǎo)入、講授新知、鞏固練習(xí)、課堂小結(jié)、布置作業(yè)五大環(huán)節(jié)。課堂的導(dǎo)入環(huán)節(jié)以競賽題目的形式呈現(xiàn)，學(xué)生分組討論題目，教師借此引入新課；隨后，利用“對分課堂”模式進(jìn)行講授新知，前一半時(shí)間，教師講授新課，后一半時(shí)間，學(xué)生帶著問題進(jìn)行討論，增強(qiáng)師生互動(dòng)、生生互動(dòng)；鞏固練習(xí)環(huán)節(jié)和布置作業(yè)環(huán)節(jié)仍以ACM-ICPC競賽變式題（基礎(chǔ)題型、挑戰(zhàn)題型）考查學(xué)生的掌握情況；課堂小結(jié)環(huán)節(jié)加強(qiáng)經(jīng)典算法的綜合分析，重點(diǎn)是講明算法之間的聯(lián)系。課程考核包括理論考核（50%）和實(shí)踐考核（50%），理論考核是指平時(shí)出勤、課堂回答問題、課后作業(yè)以及期末考試，實(shí)踐考核是指實(shí)驗(yàn)課和ACM-ICPC競賽試題的練習(xí)。

圖2 教學(xué)改革后的教學(xué)流程示意圖

3 結(jié)語

基于ACM-ICPC競賽模式的算法設(shè)計(jì)與分析教學(xué)改革實(shí)踐，指出了傳統(tǒng)教學(xué)存在的一些問題，比如理論與實(shí)踐脫鉤、課程枯燥且難度大、考核方式不當(dāng)?shù)葐栴}，在傳統(tǒng)教學(xué)的基礎(chǔ)上，進(jìn)行了教學(xué)改革。把算法設(shè)計(jì)與分析相關(guān)知識(shí)以競賽題目的形式呈現(xiàn)，激發(fā)學(xué)生的學(xué)習(xí)興趣。引入“對分課堂”模式，充分體現(xiàn)了學(xué)生的主導(dǎo)地位，增強(qiáng)了師生之間、生生之間的互動(dòng)性。通過理論考核和實(shí)踐考核相結(jié)合，激勵(lì)學(xué)生邊學(xué)習(xí)邊實(shí)踐，彌補(bǔ)了傳統(tǒng)教學(xué)的不足。通過算法設(shè)計(jì)與分析教學(xué)改革實(shí)踐，鍛煉了學(xué)生分析問題解決問題的能力，整體改善了教學(xué)效果。