楊春明

摘要:本文分析了“算法分析與設(shè)計”課程教學(xué)中存在的問題,利用“任務(wù)驅(qū)動”教學(xué)方法,引入ACM/ICPC在線評測平臺,結(jié)合教學(xué)實踐,從任務(wù)設(shè)計、課堂教學(xué)和課程考核等方面探討了一種注重過程和實踐的教學(xué)模式。

關(guān)鍵詞:任務(wù)驅(qū)動;在線評測;代碼雷同;教學(xué)改革

中圖分類號:G642 文獻標(biāo)識碼:B

1引言

“算法分析與設(shè)計”是一門面向設(shè)計的專業(yè)核心課程,是計算機科學(xué)研究的重要領(lǐng)域之一,也是現(xiàn)代軟件系統(tǒng)的核心問題。課程旨在培養(yǎng)學(xué)生分析問題和解決問題的能力,掌握算法設(shè)計及復(fù)雜性分析方法。課程理論與實踐并重,內(nèi)容具有綜合性、廣泛性和系統(tǒng)性,是一門集應(yīng)用性、創(chuàng)造性及實踐性融為一體的綜合性課程。目前,該課程的教學(xué)方法還是以講解為主,通常只將已有的經(jīng)典算法在數(shù)學(xué)模型和數(shù)據(jù)結(jié)構(gòu)上片面地解釋給學(xué)生;在實踐環(huán)節(jié)只盲目地驗證算法,而對該算法的運行效率、測試數(shù)據(jù)的規(guī)模以及實際應(yīng)用場景則很少考慮。學(xué)生的學(xué)習(xí)則主要以理解和記憶的繼承式學(xué)習(xí)為主,雖然記住了大量的算法理論,但沒有“理解”和“消化”,不能靈活運用算法;在實踐環(huán)節(jié)學(xué)生代碼抄襲嚴(yán)重,很難達到訓(xùn)練的效果。在這種教學(xué)模式下,學(xué)生缺乏問題抽象能力,在遇到實際問題時無從下手,思維創(chuàng)新能力和實踐能力難以得到有效的提高。

針對以上問題,文獻[1]從教學(xué)思想及教師角色的轉(zhuǎn)變兩個方面探討了如何在課堂教學(xué)中訓(xùn)練學(xué)生的綜合分析能力。文獻[2～3]對教學(xué)內(nèi)容的選擇、以學(xué)生為中心教學(xué)方式的改變、實驗與課程設(shè)計環(huán)節(jié)的加強、考核形式及評分標(biāo)準(zhǔn)的改革等方面做了探討。筆者在長期的教學(xué)實踐中,結(jié)合課程特點和實際教學(xué),利用“任務(wù)驅(qū)動”教學(xué)方法,引入ACM/ICPC的在線評測系統(tǒng),探討了算法分析與設(shè)計的課程教學(xué)改革。

“任務(wù)驅(qū)動”是一種建立在建構(gòu)主義學(xué)習(xí)理論基礎(chǔ)上的一種教學(xué)方法,是建構(gòu)主義理論在教育教學(xué)中的具體應(yīng)用。這種教學(xué)方法主張教師將教學(xué)內(nèi)容隱含在一個或幾個有代表性的任務(wù)中,以完成任務(wù)作為教學(xué)活動的中心;學(xué)生在完成任務(wù)的動機驅(qū)動下,通過分析和討論任務(wù)涉及的知識及需要解決的問題;在老師的指導(dǎo)下,通過對知識的主動學(xué)習(xí)和應(yīng)用,自主探索來完成任務(wù)。該教學(xué)方法的顯著特點是以訓(xùn)練學(xué)生能力為主,教師的主要功能是“促進學(xué)生學(xué)習(xí),引導(dǎo)學(xué)生成功”,是基于探究學(xué)習(xí)和協(xié)作學(xué)習(xí)的一種教學(xué)模式。

2注重教學(xué)過程及考核的“任務(wù)驅(qū)動”教學(xué)模式實踐

2.1 “任務(wù)驅(qū)動”教學(xué)基本模式

算法分析與設(shè)計的課程內(nèi)容由一些具體問題構(gòu)成(如排序問題、字符串處理問題、查找問題、圖問題、組合問題、幾何問題等),這些問題可看成是“任務(wù)驅(qū)動”教學(xué)法中的“任務(wù)”。在課程教學(xué)中,將具體的算法設(shè)計策略融入到這些“任務(wù)”中;課堂教學(xué)以任務(wù)為主,引導(dǎo)學(xué)生利用算法設(shè)計策略探索解決方案;在課后的實踐環(huán)節(jié),將結(jié)合實際應(yīng)用且融入了知識點的任務(wù)放到ACM/ICPC在線評測系統(tǒng)上,讓學(xué)生在課后根據(jù)任務(wù)描述,自主探索問題解決方案,并提交程序代碼,在線評測系統(tǒng)根據(jù)任務(wù)設(shè)計時的測試數(shù)據(jù)來評價學(xué)生的解決方案;同時,為了避免學(xué)生抄襲代碼,可以將學(xué)生代碼導(dǎo)出后甄別代碼雷同情況。

整個教學(xué)過程以“任務(wù)”為中心,通過課堂教學(xué)和課后實踐兩個環(huán)節(jié)的任務(wù)驅(qū)動,讓學(xué)生在自主探索的過程中掌握算法分析方法和常見的算法設(shè)計策略,并應(yīng)用到實際問題中,訓(xùn)練學(xué)生實踐能力,以達到教學(xué)目標(biāo)。

2.2面向應(yīng)用的任務(wù)設(shè)計

任務(wù)設(shè)計是“任務(wù)驅(qū)動”教學(xué)實施的第一步,也是該方法的核心,要求教師將教學(xué)內(nèi)容和教學(xué)目標(biāo)隱含到具體的任務(wù)中。課堂教學(xué)和實踐環(huán)節(jié)的任務(wù)設(shè)計有著各自的側(cè)重點。

(1) 課堂教學(xué)中的任務(wù)設(shè)計

課堂教學(xué)環(huán)節(jié)的任務(wù)設(shè)計重點是把教學(xué)內(nèi)容和教學(xué)目標(biāo)融入到任務(wù)中,讓學(xué)生在教師的引導(dǎo)下逐步探索該任務(wù)的解決方法,以此掌握某一類算法設(shè)計策略。課堂教學(xué)是一個逐步推進的過程,因此,課堂教學(xué)中的任務(wù)可設(shè)計成多個有遞進關(guān)系的小任務(wù),由易到難,循序漸進地完成,激發(fā)學(xué)生的學(xué)習(xí)興趣。

例如,在講到動態(tài)規(guī)劃算法時,可根據(jù)動態(tài)規(guī)劃求解的一般步驟來設(shè)計任務(wù)。動態(tài)規(guī)劃是解決最優(yōu)性問題一種重要算法設(shè)計策略,是通過尋找問題的遞推關(guān)系來解決問題,教學(xué)的重點是讓學(xué)生掌握尋找遞推關(guān)系式的方法。遞推關(guān)系表明了一些交疊子問題之間的關(guān)系,這些交疊的子問題可看成不同的階段,遞推關(guān)系式表明了階段之間的關(guān)系。動態(tài)規(guī)劃算法的求解步驟為劃分階段、找出階段之間的遞推關(guān)系及初始值、利用初始值求解遞推關(guān)系式。因此,動態(tài)規(guī)劃教學(xué)的任務(wù)設(shè)計按照求解步驟可分成多個由易到難的小任務(wù),通過逐步解決這些任務(wù)來掌握動態(tài)規(guī)劃算法的知識點。

動態(tài)規(guī)劃算法中求解有向圖傳遞閉包的Warshall算法的任務(wù)可設(shè)計為:

任務(wù)一:劃分傳遞閉包的階段?

任務(wù)二:根據(jù)題目要求確定階段之間的遞推關(guān)系及初始條件。

任務(wù)三:根據(jù)遞推關(guān)系描述算法。

任務(wù)四:分析算法的效率,并討論與遍歷方法的效率比較。

(2) 實踐環(huán)節(jié)的任務(wù)設(shè)計

實踐環(huán)節(jié)的任務(wù)設(shè)計重點在綜合應(yīng)用課堂教學(xué)中講授的算法策略,需要面向具體應(yīng)用,且難度適中、內(nèi)容典型新穎、能有效激發(fā)學(xué)生學(xué)習(xí)興趣。這一環(huán)節(jié)的任務(wù)應(yīng)注意創(chuàng)造一種與現(xiàn)實應(yīng)用緊密結(jié)合的任務(wù)環(huán)境,可融入多種算法設(shè)計策略,還應(yīng)考慮提供具有一定規(guī)模的測試數(shù)據(jù),以測試不同算法的效率。

如Warshall算法實踐環(huán)節(jié)的任務(wù)可設(shè)計為:

任務(wù):挑棒游戲

有若干塑料游戲棒散倒在桌子上,玩家要試著把他們一根根取走而不移動其他游戲棒。我們只考慮一對游戲棒之間是不是通過一系列相互搭著的游戲棒相連接。給定N(N>1)根游戲棒的端點列表,請找出所有相連的游戲棒。注意,搭在一起的算相連,但能通過其他相連游戲棒間接相連的也算相連。測試數(shù)據(jù)給多組,每組測試數(shù)據(jù)的規(guī)模不定,這樣可以比較出不同算法的效率。

該任務(wù)初一看跟Warshall算法沒有聯(lián)系,但仔細分析后發(fā)現(xiàn),只要將游戲棒縮小成一個點,如果兩根游戲棒的端點值一樣,則可以看成這兩個點之間有邊相連;這樣散倒在桌子上的游戲棒就變成了一個無向圖,找出所有相連游戲棒的任務(wù)就變成了求出該無向圖的傳遞閉包。該任務(wù)可以有效的訓(xùn)練了學(xué)生理解問題、分析問題、靈活利用所學(xué)算法策略求解問題的能力。

另外,實踐環(huán)節(jié)任務(wù)的設(shè)計除了考慮綜合應(yīng)用外,還應(yīng)考慮到學(xué)生之間水平的差異。一個教學(xué)班上學(xué)生的接受能力、理解能力和動手能力各不相同,應(yīng)區(qū)別對待。對于能力強的學(xué)生,在完成基本要求的基礎(chǔ)上,再增加一些有難度的問題,并引導(dǎo)學(xué)生自主研究新的解決問題的方法,激發(fā)學(xué)生的創(chuàng)新能力。在具體實施時,考慮提供多個難易程度不一樣的任務(wù),一些為必選,一些為可選,讓學(xué)生選擇完成,實現(xiàn)因材施教。

2.3以培養(yǎng)學(xué)生能力為中心的課堂教學(xué)

課程的目標(biāo)是培養(yǎng)學(xué)生算法設(shè)計與分析的能力,只有學(xué)生去思考并實踐了才能很好掌握這些技能。因此,在課堂教學(xué)中應(yīng)改變以往上課時老師唱主角,將大量內(nèi)容“灌輸”給學(xué)生,而不重視學(xué)生反饋和實踐的教學(xué)方式;重點應(yīng)放在指導(dǎo)學(xué)習(xí)方法,根據(jù)任務(wù)引導(dǎo)學(xué)生理解算法設(shè)計的基本策略與分析的基本思路,通過具體實例解析一些經(jīng)典算法,讓學(xué)生討論算法在求解該任務(wù)時的效率,分析方法的優(yōu)劣及適用場景,當(dāng)學(xué)生了解算法設(shè)計的基本方法后,把求知的鑰匙交給學(xué)生。

在課堂教學(xué)中以學(xué)生為中心,注意對問題進行歸類,揭示算法設(shè)計策略的規(guī)律,使學(xué)生觸類旁通;這樣,學(xué)生在碰到實際問題時就不至于茫然,有一套明確的解題思路。在引導(dǎo)學(xué)生探索任務(wù)求解方案時采用啟發(fā)式提問,運用富有思考性的問題,引導(dǎo)學(xué)生積極思考,讓學(xué)生自己去分析問題、解決問題。在任務(wù)求解方案找到后適時地開展課堂討論,引導(dǎo)學(xué)生對方案提出疑問,討論算法的效率及實際應(yīng)用場景,激發(fā)學(xué)生針對一些問題探求新的解決思路,讓學(xué)生對各種方法加以評價;這有助于啟發(fā)學(xué)生的思維,加深對問題的理解。

2.4注重過程的考核及評分標(biāo)準(zhǔn)改革實踐

課程考核是“任務(wù)驅(qū)動”教學(xué)法實施的評價階段,主要評價學(xué)生是否完成了對課程知識點的掌握及靈活應(yīng)用,也是課程教學(xué)的重要階段。目前,該課程的考核基本上分為兩個部分,一部分是平時成績,占30%～40%,主要由作業(yè)和出勤組成;另一部分為期末考試,占60%～70%。這樣的考核方式很難考察學(xué)生的實踐能力,導(dǎo)致大部分學(xué)生只注重期末考試,而忽略學(xué)習(xí)過程,很難有效的提高學(xué)生的創(chuàng)新能力和實踐能力。

算法分析與設(shè)計課程的考核應(yīng)著重考核學(xué)生對常見算法設(shè)計策略的靈活應(yīng)用及效率分析,而不是對算法的死記硬背。對此,在筆者的教學(xué)實踐中,引入ACM/ICPC在線評測系統(tǒng)及代碼雷同判斷系統(tǒng),對課程的考核方式及評分標(biāo)準(zhǔn)作了如下改革:

課程考核分為三部分,分別為課堂討論考核(10%)、常見算法設(shè)計策略的應(yīng)用(過程)考核(60%)、課程報告考核(30%)。

課堂討論考核主要考核學(xué)生的學(xué)習(xí)積極性,包括對提問的回答、學(xué)生提問及討論。在課堂教學(xué)過程中記錄下每位學(xué)生的發(fā)言次數(shù),到期末統(tǒng)計次數(shù),給出相應(yīng)的分?jǐn)?shù)。

常見算法設(shè)計策略的應(yīng)用(過程)考核主要考核學(xué)生的實踐能力,在實踐環(huán)節(jié)完成。這一部分的考核與課堂教學(xué)同步,在ACM/ICPC在線評測系統(tǒng)上進行;在評測系統(tǒng)上提供多道難易程度不一的問題(任務(wù)),讓學(xué)生在規(guī)定時間(如兩周)內(nèi)求解并提交代碼到系統(tǒng)上,要求通過任務(wù)的測試數(shù)據(jù),完成不同的任務(wù)可獲得不同的分?jǐn)?shù)。為了避免代碼抄襲,在一次考核完成后,從在線評測系統(tǒng)中提取學(xué)生代碼,利用代碼雷同判斷系統(tǒng)判斷代碼的雷同率,如果代碼雷同率較高(如90%),則可認(rèn)定為抄襲,計0分。代碼雷同判斷是一個難度較大的工作,筆者這里采用的是Stanford大學(xué)的Moss系統(tǒng),它提供了一個免費的使用接口,通過該接口,可判斷你提交代碼的雷同率[7]。

課程報告考核主要考核學(xué)生算法分析與設(shè)計的綜合能力,在課程結(jié)束后進行。考核時給出多個具有一定綜合性和多種測試數(shù)據(jù)的任務(wù),讓學(xué)生選擇1～2個任務(wù)解決,并撰寫報告。報告內(nèi)容主要包括任務(wù)分析、算法設(shè)計、算法效率分析、算法實現(xiàn)、程序測試及討論組成。根據(jù)學(xué)生撰寫報告內(nèi)容的質(zhì)量來綜合給分。

三個部分的考核綜合考慮了學(xué)生學(xué)習(xí)過程、課程內(nèi)容、教學(xué)目標(biāo)和課程的特點,能有效激發(fā)學(xué)生的學(xué)習(xí)積極性,很好的訓(xùn)練學(xué)生的實踐能力。在筆者多次的實踐中,取得了較好的教學(xué)效果。

3小結(jié)

“任務(wù)驅(qū)動”教學(xué)法能有效的結(jié)合算法分析與設(shè)計的課程內(nèi)容和教學(xué)目標(biāo),它使學(xué)生在任務(wù)的求解過程中掌握了課程的知識點,達到教學(xué)目標(biāo)。文章針對當(dāng)前算法分析與設(shè)計課程教學(xué)中存在的一些問題,利用“任務(wù)驅(qū)動”教學(xué)方法及ACM/ICPC在線評測系統(tǒng),探索了一種注重過程和實踐的“任務(wù)驅(qū)動”教學(xué)模式,并在筆者的課程教學(xué)中多次實踐,取得了較好的效果。

參考文獻:

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

[2] 劉波. “算法設(shè)計與分析”教學(xué)探討[J]. 高等理科教育,2007(4):78-80.

[3] 孫紅麗,葉斌. 淺談算法設(shè)計與分析課程的教學(xué)改革[J]. 太原教育學(xué)院學(xué)報,2005(12):45-47.

[4] 侯海云,李興保. 任務(wù)驅(qū)動教學(xué)理念新解[J]. 中國現(xiàn)代教育裝備,2007(2):98-100.

[5] 曾希君.“任務(wù)驅(qū)動”教學(xué)法在計算機專業(yè)課教學(xué)中的應(yīng)用探索[J]. 計算機教育,2007(9):7-9.

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