基于ACM模式的離散數學實驗探究

陳宇　臧美英　李林輝

【摘要】離散數學是計算機及相關專業核心課程，本文在介紹離散數學、ACM及ACM在線評測系統的基礎上，提出了基于ACM模式的離散數學實驗探究，探討了教學方式與手段及實驗教學的改革。這種改革將提高離散數學課程的教學質量和教學水平，有助于培養學生的抽象思維、邏輯思維、心理素質及團隊協作能力。

【關鍵詞】離散數學 實踐教學 ACM

【中圖分類號】G642.0 【文獻標識碼】A 【文章編號】2095-3089（2015）04-0032-02

The reform and exploration of Discrete Mathematics practice teaching model based on ACM

Chen Yu，Meiying Zang， Linhui Li，

（School of information and computer engineering， Northeast Forestry University，Harbin 150040， China）

【Abstract】 Discrete Mathematics is the core courses of the computer and the related majors， This article describes the basic Discrete Mathematics， ACM and ACM on-line evaluation system ，in addition ，it puts Discrete Mathematics practice teaching reform measures based on ACM model ，it explores the ways and means of teaching and reforms the experimental teaching .This reformation will improve the teaching quality and teaching level of the Discrete Mathematics ，it can help to cultivate students abstract thinking ，logical thinking ，psychological quality and team cooperation ability.

【Key words】 Discrete Mathematics； Practical Teaching； ACM

1.ACM及ACM在線評測系統簡介

ACM國際大學生程序設計競賽是由美國計算機協會（ACM）主辦的，簡稱ACM / ICPC，自從1977年開始至今已經連續舉辦31屆[1]。其宗旨是提供一個讓大學生向IT界展示自己分析問題和解決問題的能力的絕好機會，讓下一代IT天才可以接觸到其今后工作中將要用到的各種軟件，展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。ACM成立于計算機誕生次年，是目前計算機學界中歷史最悠久、最具權威性的組織。該賽事分高校校內賽、地區賽、大洲預賽和世界決賽四個級別。每一屆的賽事在秋季學期舉行各大洲預賽，在春季學期舉行世界總決賽。ACM/ICPC比賽的賽題有實際背景，趣味性和實用性較強，分不同水平的題，考查的知識范圍較全面并具有層次性。而且絕大部分題沒有定解，留有廣闊的思維空間，有益于培養創造性。學生在激烈的競賽中感受數學思維與算法藝術的結合之美，提升編程能力和解決實際問題能力[2]。

自2006年我校第一次參與ACM大賽黑龍江省賽至今每年都組織團隊參與比賽，并取得不錯成績，并成立ACM實驗室，讓學生以精通編程為榮，讓程序編織夢想，形成了一個積極向上的自主學習氛圍，一些高校已經將ACM在線評測系統運用到計算機課程的教學環節之中并取得了不錯的效果。

我校ACM在線評測系統界面如圖一所示：

圖1.ACM/ICPC在線評測平臺

它是集程序設計競賽、競賽訓練、課程實驗、平時練習于一身的網上實時提交系統[3]。該系統提供了大量供學生練習和競賽的競賽題目，學生在線提交解決相關練習和競賽題的程序代碼，系統可以自動編譯程序代碼，生成可執行文件，并根據已存儲的測試用例，從程序的正確性、程序運行總時間、耗費內存、單用例執行時間、程序返回結果等各方面評測程序代碼，并精確返回各方面的評測結果。不但支持C、C++、PASCAL以及JAVA語言的編譯，還定義了一套具有充分可擴展性的編輯器擴充規則，可以在不修改系統任何實現的情況下，通過管理配置文件增加系統可以支持的語言和編譯器。ACM在線測評系統功能模塊圖如圖二所示：

圖2.ACM評測系統功能模塊圖

ACM在線評測系統性能上的穩定快速為計算機專業各門編程課程提供有效的實驗環境。

2.結合ACM模式探索離散結構課程實踐教學

“離散數學”課程是計算機專業核心基礎課程之一，是由數理邏輯、代數結構、集合論、圖論四個部分組成[4]。它是把非連續對象的數量和空間關系作為研究對象的若干數學分支的總稱。隨著計算機技術的發展，離散數學的地位逐漸提高。該課程為數據結構、操作系統、數據庫原理、編譯原理、人工智能等專業課程提供必備的基礎知識，對離散數學的學習無論是對學生們學習后續的專業課程，還是對以后參加工作，都有著重要的意義。通過對離散數學的學習有助于培養學生的學科素質，使學生的抽象思維能力和嚴格邏輯推理能力有所提高。但由于其內容多、理論性強、抽象、解題思路嚴謹，傳統的離散數學教學不能提高學生的學習興趣，教學效果不理想。ACM競賽擁有著較長的歷史，它的方法成熟，把ACM模式應用于離散數學的教學過程中，通過運用現代教學技術改進傳統教學方法是非常必要的。

2.1 建立基于ACM的離散結構教學模式的意義

1.ACM模式是讓學生三個人共用一臺電腦，通過團隊合作在短時間內解決問題的方法。有利于提高學生的個體思維能力，增強學生們的團隊合作意識，增進學生們之間的學術交流。

2.學生們通過建立的基于ACM競賽的網絡教學平臺進行學習，每個人都可以注冊ID，在平臺上學習離散數學的相關課程，不受時間和地域的限制。

3.通過ACM模式競賽式學習，校園之間形成競爭，為此，學校會營造濃厚的學習氛圍，在課余時間對學生進行培訓，旨在讓學生在課余時間對離散數學知識進行鉆研 學習。

4.在離散數學課程的學習中，計算思維是學生們學習的一大難點，計算思維的本質是抽象與自動化，而這些恰恰是ACM競賽必備的素養。把ACM模式應用于離散數學的教學中，培養學生的計算機理論修養，提高學生們的實踐能力，學以致用，通過實踐使學生真正掌握離散數學的豐富知識和算法的精髓。

2.2基于ACM的離散結構教學模式的設計

ACM模式可以開闊學生的視野，培養學生的實踐能力，團隊合作能力，增強創新意識[5]。基于ACM模式的離散數學實踐教學設計分為三個層次：基礎型實驗、綜合型實驗和創新型實驗具體實現方法如下：

（1）基礎型實驗，主要內容是鏈表隊列或堆棧，掌握命題邏輯中的真值表、聯接詞、主范式，進行真值計算、關系閉包計算，計算兩點間長度為m的路的數目等。要求學生掌握基本的離散結構和方法，能運用離散結構描述實際對象并對其進行處理，有較好的問題分析和解決能力。

（2）綜合型實驗，主要內容有商品營銷傭金問題、學生管理系統、物資管理系統穿衣排序、中國郵路問題、巡回售貨員問題等[6]。需要學生具體掌握算法分析與設計，掌握數理邏輯、集合與關系理論、圖論的知識，具有一定的綜合素質，有對知識的實際運用能力。

（3）創新型實驗，需要學生掌握基本的軟件重用方法，運用面向過程和面向對象的設計方法。主要內容有創新的設計完成測謊儀、電梯系統、TSP問題、自動售貨系統、環游世界問題電報碼設計、著色問題、校園導游系統等問題。其中程序的測試采用ACM的模式進行，保證軟件測試的質量。

創新型實驗這一層次要求較高，對那些學有余力、創新性思維強、興趣濃厚的學生，提供了一些難度較高的項目，有利于學生申請并完成本科生的科技創新項目，讓他們初步形成軟件從事者應具備的工作作風和嚴謹態度。

3.基于ACM的離散結構教學模式改革措施

（1）案例教學

案例教學通過模擬或重現實際生活中的某些場景，需要學生把自己納入案例場景，通過研討的方式來進行學習。離散數學涉及知識點多并且具有一定難度，學生很難對它產生興趣。教師可以用ACM競賽的形式展現課程內容，模擬ACM競賽環境，從而提高同學們的學習興趣，學習致用，使得學生能夠充滿熱情地把每一個知識點理解透徹。

（2）作業形式考核

在學完一章節后，教師要布置一定的作業讓學生課外完成。要求每個學生在規定時間內獨立完成作業，提交作業。教師根據學生的課外作業制訂考核標準。根據作業考核標準，教師給學生的作業予以考核評判。最后，根據每次作業的評判，教師最后給予綜合評判。

（3）基于 ACM 模式的實驗教學

離散數學的內容很多，為了解決實際教學中出現了課時少和教學內容多的矛盾，提高學生學習興趣，加入實驗教學環節。離散數學上機實驗應側重編程思想的掌握和運用，利用 VC++、Java 或其他語言完成這些實驗，做到理論與應用的完美結合[7]。實驗課程的加入幫助學生對相應知識點的深入理解與消化，并且引導學生運用所學離散數學知識分析和解決實際問題，進一步加深對離散數學在計算機解決問題中重要作用的理解，提高軟件開發能力。將高度抽象的離散數學理論與編程等結合起來，能夠極大地提高學生學習離散數學的積極性，增強解決實際問題的信心。

（4）跨學科的實訓

在實訓環節上，除了讓學生做一些實驗題目外，同時對學生在數據結構、JAVA、C++等其他課程上進行實訓，運用不同的語言，與這些課程結合起來來完成教學內容。

4.結束語

ACM模式的實踐教學可以夯實學生的程序設計基礎，對于離散結構的學習有著重要意義。它把對理論知識的學習與實際的應用有機的結合起來，注重培養學生的編程能力，訓練學生的解題思維，對于培養學生的創新能力具有很大的幫助。通過對離散結構實驗教學的改革，取得了顯著的效果，提高了教學質量和教學水平，對軟件開發類課程的教學改革有一定的示范作用。

參考文獻：

[1]金保華，閆紅巖，張曉娟，徐紅霞.基于ACM/ICPC的程序設計語言的教學改革與實踐[J].中國電力教育，2011，20：79-80.

[2]武建華.基于ACM模式的數據結構實踐教學改革與探索[J].計算機教育，2007，

24：114-116.

[3]房明磊，蔣利華.離散數學教學的探討與思考[J].新西部（下半月），2007，01：239-240.

[4]肖利芳，段梅.離散數學教學模式的改進與創新[J].中國電力教育，2014，11：129-131.

[5]陳博.基于ACM模式的教學方案研究[J].咸寧學院學報，2010，09：131-132.

[6]常子楠.基于ACM模式的程序設計類課程實踐教學探索[J].計算機教育，2010，1 6：144-146.

[7]何立群，廖慧芬.基于ACM模式的算法教學的探索[J].電腦知識與技術，2009，34：9 765-9766.

基金項目：

中央高校基本科研業務費專項資金項目（2013CBQ03）；黑龍江省教育廳科學技術研究項目（12513016）；黑龍江省自然科學基金項目（F201347）；哈爾濱市科技創新人才專項資金項目（2013RFQXJ100）；東北林業大學重點課程建設基金；