基于競賽模式的“算法分析與設(shè)計”教學探索與實踐

楊春明 陳念年

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

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

中圖分類號:G642 文獻標識碼:A

1程序設(shè)計競賽

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

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

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

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

2.1 “算法分析與設(shè)計”課程的特點

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

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

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

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

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

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

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

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

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

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

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

3教學實踐及實效

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

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

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

4結(jié)論

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

參考文獻:

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

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

[3] 王素立,白首華. 算法分析與設(shè)計教學方法[J]. 湘潭師范學院學報:自然科學版,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è)計與分析基礎(chǔ)[M]. 潘彥,譯. 2版. 北京: 清華大學出版社,2007.

[6] 李文新,郭煒. 北京大學程序在線評測系統(tǒng)及其應(yīng)用[J]. 吉林大學學報:信息科學版,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