“算法分析與設計”任務驅動教學模式改革與實踐

楊春明

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

關鍵詞:任務驅動;在線評測;代碼雷同;教學改革

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

1引言

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

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

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

2注重教學過程及考核的“任務驅動”教學模式實踐

2.1 “任務驅動”教學基本模式

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

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

2.2面向應用的任務設計

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

(1) 課堂教學中的任務設計

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

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

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

任務一:劃分傳遞閉包的階段?

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

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

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

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

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

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

任務:挑棒游戲

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

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

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

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

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

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

2.4注重過程的考核及評分標準改革實踐

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

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

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

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

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

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

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

3小結

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

參考文獻:

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

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

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

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

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

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