基于ACM-ICPC競賽模式的算法設計與分析教學改革實踐

王淼，董星星

1.河南工程學院 計算機學院，河南 鄭州 451191； 2.河南理工大學 計算機科學與技術學院，河南 焦作 454000

0 引言

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

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

如何更好地講授算法設計與分析這門課程，是廣大教師所面臨的問題，在講授過程中，筆者發現了教學存在的問題，并嘗試做出了改革實踐，積累了一些經驗。如果教師將算法設計與分析的課程內容與ACM-ICPC競賽結合起來，通過競賽題目引導學生分析問題，進而展開課程內容講解，將有利于調動學生學習的積極性，使得學生深入理解算法原理。

1 算法設計與分析教學存在的問題

1.1 理論與實踐脫軌，教學方式單一

在教學方式上，傳統的教學重視理論教學，忽略實踐教學，教師大多通過PPT講解課程內容，缺乏創新。算法設計與分析的課堂環節包括課程導入、講授新知、鞏固練習、課堂小結，教師主要利用講授法完成大部分環節，學生拿著課本聽講，缺少師生之間、生生之間的課堂討論，容易導致學生注意力不集中，聽課效果較差。

除此之外，雖然課程安排包括實驗課，但實驗課時間短、要求較低，學生對于實驗課不夠重視，部分學生并未理解算法的設計原理和具體實現，沒有按照要求編寫程序，而是直接提交實驗報告。總體來說，教師的教學方式比較單一，主要是通過PPT展示教學內容，忽略了互動環節，缺乏生動形象的教學方式，并且沒有意識到實驗課的重要性，一直以同樣的方式教學，學生容易注意力分散，學習效果差。

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

在教學內容上，與其他基礎課程相比，算法設計與分析課程本身所涉及的知識點難度較大，缺乏生動形象的案例幫助理解，而且需要一定的數學基礎。為了后續能夠編寫程序，課程內容中的很多經典算法需要學生掌握，如果教師花費大量的時間講授基礎知識，學生參與感不強，難免會感覺枯燥，缺少學習算法知識的興趣。

算法分析需要學生靜下心來思考問題，而學生自身分析問題和解決問題的能力不夠，使得難以理解算法原理和具體實現。想要真正理解算法設計與分析這門課程，并學會應用算法設計與分析解決實際問題，機械地記憶算法的步驟是遠遠不夠的，需要冷靜、努力、認真分析才可以，發現學習算法設計與分析課程的樂趣，慢慢激起學生學習算法的興趣。

1.3 實驗要求過于形式，考核方式不當

在考核方式上，傳統的算法設計與分析的課程考核分為期末考核、實驗課考核兩部分。期末考核包括平時成績和期末考試試卷成績。期末考試的試卷內容是課本上的理論知識，平時成績包括課堂出勤和課堂作業，側重考察理論知識的掌握情況。實驗課考核包括經典算法的程序實現，側重考查學生操作能力。

看似合理的考核方式實際存在諸多問題。期末考核以期末考試試卷成績為主，平時成績作為參考。由于期末考試試卷的成績所占比重較大，很多學生在考試前幾周開始復習考試內容，前期并沒有投入學習，只是“為了考試而考試”，失去了考試的真正意義。

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

2 基于ACM-ICPC競賽模式的教學改革

2.1 教學內容改革，與競賽試題結合

ACM-ICPC競賽題目具有創造性、難度較大、考察范圍廣、與生活中的實際問題聯系緊密。為了解決算法設計與分析的教學內容與實踐脫軌、學生缺乏興趣的問題，針對教學內容進行改革，與競賽試題相結合。該教學模式著重培養學生分析問題和解決問題的能力，比如在競賽中無法將實際的問題轉化為利用相關算法實現。

課堂的導入環節以競賽題目的形式呈現，讓學生分組討論題目，發現自己疑惑的知識，然后教師針對學生提出的問題進行解答，并展開新知識的講解。這樣將有利于激發學生的學習興趣，培養學生的團隊協作能力。

除此之外，課堂的鞏固練習和布置作業環節同樣與ACM-ICPC競賽題目結合，利用ACMICPC競賽變式題考查學生對于知識的具體掌握情況。ACM-ICPC競賽變式題的題型分為基礎型和挑戰型，基礎題型主要涉及排序、遞歸、分治法、動態規劃、貪心算法、分支界限法等基礎知識，鍛煉學生的基礎編程能力；挑戰題型主要涉及算法的綜合應用，可以適當設置ACM-ICPC競賽真題，培養學生的凝聚力和創造力。總體來說，通過教學內容和競賽試題的結合，引導學生深入思考，培養學生的創新思維，從而達到改善教學效果的目的。

2.2 教學方式改革，重視互動式教學

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

課堂的新授環節從分析問題入手，教師講授算法的實現原理，學生帶著問題討論，最終利用ACM-ICPC競賽變式題考查學生對于知識的具體掌握情況。這樣的課堂教學不僅僅強調了算法理論知識的學習，更重要的是讓學生掌握算法的具體實現。總體來說，通過互動式教學，增強教學過程中的師生互動、生生互動，貫徹了“以人為主”的教學理念。

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

考核作為教學過程中的一個檢驗環節，科學的評價方式對促進學生的學習具有重要的導向作用[6-7]。傳統的考核方式包括期末考核、實驗課考核。期末考核以期末考試試卷成績為主，平時成績作為參考，過于強調結果而忽略學習過程，實驗課考核存在同樣的問題，學生在平時學習比較松懈，這樣的考核方式無法反映出學生對于這門課程的真實掌握情況。

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

2.4 加強經典算法的綜合分析

算法設計與分析課程有很多經典問題，可以采用不同的算法實現。教師在講解過程中，對各算法的復雜度進行分析比較，總結各算法的優缺點，重點是分析算法之間的聯系，圖1展示了分治法、動態規劃法、貪心法之間的聯系，使得學生可以理解典型算法的核心思想。通過這些經典問題的綜合分析，引導學生深入思考問題，培養學生的邏輯分析能力和獨立思考能力。

圖1 經典算法之間的聯系

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

圖2 教學改革后的教學流程示意圖

3 結語

基于ACM-ICPC競賽模式的算法設計與分析教學改革實踐，指出了傳統教學存在的一些問題，比如理論與實踐脫鉤、課程枯燥且難度大、考核方式不當等問題，在傳統教學的基礎上，進行了教學改革。把算法設計與分析相關知識以競賽題目的形式呈現，激發學生的學習興趣。引入“對分課堂”模式，充分體現了學生的主導地位，增強了師生之間、生生之間的互動性。通過理論考核和實踐考核相結合，激勵學生邊學習邊實踐，彌補了傳統教學的不足。通過算法設計與分析教學改革實踐，鍛煉了學生分析問題解決問題的能力，整體改善了教學效果。