楊春明 陳念年

摘要:本文分析了程序設(shè)計(jì)競賽的特點(diǎn)及算法分析與設(shè)計(jì)課程教學(xué)中存在的問題,利用程序在線評測平臺,提出了基于程序設(shè)計(jì)競賽的教學(xué)模式,并在教學(xué)中進(jìn)行了實(shí)踐。

關(guān)鍵詞:程序設(shè)計(jì)競賽;在線評測;計(jì)算機(jī)算法;教學(xué)改革

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:A

1程序設(shè)計(jì)競賽

近年來,針對大學(xué)生的程序設(shè)計(jì)競賽開展得越來越多,比較常見的有ACM-ICPC、TopCoder、百度之星、Google挑戰(zhàn)賽等。其中ACM-ICPC (ACM International Collegiate Programming Contest)即ACM國際大學(xué)生程序設(shè)計(jì)競賽,是歷史最悠久、規(guī)模最大的競賽。

由于程序設(shè)計(jì)競賽具有開放性、綜合性和評判的客觀性特征,可以有效檢驗(yàn)參賽選手綜合應(yīng)用知識分析和解決問題的能力,因此它不僅培養(yǎng)參賽選手的創(chuàng)造力和團(tuán)隊(duì)合作精神,而且也檢測選手們在壓力下進(jìn)行創(chuàng)新思維和理性實(shí)踐的能力。通過參與比賽,學(xué)生提高了利用計(jì)算機(jī)求解問題和程序設(shè)計(jì)的能力,形成積極向上的自主學(xué)習(xí)氛圍。

在程序設(shè)計(jì)競賽中,在線評測系統(tǒng)是開展競賽的核心。它是一個(gè)在線程序與算法設(shè)計(jì)的練習(xí)和競賽平臺,提供大量程序和算法設(shè)計(jì)的題目,供學(xué)生練習(xí)或競賽,學(xué)生可以使用自己熟悉的語言提交程序代碼,系統(tǒng)編譯提交代碼,如果沒有錯(cuò)誤,則生成可執(zhí)行文件,并利用系統(tǒng)的測試用例來測試,如果輸出結(jié)果正確,則返回程序消耗的內(nèi)存空間和時(shí)間。對于競賽題目,系統(tǒng)可以從程序正確性、運(yùn)行總時(shí)間、消耗內(nèi)存空間、返回結(jié)果等方面來考察學(xué)生提交的代碼,且支持多種語言。系統(tǒng)可以實(shí)現(xiàn)在制定的時(shí)間段提供競賽的功能,根據(jù)學(xué)生解題數(shù)目和時(shí)間進(jìn)行排名,也可以批量導(dǎo)出學(xué)生代碼,進(jìn)行分析。在線評測系統(tǒng)除了能用于程序設(shè)計(jì)競賽外,還可以廣泛用于輔助程序設(shè)計(jì)類課程的教學(xué),為學(xué)生提供一個(gè)開放的、自主學(xué)習(xí)的實(shí)驗(yàn)環(huán)境。

2基于競賽模式的算法分析與教學(xué)設(shè)計(jì)

2.1 “算法分析與設(shè)計(jì)”課程的特點(diǎn)

計(jì)算機(jī)專業(yè)要培養(yǎng)具備較強(qiáng)程序設(shè)計(jì)能力的程序員,需要掌握高級程序設(shè)計(jì)語言及數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)策略及設(shè)計(jì)模式、軟件體系結(jié)構(gòu)及開發(fā)方法等知識?！八惴ǚ治雠c設(shè)計(jì)”是面向設(shè)計(jì)的核心課程,主要通過介紹常見的算法設(shè)計(jì)策略及復(fù)雜性分析方法,培養(yǎng)學(xué)生分析和解決問題的能力,為開發(fā)高效的軟件系統(tǒng)奠定堅(jiān)實(shí)的基礎(chǔ)。該課程理論與實(shí)踐并重,內(nèi)容具有綜合性、廣泛性和系統(tǒng)性,是一門集應(yīng)用性、創(chuàng)造性及實(shí)踐性融為一體的課程。主要內(nèi)容包括算法效率分析基礎(chǔ)、分治法、貪心法、動(dòng)態(tài)規(guī)劃、分支限界、回溯、近似算法、概率算法等常見的算法設(shè)計(jì)策略,也覆蓋了排序、搜索、圖論、幾何、組合、數(shù)值計(jì)算等問題,這也是程序設(shè)計(jì)競賽中常見的核心問題。因此,該課程在強(qiáng)調(diào)算法的設(shè)計(jì)思想和方法的同時(shí),需要更加注重算法的應(yīng)用和實(shí)現(xiàn),教會(huì)學(xué)生如何利用計(jì)算機(jī)創(chuàng)造性地解決問題,培養(yǎng)學(xué)生獨(dú)立分析和解決問題的能力。

目前,該課程的教學(xué)方法還是以傳統(tǒng)的講解為主,教師通常只是將已有的經(jīng)典算法在已有的數(shù)學(xué)模型和數(shù)據(jù)結(jié)構(gòu)上片面地解釋給學(xué)生;在實(shí)踐環(huán)節(jié)只是盲目的驗(yàn)證算法,而對該算法的運(yùn)行效率、測試數(shù)據(jù)規(guī)模以及實(shí)際的應(yīng)用場景則很少考慮。學(xué)生的學(xué)習(xí)則主要以理解和記憶為主,沒有“理解”和“消化”,不能靈活運(yùn)用算法;在實(shí)踐環(huán)節(jié),學(xué)生代碼抄襲嚴(yán)重,很難達(dá)到訓(xùn)練的效果。這種教學(xué)模式下,學(xué)生缺乏問題抽象能力,在遇到實(shí)際問題時(shí)無從下手,思維創(chuàng)新能力和實(shí)踐能力難以得到有效的提高。

針對以上問題,筆者利用程序設(shè)計(jì)競賽模式和在線評測系統(tǒng)的特點(diǎn),來彌補(bǔ)課程教學(xué)中的不足,探討“算法分析與設(shè)計(jì)”的課程教學(xué)改革,培養(yǎng)高水平的創(chuàng)新型IT人才。

2.2基于程序設(shè)計(jì)競賽的算法分析與設(shè)計(jì)教學(xué)模式

程序設(shè)計(jì)競賽具有一定的時(shí)效性、開放性和評判的客觀性,學(xué)生通過競賽可以有效提高問題求解和程序設(shè)計(jì)能力。“算法分析與設(shè)計(jì)”課程通過介紹一些具體問題(如排序問題、檢索問題、路徑問題、組合問題等)的解決策略,讓學(xué)生掌握算法的設(shè)計(jì)策略和分析方法。把這些問題編制成在線評測系統(tǒng)上的競賽題目,在指定的時(shí)間內(nèi)以競賽方式開展實(shí)驗(yàn)或考核,讓學(xué)生提交解決問題的程序代碼,最后再導(dǎo)出學(xué)生代碼進(jìn)行分析。為了避免學(xué)生大規(guī)模的代碼抄襲,可以使用代碼甄別系統(tǒng),該系統(tǒng)可判斷代碼的雷同率,有效分析學(xué)生代碼的抄襲程度。教學(xué)基本模式(圖1)以“競賽題目”為中心,通過課堂教學(xué)和課后實(shí)踐兩個(gè)環(huán)節(jié),讓學(xué)生掌握算法分析方法和常見的算法設(shè)計(jì)方法,并應(yīng)用到實(shí)際問題中,訓(xùn)練學(xué)生的程序設(shè)計(jì)能力。

競賽題目的設(shè)計(jì)是課程教學(xué)的核心。題目設(shè)計(jì)應(yīng)注意難度適中、內(nèi)容新穎、能有效激發(fā)學(xué)生的學(xué)習(xí)興趣,更重要的是要融入一種或多種算法設(shè)計(jì)策略,創(chuàng)造一種與現(xiàn)實(shí)應(yīng)用緊密結(jié)合的環(huán)境;同時(shí)提供具有一定規(guī)模的一組或多組測試數(shù)據(jù),以測試算法的效率。另外,設(shè)計(jì)題目時(shí)還應(yīng)考慮學(xué)生水平的差異,對于能力強(qiáng)的學(xué)生,在完成基本要求的基礎(chǔ)上,再增加一些有難度的問題,并引導(dǎo)學(xué)生自主研究新的問題解決方法,激發(fā)學(xué)生的創(chuàng)新能力。在具體實(shí)施時(shí),考慮提供多個(gè)難易程度不一樣的題目,如可分為基本算法的驗(yàn)證、基本應(yīng)用、綜合應(yīng)用三個(gè)層次,一些為必選,一些為可選,讓學(xué)生選擇完成,因材施教。如合并排序、快速排序可作為基本算法的驗(yàn)證,最近點(diǎn)對和凸包問題可作為分治法的基本應(yīng)用,而挑棒游戲可作為動(dòng)態(tài)規(guī)劃策略中求解有向圖傳遞閉包的Warshall算法的綜合應(yīng)用。

課堂教學(xué)重點(diǎn)應(yīng)放在指導(dǎo)學(xué)習(xí)方法,根據(jù)任務(wù)引導(dǎo)學(xué)生理解算法設(shè)計(jì)的基本策略與分析的基本思路;通過具體實(shí)例解析一些經(jīng)典算法,讓學(xué)生討論算法在求解該任務(wù)時(shí)的效率,分析方法的優(yōu)劣及適用場景;注意對問題進(jìn)行歸類,揭示算法設(shè)計(jì)策略的規(guī)律,使學(xué)生觸類旁通;采用啟發(fā)式提問,運(yùn)用富有思考性的問題,引導(dǎo)學(xué)生自己去分析、解決問題。在題目求解方案找到后,適時(shí)地開展課堂討論,引導(dǎo)學(xué)生對方案提出疑問,討論算法的效率及實(shí)際應(yīng)用場景,激發(fā)學(xué)生探求新的解決思路,讓學(xué)生對各種方法加以評價(jià);啟發(fā)學(xué)生的思維,加深對問題的理解。

2.3基于程序設(shè)計(jì)競賽的教學(xué)模式的優(yōu)勢

(1) 提供了開放的、自主學(xué)習(xí)的實(shí)驗(yàn)環(huán)境。通過網(wǎng)絡(luò)使用,學(xué)生可以隨時(shí)提交程序代碼,并可在豐富的程序與算法設(shè)計(jì)題庫中尋找合適的題目,訓(xùn)練程序設(shè)計(jì)能力。

(2) 有效訓(xùn)練了學(xué)生的程序設(shè)計(jì)能力,培養(yǎng)創(chuàng)新型IT人才?！八惴ǚ治雠c設(shè)計(jì)”的學(xué)習(xí)難點(diǎn)在于如何將常見的算法策略應(yīng)用到實(shí)際環(huán)境中。通過三個(gè)層次(算法驗(yàn)證、基本應(yīng)用、綜合應(yīng)用)的實(shí)踐訓(xùn)練,讓學(xué)生熟練掌握常見的算法設(shè)計(jì)策略,加深對各種算法設(shè)計(jì)策略的認(rèn)識,理解算法的意義及精髓,達(dá)到學(xué)以致用。

(3) 形成良好的學(xué)習(xí)氛圍,加強(qiáng)學(xué)生之間的交流。使用在線評測系統(tǒng)進(jìn)行課程考核并舉辦程序與算法設(shè)計(jì)競賽,以團(tuán)隊(duì)方式參與,可以形成良好的校園競爭和交流的學(xué)習(xí)氛圍;學(xué)生有了在課余時(shí)間自主進(jìn)行本學(xué)科知識鉆研的機(jī)會(huì)和環(huán)境;也讓學(xué)生體驗(yàn)團(tuán)隊(duì)協(xié)作的重要性,為軟件項(xiàng)目團(tuán)隊(duì)化的合作要求做好準(zhǔn)備。

3教學(xué)實(shí)踐及實(shí)效

在筆者的教學(xué)實(shí)踐中,采用了北京大學(xué)的POJ搭建了程序在線評測平臺,并在近兩年的算法分析與設(shè)計(jì)課程中利用該教學(xué)模式進(jìn)行了改革,取得了很好的效果。為了更全面的訓(xùn)練學(xué)生的程序設(shè)計(jì)能力,課程考核采用了過程考核、課程報(bào)告、出勤三部分綜合考查的考核方案,三部分分別占總成績的70%、20%、10%。過程考核考察學(xué)生對算法設(shè)計(jì)策略的掌握程度,一共安排4次,每次以競賽的方式進(jìn)行,共計(jì)24道試題,每次選做3～5道,共計(jì)選做15道,每次考核中均有1～2道稍有難度的試題,內(nèi)容覆蓋了簡單算法、分治法、減治法、變治法、時(shí)空權(quán)衡、動(dòng)態(tài)規(guī)劃、貪婪策略、回溯和分支限界等。課程報(bào)告考察學(xué)生綜合應(yīng)用算法分析和設(shè)計(jì)方法的能力,為9選1,根據(jù)所選題目撰寫詳細(xì)的解題報(bào)告。

在最近的一次教學(xué)中,筆者對教學(xué)班上66名同學(xué)進(jìn)行了問卷調(diào)查,調(diào)查學(xué)生對教學(xué)改革的滿意度、可取之處和不足。調(diào)查結(jié)果如表1、表2、表3所示:

從調(diào)查結(jié)果可以看出,學(xué)生的滿意度很高,表明學(xué)生對此教學(xué)模式的認(rèn)同度較高。從每次考核代碼雷同甄別情況看,代碼雷同率90%以上的低于10%,學(xué)生在POJ上做題的積極性也很高,常常會(huì)有1/3的非教學(xué)班同學(xué)參與每次考核?？梢娺@種注重過程的考核方式在教學(xué)中取得了很好的教學(xué)效果。

4結(jié)論

基于在線評測系統(tǒng)的程序設(shè)計(jì)競賽具開放性和評判客觀性的特點(diǎn),教師結(jié)合“算法分析與設(shè)計(jì)”課程的特點(diǎn),將程序競賽模式應(yīng)用到課程的教學(xué)中,可以有效訓(xùn)練和考察學(xué)生的程序設(shè)計(jì)能力,還可以激發(fā)學(xué)生的學(xué)習(xí)興趣。當(dāng)然,在該教學(xué)模式的實(shí)踐中,應(yīng)注意每次考核或?qū)嶒?yàn)題目的選擇要緊密結(jié)合課程知識點(diǎn)和實(shí)際應(yīng)用;在實(shí)踐過程中注重與學(xué)生的交流,激發(fā)學(xué)生學(xué)習(xí)熱情,注重教學(xué)過程,促進(jìn)學(xué)生掌握算法的精髓。

參考文獻(xiàn):

[1] 王卓威,尹寶林. 一個(gè)基于網(wǎng)絡(luò)的程序自動(dòng)評測系統(tǒng)[J]. 北京航空航天大學(xué)學(xué)報(bào),2004,30(6):502-505.

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

[3] 王素立,白首華. 算法分析與設(shè)計(jì)教學(xué)方法[J]. 湘潭師范學(xué)院學(xué)報(bào):自然科學(xué)版,2005(9):124-127.

[4] Alex Aiken. A System for Detecting Software Plagiarism[EB/OL]. http://theory.stanford.edu/～aiken/moss/.

[5] Anany Levitin. 算法設(shè)計(jì)與分析基礎(chǔ)[M]. 潘彥,譯. 2版. 北京: 清華大學(xué)出版社,2007.

[6] 李文新,郭煒. 北京大學(xué)程序在線評測系統(tǒng)及其應(yīng)用[J]. 吉林大學(xué)學(xué)報(bào):信息科學(xué)版,2005,23(8):170-177.

The Teaching Exploration and Practice of Algorithm Analysis and Design base on Programming Contest

YANG Chun-ming, CHEN Nian-nian

(School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: This paper analyzes the characteristics of program contest and the problem of algorithm analysis and design in teaching, and puts forwards a staged and validated teaching method base on programming contest.

Key words: programming contest; online judge; computer algorithm; teaching reform