基于ACM模式的離散數(shù)學(xué)實(shí)驗(yàn)探究

陳宇　臧美英　李林輝

【摘要】離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)核心課程，本文在介紹離散數(shù)學(xué)、ACM及ACM在線評(píng)測(cè)系統(tǒng)的基礎(chǔ)上，提出了基于ACM模式的離散數(shù)學(xué)實(shí)驗(yàn)探究，探討了教學(xué)方式與手段及實(shí)驗(yàn)教學(xué)的改革。這種改革將提高離散數(shù)學(xué)課程的教學(xué)質(zhì)量和教學(xué)水平，有助于培養(yǎng)學(xué)生的抽象思維、邏輯思維、心理素質(zhì)及團(tuán)隊(duì)協(xié)作能力。

【關(guān)鍵詞】離散數(shù)學(xué) 實(shí)踐教學(xué) ACM

【中圖分類號(hào)】G642.0 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】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在線評(píng)測(cè)系統(tǒng)簡(jiǎn)介

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

自2006年我校第一次參與ACM大賽黑龍江省賽至今每年都組織團(tuán)隊(duì)參與比賽，并取得不錯(cuò)成績(jī)，并成立ACM實(shí)驗(yàn)室，讓學(xué)生以精通編程為榮，讓程序編織夢(mèng)想，形成了一個(gè)積極向上的自主學(xué)習(xí)氛圍，一些高校已經(jīng)將ACM在線評(píng)測(cè)系統(tǒng)運(yùn)用到計(jì)算機(jī)課程的教學(xué)環(huán)節(jié)之中并取得了不錯(cuò)的效果。

我校ACM在線評(píng)測(cè)系統(tǒng)界面如圖一所示：

圖1.ACM/ICPC在線評(píng)測(cè)平臺(tái)

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

圖2.ACM評(píng)測(cè)系統(tǒng)功能模塊圖

ACM在線評(píng)測(cè)系統(tǒng)性能上的穩(wěn)定快速為計(jì)算機(jī)專業(yè)各門編程課程提供有效的實(shí)驗(yàn)環(huán)境。

2.結(jié)合ACM模式探索離散結(jié)構(gòu)課程實(shí)踐教學(xué)

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

2.1 建立基于ACM的離散結(jié)構(gòu)教學(xué)模式的意義

1.ACM模式是讓學(xué)生三個(gè)人共用一臺(tái)電腦，通過團(tuán)隊(duì)合作在短時(shí)間內(nèi)解決問題的方法。有利于提高學(xué)生的個(gè)體思維能力，增強(qiáng)學(xué)生們的團(tuán)隊(duì)合作意識(shí)，增進(jìn)學(xué)生們之間的學(xué)術(shù)交流。

2.學(xué)生們通過建立的基于ACM競(jìng)賽的網(wǎng)絡(luò)教學(xué)平臺(tái)進(jìn)行學(xué)習(xí)，每個(gè)人都可以注冊(cè)ID，在平臺(tái)上學(xué)習(xí)離散數(shù)學(xué)的相關(guān)課程，不受時(shí)間和地域的限制。

3.通過ACM模式競(jìng)賽式學(xué)習(xí)，校園之間形成競(jìng)爭(zhēng)，為此，學(xué)校會(huì)營(yíng)造濃厚的學(xué)習(xí)氛圍，在課余時(shí)間對(duì)學(xué)生進(jìn)行培訓(xùn)，旨在讓學(xué)生在課余時(shí)間對(duì)離散數(shù)學(xué)知識(shí)進(jìn)行鉆研 學(xué)習(xí)。

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

2.2基于ACM的離散結(jié)構(gòu)教學(xué)模式的設(shè)計(jì)

ACM模式可以開闊學(xué)生的視野，培養(yǎng)學(xué)生的實(shí)踐能力，團(tuán)隊(duì)合作能力，增強(qiáng)創(chuàng)新意識(shí)[5]?；贏CM模式的離散數(shù)學(xué)實(shí)踐教學(xué)設(shè)計(jì)分為三個(gè)層次：基礎(chǔ)型實(shí)驗(yàn)、綜合型實(shí)驗(yàn)和創(chuàng)新型實(shí)驗(yàn)具體實(shí)現(xiàn)方法如下：

（1）基礎(chǔ)型實(shí)驗(yàn)，主要內(nèi)容是鏈表隊(duì)列或堆棧，掌握命題邏輯中的真值表、聯(lián)接詞、主范式，進(jìn)行真值計(jì)算、關(guān)系閉包計(jì)算，計(jì)算兩點(diǎn)間長(zhǎng)度為m的路的數(shù)目等。要求學(xué)生掌握基本的離散結(jié)構(gòu)和方法，能運(yùn)用離散結(jié)構(gòu)描述實(shí)際對(duì)象并對(duì)其進(jìn)行處理，有較好的問題分析和解決能力。

（2）綜合型實(shí)驗(yàn)，主要內(nèi)容有商品營(yíng)銷傭金問題、學(xué)生管理系統(tǒng)、物資管理系統(tǒng)穿衣排序、中國(guó)郵路問題、巡回售貨員問題等[6]。需要學(xué)生具體掌握算法分析與設(shè)計(jì)，掌握數(shù)理邏輯、集合與關(guān)系理論、圖論的知識(shí)，具有一定的綜合素質(zhì)，有對(duì)知識(shí)的實(shí)際運(yùn)用能力。

（3）創(chuàng)新型實(shí)驗(yàn)，需要學(xué)生掌握基本的軟件重用方法，運(yùn)用面向過程和面向?qū)ο蟮脑O(shè)計(jì)方法。主要內(nèi)容有創(chuàng)新的設(shè)計(jì)完成測(cè)謊儀、電梯系統(tǒng)、TSP問題、自動(dòng)售貨系統(tǒng)、環(huán)游世界問題電報(bào)碼設(shè)計(jì)、著色問題、校園導(dǎo)游系統(tǒng)等問題。其中程序的測(cè)試采用ACM的模式進(jìn)行，保證軟件測(cè)試的質(zhì)量。

創(chuàng)新型實(shí)驗(yàn)這一層次要求較高，對(duì)那些學(xué)有余力、創(chuàng)新性思維強(qiáng)、興趣濃厚的學(xué)生，提供了一些難度較高的項(xiàng)目，有利于學(xué)生申請(qǐng)并完成本科生的科技創(chuàng)新項(xiàng)目，讓他們初步形成軟件從事者應(yīng)具備的工作作風(fēng)和嚴(yán)謹(jǐn)態(tài)度。

3.基于ACM的離散結(jié)構(gòu)教學(xué)模式改革措施

（1）案例教學(xué)

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

（2）作業(yè)形式考核

在學(xué)完一章節(jié)后，教師要布置一定的作業(yè)讓學(xué)生課外完成。要求每個(gè)學(xué)生在規(guī)定時(shí)間內(nèi)獨(dú)立完成作業(yè)，提交作業(yè)。教師根據(jù)學(xué)生的課外作業(yè)制訂考核標(biāo)準(zhǔn)。根據(jù)作業(yè)考核標(biāo)準(zhǔn)，教師給學(xué)生的作業(yè)予以考核評(píng)判。最后，根據(jù)每次作業(yè)的評(píng)判，教師最后給予綜合評(píng)判。

（3）基于 ACM 模式的實(shí)驗(yàn)教學(xué)

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

（4）跨學(xué)科的實(shí)訓(xùn)

在實(shí)訓(xùn)環(huán)節(jié)上，除了讓學(xué)生做一些實(shí)驗(yàn)題目外，同時(shí)對(duì)學(xué)生在數(shù)據(jù)結(jié)構(gòu)、JAVA、C++等其他課程上進(jìn)行實(shí)訓(xùn)，運(yùn)用不同的語(yǔ)言，與這些課程結(jié)合起來來完成教學(xué)內(nèi)容。

4.結(jié)束語(yǔ)

ACM模式的實(shí)踐教學(xué)可以夯實(shí)學(xué)生的程序設(shè)計(jì)基礎(chǔ)，對(duì)于離散結(jié)構(gòu)的學(xué)習(xí)有著重要意義。它把對(duì)理論知識(shí)的學(xué)習(xí)與實(shí)際的應(yīng)用有機(jī)的結(jié)合起來，注重培養(yǎng)學(xué)生的編程能力，訓(xùn)練學(xué)生的解題思維，對(duì)于培養(yǎng)學(xué)生的創(chuàng)新能力具有很大的幫助。通過對(duì)離散結(jié)構(gòu)實(shí)驗(yàn)教學(xué)的改革，取得了顯著的效果，提高了教學(xué)質(zhì)量和教學(xué)水平，對(duì)軟件開發(fā)類課程的教學(xué)改革有一定的示范作用。

參考文獻(xiàn)：

[1]金保華，閆紅巖，張曉娟，徐紅霞.基于ACM/ICPC的程序設(shè)計(jì)語(yǔ)言的教學(xué)改革與實(shí)踐[J].中國(guó)電力教育，2011，20：79-80.

[2]武建華.基于ACM模式的數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)改革與探索[J].計(jì)算機(jī)教育，2007，

24：114-116.

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

[4]肖利芳，段梅.離散數(shù)學(xué)教學(xué)模式的改進(jìn)與創(chuàng)新[J].中國(guó)電力教育，2014，11：129-131.

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

[6]常子楠.基于ACM模式的程序設(shè)計(jì)類課程實(shí)踐教學(xué)探索[J].計(jì)算機(jī)教育，2010，1 6：144-146.

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

基金項(xiàng)目：

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目（2013CBQ03）；黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目（12513016）；黑龍江省自然科學(xué)基金項(xiàng)目（F201347）；哈爾濱市科技創(chuàng)新人才專項(xiàng)資金項(xiàng)目（2013RFQXJ100）；東北林業(yè)大學(xué)重點(diǎn)課程建設(shè)基金；