基于ACM-ICPC模式的算法分析與設計課程的建設

◎張文達

針對算法分析與設計課程的教學實際，文章分析了該課程教學模式的局限性和傳統的實踐教學中存在的問題，提出將ACM-ICPC競賽模式引入該課程教學的觀點，開發了一個基于ACM-ICPC模式的程序測評系統，并應用在算法分析與設計課程的實踐教學中，取得了良好的教學效果。

一、引言

算法分析與設計是面向設計的計算機專業核心課程，主要通過對經典算法的學習和研究，使學生掌握算法的設計策略和算法復雜度的分析方法，培養學生分析和解決實際問題的能力。該課程教學內容繁多，涉及的知識面很廣，主要內容包括算法分析方法、遞歸算法、分治算法、貪心算法、動態規劃、回溯算法、分支限界、近似算法、概率算法等經典的算法，覆蓋了多項式、數論、矩陣、集合、圖論、幾何、模式匹配等數值和非數值計算問題。

目前，各高校該課程分配的課時普遍較少，教學方法也都是以講解為主，即使設置了實驗課，在實踐環節通常也只是一味地對算法進行驗證，很少考慮到算法的運行效率分析、測試數據的規模以及實際的應用場景。而且，在傳統實踐教學中，學生抄襲代碼的情況嚴重，不能有效提高學生的實踐能力，無法體現實踐教學的真正作用。在這種教學模式下，學生缺乏對實際問題進行抽象和分析的能力，思維創新和實踐能力難以得到有效提高。本文結合我校實際教學情況，將ACM-ICPC競賽模式與算法分析與設計課程的建設相結合，達到了良好的教學效果。

二、課程現狀

該課程的開設是面向計算機科學與技術專業大三的學生，學生在學習該課程之前，已經學習了C／C++程序設計、數據結構、Java程序設計、高等數學和離散數學等課程，但是由于學生欠缺良好的計算思維，邏輯分析能力相對不足，編程實踐能力仍然比較弱，學生在學習該課程時倍感吃力。目前我校在算法分析與設計課程信息化建設方面有許多不足，主要體現在以下幾點：

1.課程之間的聯系不夠緊密。算法分析與設計課程與其他課程的關系是很密切的，如數據結構，它們之間相互作用，從而提高計算機專業學生的實踐能力，為學院培養高素質的應用型人才。

2.教學資源不足。當前課程并沒有信息化系統的支持。學生只能通過網絡搜索所需的資源，獲取教師的P跗也只能通過教師，教學資源沒有實現整合和共享。

3.編程競賽平臺不多。在參加或舉辦程序設計類競賽方面，學生只參與了國內的"藍橋杯"這一個程序設計類競賽，學院內部并沒有開展此類競賽活動。

三、ACM-lCPC模式下的課程建設

1.ACM-ICPC在課程中的作用。

ACM國際大學生程序設計競賽（ACM-ICPC）是由國計算機協會（ACM）主辦的，是一項旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。經過40多年的發展，ACM-ICPC已經發展成為最具影響力的大學生計算機競賽。競賽時間為5個小時，重點考察選手的算法和程序設計能力。選手通過網絡提交程序，評委負責將結果（正確或出錯的類型）通過網絡盡快返回給選手。

將ACM-ICPC競賽模式引入算法分析與設計的教學中，可以激發學生的主動學習積極性，鼓勵學生勤思考、多實踐。相對于傳統的實踐教學具有以下幾方面的優勢：（1）在網上進行實踐教學，沒有時間和空間的局限性。教師可以在測評系統中對同一個實驗項目布置多個難度各異的題目，學生可以根據自己的掌握情況。從易到難選擇合適的時間完成訓練題目。（2）對創造校園的學術交流氛圍有良好的促進作用。學生在課余時間通過在網上提交自己編寫的程序源代碼，自主進行算法和程序的交流，有利于培養學生的學術修養。實現學生與教師、學生與學生之間的交流和互動。（3）減輕教師實踐教學時的指導負擔。傳統的實踐教學在機房進行，教師需要在整個機房進行巡視，為有疑問的同學進行解答。而ACM-ICPC競賽模式的在線測評系統可以對學生提交的作業進行評測，大大減輕了教師的負擔。

2.測評系統的設計與開發。

該系統基于Java EE，是一個程序在線評判、程序設計競賽和交流的平臺。可不斷擴展題庫供學生進行程序設計練習，系統自動對提交的程序源代碼進行編譯、運行并評判程序的正確性。系統可供課程日常訓練和網上實時競賽使用，也具備站內交流和站內全文檢索功能。系統有兩個版本的評判模塊，一個基于純Java，另一個基于C++，兩者均可在Windows平臺下運行。學生在系統提交程序后，系統先將程序保存至數據庫，再寫入評判隊列，由系統評判內核進行編譯、運行并返回結果。返回的結果類型有AC、WA、Rr砸、TLE、PE、MLE、CE。每個題目可能有多個測試數據，內核在讀取主系統傳遞給它的參數后，編譯程序，生成可執行文件，之后對于每個測試數據運行一次"驗證測試數據"的操作。

系統用戶分為四種：普通用戶、高級用戶、論壇版主及系統管理員。任何學生都可注冊成為普通用戶。普通用戶可以做練習題，提交程序并得到系統的評判和結果反饋；可以根據程序提交情況參與用戶排名：擁有并可使用自己的站內信箱；可以查看、保存和管理自己提交的源代碼；可以在論壇發帖，參與問題討論；可以參加程序設計競賽，并查看比賽結果和統計數據。任何解答題目超過20道的普通用戶。可自動升級為高級用戶。高級用戶擁有普通用戶的所有權限。還可以上傳題目和測試數據，并可對自己上傳的題目進行管理、修改等。高級用戶上傳的題目，經管理員確認后，便可加入系統的正式題庫。系統在題目信息中記錄上傳題目者的相關信息。論壇版主為系統管理員授予，擁有普通用戶的所有權限，同時對相應的論壇板塊擁有管理權。系統管理員管理系統的日常運行，擁有所有的管理權限，需要對題目和測試數據進行篩選，檢查系統運行情況，組織程序設計競賽。

3.課程設置。結合我校實際情況，我們在算法分析與設計課程的實踐教學內容上設計了遞歸算法、分治算法、動態規劃算法、貪心算法、回溯算法、分支界限算法共6個經典算法的實驗項目。由于實踐教學課時有限，傳統的教學方式每個實驗項目只能設計2-3道題目。引入ACM-ICPC模式之后，學生可以利用課余時間通過網絡完成程序設計，每個實驗項目題量增加到6-8個，題目難度各異，學生可以根據自己的知識掌握程度和能力選擇合適的時間完成。較容易的題目可以先完成，具有一定的綜合性、難度較大的題目，可以在有相當的訓練量之后完成。這種循序漸進的訓練方式，更有利于學生對算法原理的理解和掌握，也更有利于形成由淺入深的思維模式，有效提高學生的分析問題、解決問題的能力。

四、課程建設實踐成果

實施ACM-ICPC競賽模式的程序在線測評系統以后，學生的學習積極性得到了較大的提高。學生對經典算法的掌握程度和實踐能力也大大提高了。學生在各種全國性考試和比賽中取得了較好的成績。學生的自主學習能力有所提高，教師在實驗課上的空閑率由原來的0.4%增長33.3%，學生對教師的依賴程度大大降低。

結語：基于ACM-ICPC模式的算法分析與設計課程將理論學習與實際操作相結合，注重培養和提高學生分析和解決實際問題的能力，以公平、公正、公開的競爭形式帶動學生的自主學習，調動學生交流和研究的積極性，為課程的開展提供了良好的氛圍。在后續的研究和開發中，我們將把基于ACM-ICPC模式的程序測評系統擴展到全系范圍內的更多的程序設計類課程。