“算法設(shè)計(jì)與分析”教學(xué)模式探討

徐曉華 何 萍 陳 崚 胡孔法

摘要:本文提出在教學(xué)過(guò)程中采用結(jié)合學(xué)習(xí)興趣、當(dāng)堂練習(xí)、因材施教和多維教學(xué)的四位一體的教學(xué)模式,提高“算法設(shè)計(jì)與分析”課程的教學(xué)質(zhì)量,并對(duì)其考核方式提出了建議。

關(guān)鍵詞:算法設(shè)計(jì)與分析;計(jì)算機(jī)專(zhuān)業(yè);教學(xué)

中圖分類(lèi)號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:A

1引言

“算法設(shè)計(jì)與分析”是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的一門(mén)核心高階課程。在學(xué)習(xí)該課程之前,學(xué)生們已經(jīng)掌握了基本的數(shù)據(jù)結(jié)構(gòu)知識(shí),能熟練運(yùn)用一門(mén)或多門(mén)編程語(yǔ)言,并具備了一定的編程經(jīng)驗(yàn)。但是如何利用這些已學(xué)過(guò)的知識(shí),對(duì)不同的實(shí)際問(wèn)題設(shè)計(jì)出有效的算法,就是本門(mén)課程所要達(dá)到的教學(xué)目標(biāo)。

筆者在“算法設(shè)計(jì)與分析”教學(xué)中,不斷探索和總結(jié)教學(xué)經(jīng)驗(yàn),在教學(xué)過(guò)程中采用學(xué)習(xí)興趣、當(dāng)堂練習(xí)、因材施教和多維教學(xué)四位一體的教學(xué)模式,從而有利于學(xué)生對(duì)教學(xué)內(nèi)容的吸收和掌握,取得了良好的教學(xué)效果。

2四位一體的教學(xué)模式

“算法設(shè)計(jì)與分析”作為一門(mén)理論與實(shí)踐緊密結(jié)合的課程,要讓學(xué)生把兩方面都學(xué)好具有一定的難度。在教學(xué)過(guò)程中,教師應(yīng)該從學(xué)習(xí)興趣、當(dāng)堂練習(xí)、因材施教和多維教學(xué)四個(gè)方面將教學(xué)模式有機(jī)地協(xié)調(diào)為一個(gè)整體,使學(xué)生在享受學(xué)習(xí)的過(guò)程中提高自己的算法設(shè)計(jì)和分析能力。

2.1引導(dǎo)學(xué)生的學(xué)習(xí)興趣,激發(fā)學(xué)習(xí)主動(dòng)性

如果學(xué)生對(duì)一門(mén)課程完全沒(méi)有興趣,無(wú)論教師把教案?jìng)涞萌绾紊钊霚\出,學(xué)生也對(duì)之置若罔聞。反之,如果學(xué)生對(duì)算法或程序設(shè)計(jì)感興趣,即使沒(méi)有老師教他,也不代表他不能自學(xué)成才。因此作為一名負(fù)責(zé)任的任課教師,首當(dāng)其沖要做好的工作就是培養(yǎng)學(xué)生對(duì)本門(mén)課程的興趣。

“算法設(shè)計(jì)與分析”,顧名思義分為算法設(shè)計(jì)與算法分析兩大部分,但實(shí)際上,教師在教學(xué)時(shí)常常主要偏重于算法設(shè)計(jì)這一方面,而對(duì)算法分析輕描淡寫(xiě)、一筆帶過(guò)。原因很簡(jiǎn)單,因?yàn)樗惴ǚ治錾婕八惴◤?fù)雜性理論、艱澀難懂,當(dāng)前大多數(shù)不喜歡數(shù)學(xué)的學(xué)生對(duì)此完全沒(méi)有興趣、也接受不了。但是這些理論是涉及算法設(shè)計(jì)和算法評(píng)價(jià)的根本因素,作為教師必須要向?qū)W生傳達(dá)算法復(fù)雜性理論的重要性。對(duì)此,我們可以在介紹理論的過(guò)程中穿插一些大師的生平故事甚至傳聞?shì)W事,降低學(xué)生對(duì)枯燥理論的反感程度。例如,我們可以結(jié)合算法復(fù)雜度理論,講算法設(shè)計(jì)大師Donald E. Knuth的求學(xué)經(jīng)歷,所著著作TAOCP以及對(duì)TeX的貢獻(xiàn)等。借由學(xué)生對(duì)偉大人物的欣賞和崇拜之情,激發(fā)他們對(duì)所教內(nèi)容的學(xué)習(xí)熱情。

相比之下,“算法設(shè)計(jì)與分析”的另一方面——實(shí)踐,對(duì)于培養(yǎng)學(xué)生興趣則要容易得多,有時(shí)甚至無(wú)需培養(yǎng)。因?yàn)閷W(xué)生在自己動(dòng)手做實(shí)驗(yàn)的同時(shí),本身就有莫大的成就感來(lái)促成其學(xué)習(xí)興趣的產(chǎn)生。但是,我們還是要采取適當(dāng)?shù)氖侄蝸?lái)幫助那些連上機(jī)也不愿意的學(xué)生產(chǎn)生學(xué)習(xí)興趣。其中,最簡(jiǎn)單的方法就是把漂亮的吸引人的程序設(shè)計(jì)成果,尤其是時(shí)下流行的實(shí)際應(yīng)用演示給學(xué)生們看。例如,我們?cè)谥v動(dòng)態(tài)規(guī)劃的時(shí)候,可以在NCBI網(wǎng)站上,演示如何用Blast程序從龐大的數(shù)據(jù)庫(kù)中快速地搜索出與給定基因序列相似的所有序列;或者在講最短路徑地時(shí)候,先演示一下如何在Google Maps中計(jì)算從源點(diǎn)到目的地的最短路徑。此外,考慮到現(xiàn)在的學(xué)生好勝心較強(qiáng),我們還可以配套開(kāi)設(shè)ACM程序設(shè)計(jì)實(shí)驗(yàn)課,讓學(xué)生把已學(xué)的算法知識(shí)用于挑戰(zhàn)解決一些具有一定難度的ACM題目,從而起到加強(qiáng)鍛煉學(xué)生的編程能力和提高學(xué)生的學(xué)習(xí)熱情的目的。例如,北京大學(xué)的ACM/ICPC Judge Online就是一個(gè)很好的ACM在線題庫(kù),教師可以鼓勵(lì)或組織學(xué)生在線練習(xí)、提交程序,系統(tǒng)則會(huì)自動(dòng)判斷程序是否正確。

在講解具體的算法設(shè)計(jì)方法時(shí),教師還應(yīng)注意教學(xué)內(nèi)容的及時(shí)更新,并有意識(shí)地培養(yǎng)學(xué)生對(duì)算法思想的應(yīng)用能力。所謂教學(xué)內(nèi)容的更新,是指不能總是停留在對(duì)經(jīng)典算法的講解層面上,而是要結(jié)合當(dāng)前涌現(xiàn)的一些新算法(比如Blast,PageRank等算法),讓學(xué)生深刻地感受到這些設(shè)計(jì)方法是具有普適性,是所有算法(無(wú)論是新的還是老的)的靈魂,而不僅僅限于那些老生常談的經(jīng)典算法。例如,在講二分查找算法時(shí),教師就可以用2006年Joshua Bloch發(fā)現(xiàn)大量的二分查找的實(shí)現(xiàn)中都有bug的實(shí)例,來(lái)讓學(xué)生們了解算法的發(fā)展同樣也是與時(shí)俱進(jìn)的。而所謂培養(yǎng)學(xué)生對(duì)算法思想的應(yīng)用能力,是指要鍛煉學(xué)生有運(yùn)用舊方法來(lái)解決新問(wèn)題的靈活應(yīng)變能力,而不僅僅是就事論事,這需要大量的練習(xí)來(lái)完成這一目標(biāo)。教師也可以參考Ron Shamir的“分子生物學(xué)中的算法”這一課程,適當(dāng)?shù)刂v解一些將算法的基本設(shè)計(jì)方法應(yīng)用到實(shí)際生物信息學(xué)的例子,讓學(xué)生有感性的認(rèn)識(shí)。

教師通過(guò)培養(yǎng)學(xué)生興趣和提高他們對(duì)算法的感性認(rèn)識(shí)來(lái)提高教學(xué)質(zhì)量,與公司通過(guò)產(chǎn)品推介來(lái)吸引買(mǎi)家,本質(zhì)上是相通的。學(xué)生對(duì)課程產(chǎn)生了自主學(xué)習(xí)的興趣,那么教學(xué)工作的開(kāi)展就會(huì)事半功倍,就好比用戶(hù)本身對(duì)公司的產(chǎn)品產(chǎn)生了購(gòu)買(mǎi)欲望,那么銷(xiāo)售工作的開(kāi)展自然也是順?biāo)浦邸?/p>

2.2通過(guò)當(dāng)堂練習(xí),及時(shí)反映存在問(wèn)題

“算法設(shè)計(jì)與分析”這門(mén)課程不但包括對(duì)學(xué)生理論知識(shí)的灌輸,而且還包括對(duì)學(xué)生的算法實(shí)現(xiàn)能力的培養(yǎng)。因?yàn)閷?duì)于學(xué)生而言,理解是一回事,實(shí)現(xiàn)是另一回事。理解的只是一個(gè)大概、一個(gè)總貌,而實(shí)現(xiàn)卻需要考慮方方面面、各個(gè)細(xì)節(jié)。只有當(dāng)學(xué)生能夠熟練地把算法在計(jì)算機(jī)上編寫(xiě)出來(lái)、運(yùn)行無(wú)誤,才能說(shuō)他是真正理解了,而不僅僅是紙上談兵。然而目前由于教學(xué)時(shí)間的限制,教師大多把上機(jī)練習(xí)安排為學(xué)生自己練習(xí)理論課上的內(nèi)容或者是課后作業(yè)。在實(shí)踐中,我們發(fā)現(xiàn)花適量的時(shí)間讓學(xué)生做一定的課上練習(xí),是非常必要也是非常重要的,原因主要有二:

(1) 真實(shí)反映學(xué)生掌握情況。與課后練習(xí)相比,當(dāng)堂練習(xí)更能夠真實(shí)地反映學(xué)生對(duì)測(cè)試內(nèi)容的掌握情況和熟悉程度。因?yàn)樵谡n后作業(yè)中,經(jīng)常出現(xiàn)一些偷懶的學(xué)生通過(guò)抄襲來(lái)完成自己的作業(yè)現(xiàn)象,如果教師單以課后作業(yè)的完成情況來(lái)判斷學(xué)生對(duì)知識(shí)的掌握程度,得到的結(jié)果可能會(huì)過(guò)于樂(lè)觀。而當(dāng)堂練習(xí)則可較好地彌補(bǔ)這一缺陷,教師通過(guò)在課上當(dāng)場(chǎng)布置一個(gè)或多個(gè)作業(yè),讓學(xué)生們寫(xiě)在紙上很快地交上來(lái),基于這種作業(yè)完成情況的評(píng)價(jià)會(huì)更加真實(shí)反映學(xué)生究竟在哪些方面存在著共同的問(wèn)題或個(gè)別的問(wèn)題,然后教師可逐個(gè)針對(duì)解決。

(2) 凸顯差距,激發(fā)競(jìng)爭(zhēng)氛圍。在當(dāng)堂練習(xí)過(guò)程中,教師可以挑選一個(gè)或兩個(gè)優(yōu)秀的學(xué)生在黑板上來(lái)做練習(xí)題。當(dāng)前的大學(xué)生有著強(qiáng)烈的表現(xiàn)欲望,渴望得到別人的關(guān)注,教師可以利用大學(xué)生的這一心理特點(diǎn),在課上有意地營(yíng)造適當(dāng)?shù)母?jìng)爭(zhēng)氣氛、調(diào)動(dòng)學(xué)生的積極性。與此同時(shí),通過(guò)學(xué)生在黑板上做演示,也能讓一些后進(jìn)的同學(xué)真實(shí)地感受到自己和別人的差距,在好勝心理的驅(qū)使下,有可能會(huì)成為其奮起直追的學(xué)習(xí)動(dòng)力。

考慮到課堂時(shí)間有限的因素,教師在事先設(shè)計(jì)當(dāng)堂練習(xí)的時(shí)候,應(yīng)注意將練習(xí)的難度設(shè)置為比一般課后作業(yè)的難度相對(duì)稍低一些,例如以填空方式或者只要求寫(xiě)算法思想等等。

2.3設(shè)計(jì)遞進(jìn)式難度課后習(xí)題,因材施教

盡管“算法設(shè)計(jì)與分析”這門(mén)課程是針對(duì)已經(jīng)接受了三年或更多計(jì)算機(jī)專(zhuān)業(yè)教育的學(xué)生所開(kāi)設(shè)的,我們?nèi)匀徊荒芎鲆晫W(xué)生之間還是存在著一定的基本功或能力參差不齊的狀況。因此,我們建議教師在設(shè)計(jì)課后習(xí)題時(shí),應(yīng)根據(jù)學(xué)生能力的不同,將作業(yè)的完成要求相應(yīng)地劃分成若干個(gè)由易入難的不同等級(jí)。例如,有的學(xué)生本身對(duì)以前學(xué)過(guò)的課程就一知半解,那么教師就應(yīng)將習(xí)題的最低難度設(shè)為能夠重新掌握以前的基礎(chǔ)知識(shí);相反地,同時(shí)也有些學(xué)生早已超前學(xué)過(guò)了很多算法知識(shí)、具有很強(qiáng)編程能力,那么此時(shí),教師就應(yīng)該將習(xí)題難度的上限設(shè)置得更具挑戰(zhàn)性一點(diǎn),防止優(yōu)秀學(xué)生因自滿而止步不前。

設(shè)計(jì)這種進(jìn)階式的訓(xùn)練,有利于幫助學(xué)生認(rèn)清自己當(dāng)前的能力水平,了解與其他同學(xué)的差距,從而更好地制定自己的階段性學(xué)習(xí)計(jì)劃。教師在布置這些進(jìn)階訓(xùn)練以及講解的過(guò)程中,則宜采取表?yè)P(yáng)先進(jìn)、鼓勵(lì)后進(jìn)的方式來(lái)調(diào)動(dòng)學(xué)生積極性,形成良好的互動(dòng)。

2.4靈活使用多種教學(xué)手段

傳統(tǒng)教學(xué)方法的好處在于條理清楚、思路清晰,學(xué)生在教師寫(xiě)板書(shū)的同時(shí)可以進(jìn)行思考并比較結(jié)果是否正確。而現(xiàn)代的多媒體教學(xué)方法的好處則在于節(jié)約時(shí)間,借助于一目了然的圖形化演示使一些課程難點(diǎn)更容易為學(xué)生所理解,而且課件可以讓學(xué)生在課后繼續(xù)學(xué)習(xí)。我們?cè)凇八惴ㄔO(shè)計(jì)與分析”這門(mén)課程中,采取了將傳統(tǒng)教學(xué)方法與現(xiàn)代教學(xué)方法相結(jié)合的手段:將前者用于對(duì)課程節(jié)奏的把握和算法基本思想的闡述,而將后者用于對(duì)算法基本過(guò)程的演示和相應(yīng)例子的評(píng)講。例如,在講解算法的分而治之這一章,教師可以用傳統(tǒng)教學(xué)方法將其基本思想寫(xiě)(或畫(huà))在黑板上,以供學(xué)生隨時(shí)參考;與此同時(shí),也采用多媒體教學(xué)方式來(lái)逐步演示分而治之算法在歸并排序上的應(yīng)用。此外,網(wǎng)上有很多現(xiàn)成的在線教學(xué)資源也可以為教師所充分利用。例如在講解貪婪法時(shí),教師可以直接用網(wǎng)上現(xiàn)成的applet程序,為學(xué)生演示Dijkstra算法如何計(jì)算從源點(diǎn)到其它各頂點(diǎn)的最短距離。

3科學(xué)合理的考核方式

目前對(duì)“算法設(shè)計(jì)與分析”課程的考核方式主要是由平時(shí)考核和期末考核兩部分組成,期末考核基本上采取單一的理論考試形式。我們認(rèn)為,教師們可以考慮將該課程的期末考試分成兩部分來(lái)考核,一部分是理論考試,另一部分則是上機(jī)考試。其中理論考試側(cè)重于對(duì)算法理論和算法思想的考核,而上機(jī)考試則側(cè)重于對(duì)編程能力的考核。例如,上機(jī)考試可采用像ACM程序設(shè)計(jì)比賽一樣的規(guī)則,要求學(xué)生在規(guī)定時(shí)間內(nèi)盡可能多地完成指定的測(cè)試題目,或直接用北大的在線提交系統(tǒng)進(jìn)行評(píng)分。這樣一方面兼顧了不同學(xué)生的不同特長(zhǎng)——即有的學(xué)生數(shù)學(xué)推理能力強(qiáng),但有的學(xué)生卻動(dòng)手能力強(qiáng),另一方面也間接鼓勵(lì)了學(xué)生平時(shí)要多動(dòng)手編程,更深刻地理解算法思想,而不僅僅是死記硬背。

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

“算法設(shè)計(jì)與分析”課程是一門(mén)非常重要的計(jì)算機(jī)專(zhuān)業(yè)課程,具有理論和實(shí)踐并重的特點(diǎn),如何利用學(xué)生已有的知識(shí)和經(jīng)驗(yàn),使其快速掌握一些經(jīng)典算法的設(shè)計(jì)思想,進(jìn)而能夠動(dòng)手實(shí)踐解決一些編程問(wèn)題,是我們?cè)诮虒W(xué)中關(guān)注的重點(diǎn)。教師只有在教學(xué)過(guò)程中不停地總結(jié)教學(xué)經(jīng)驗(yàn),堅(jiān)持不懈地學(xué)習(xí)新的知識(shí),深刻掌握“算法設(shè)計(jì)與分析”的核心思想,提高自身能力,才能讓學(xué)生學(xué)到真正收益終身的算法設(shè)計(jì)思想和方法。

參考文獻(xiàn):

[1]Amy N. Langville, Carl D. Meyer. Google's PageRank and Beyond: The Science of Search Engine Rankings[M]. Princeton University Press, 2006.

[2]Donald Ervin Knuth. The Art of Computer Programming[M]. Addison-Wesley,1997.

[3]Donald Ervin Knuth. The TeXbook[M]. Addison-Wesley,1986.

Discussion on The Teaching Mode of “Algorithm Design and Analysis”

XU Xiao-hua, HE Ping, CHEN Ling, HU Kong-fa

(Department of Computer Science, Yangzhou University, Yangzhou 225009, China)

Abstract: This paper proposes a four-in-one teaching mode, which integrates inspiring students learning interest, quizzing on class, teaching according to the student's ability and combining different teaching tools to improve the quality of teaching “Algorithm design and analysis” course. Besides, some useful suggestions on the form of examination are also provided.

Key words: algorithm design and analysis; computer science, teaching