面向算法設(shè)計(jì)與分析課程的翻轉(zhuǎn)課堂教學(xué)模式研究

陳翔

摘要：以算法設(shè)計(jì)與分析課程為例，結(jié)合翻轉(zhuǎn)課堂的教學(xué)理念，提出一種翻轉(zhuǎn)課堂教學(xué)模式框架。說明具體的教學(xué)內(nèi)容安排，并總結(jié)教學(xué)改革中的經(jīng)驗(yàn)。

關(guān)鍵詞：算法設(shè)計(jì)與分析；翻轉(zhuǎn)課堂；教學(xué)模式

1 背景

算法設(shè)計(jì)與分析課程是計(jì)算機(jī)專業(yè)的核心必修課程。當(dāng)前無論是計(jì)算科學(xué)還是在計(jì)算實(shí)踐，算法都在其中扮演著重要角色。本課程在教學(xué)過程中重點(diǎn)講授計(jì)算機(jī)應(yīng)用中經(jīng)常遇到的實(shí)際問題的解法，講授設(shè)計(jì)和分析各種算法的基本原理、方法和技術(shù)，培養(yǎng)學(xué)生對算法時(shí)間和空間復(fù)雜度進(jìn)行正確分析的能力。學(xué)好算法設(shè)計(jì)與分析這門課程，一方面有助于學(xué)生進(jìn)一步鞏固已經(jīng)學(xué)習(xí)過的知識，例如高級程序設(shè)計(jì)語言和數(shù)據(jù)結(jié)構(gòu)；另一方面也有助于學(xué)生學(xué)好一些后續(xù)專業(yè)課程，例如軟件測試技術(shù)、編譯原理、數(shù)據(jù)庫原理及應(yīng)用等，因?yàn)檫@些課程中的一些較難知識點(diǎn)均與算法密切相關(guān)。

但在實(shí)際的教學(xué)過程中，筆者發(fā)現(xiàn)學(xué)生在學(xué)習(xí)該門課程的時(shí)候面臨很多的問題：①課程教學(xué)內(nèi)容的難度較高，很多知識點(diǎn)的抽象層次高，需要學(xué)生具備一定的數(shù)學(xué)分析能力。在算法的實(shí)現(xiàn)過程中，學(xué)生編程經(jīng)驗(yàn)較為匱乏，很多時(shí)候難以將偽代碼轉(zhuǎn)化為實(shí)際可運(yùn)行的代碼；②學(xué)生知識應(yīng)用能力較弱，雖然能夠理解課堂上講授的知識，但面對新的問題時(shí)，難以將學(xué)到的知識進(jìn)行靈活應(yīng)用；③學(xué)生普遍存在課前不預(yù)習(xí)、課后不復(fù)習(xí)的問題，自學(xué)意識淡薄。

麥可思公司曾對2013屆本科畢業(yè)生就“你認(rèn)為母校的教學(xué)需要改進(jìn)的地方”這一問題進(jìn)行了調(diào)研，調(diào)研的最終匯總結(jié)果如圖1所示。數(shù)據(jù)表明有49%的學(xué)生認(rèn)為已有的教學(xué)“無法調(diào)動(dòng)學(xué)生學(xué)習(xí)興趣”，31%的學(xué)生認(rèn)為“課堂讓學(xué)生參與不夠”。

筆者嘗試將翻轉(zhuǎn)課堂教學(xué)模式引入到算法設(shè)計(jì)與分析課程的教學(xué)中。翻轉(zhuǎn)課堂相對于傳統(tǒng)教學(xué)具有如下優(yōu)點(diǎn)：①在傳統(tǒng)教學(xué)中，教師主要是課堂的主導(dǎo)者和知識的傳授者，而基于翻轉(zhuǎn)課堂教學(xué)模式后，教師更多成為學(xué)生學(xué)習(xí)的引導(dǎo)者和協(xié)助者。由于引入了授課視頻，教師節(jié)省了重復(fù)知識傳授的時(shí)間，可以將更多的時(shí)間投入到學(xué)生作業(yè)的講解、教學(xué)案例的設(shè)計(jì)等環(huán)節(jié)；②學(xué)生成為教學(xué)過程中的主動(dòng)參與者。學(xué)生在課前階段通過觀看視頻，構(gòu)建了相關(guān)專業(yè)知識的基礎(chǔ)，隨后在課中階段和課后階段可以積極思考和討論相關(guān)知識點(diǎn)的應(yīng)用，這使得學(xué)習(xí)效果得到了大幅度的提升。因此翻轉(zhuǎn)課堂的引入能夠在一定程度上緩解傳統(tǒng)教學(xué)中難以解決的一些問題。

2 翻轉(zhuǎn)課堂教學(xué)模式在算法課程中的應(yīng)用

以高等院校計(jì)算機(jī)專業(yè)權(quán)威教改期刊《計(jì)算機(jī)教育》為例，將翻轉(zhuǎn)課堂、翻轉(zhuǎn)教學(xué)或反轉(zhuǎn)課堂設(shè)置為關(guān)鍵詞，并在CNKI數(shù)據(jù)庫搜索后，得到了相關(guān)文獻(xiàn)數(shù)量統(tǒng)計(jì)結(jié)果：近3年國內(nèi)教師對翻轉(zhuǎn)課堂這一教學(xué)模式愈加關(guān)注，在2013年僅有2篇文獻(xiàn)，而到2015年相關(guān)文獻(xiàn)已經(jīng)大幅度增長到35篇。

通過分析已有文獻(xiàn)，不難看出，翻轉(zhuǎn)課堂模式能夠成功執(zhí)行需要具備2個(gè)因素：①小班授課；②高質(zhì)量的教學(xué)資源。

翻轉(zhuǎn)課堂需要教師與學(xué)生之間積極互動(dòng)，若學(xué)生數(shù)量太多，其互動(dòng)效果很難保證，因此小班授課是成功實(shí)施翻轉(zhuǎn)課堂教學(xué)的前提。目前南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)碩士每年的招生規(guī)模為15人左右，而算法設(shè)計(jì)與分析課程又是研究生課程體系中的必修專業(yè)課程，這為筆者的教學(xué)改革實(shí)踐提供了實(shí)驗(yàn)對象。

高質(zhì)量的教學(xué)資源是成功實(shí)施翻轉(zhuǎn)課堂的關(guān)鍵。隨著慕課（MOOC）的蓬勃發(fā)展，很多優(yōu)質(zhì)教學(xué)資源實(shí)現(xiàn)了共享。在教學(xué)改革實(shí)踐中，筆者充分利用了北京大學(xué)屈婉玲教授在Coursera上開設(shè)的慕課“算法設(shè)計(jì)與分析”，并以屈婉玲教授編寫的教材《算法設(shè)計(jì)與分析》作為上課的指定教材。除此之外，筆者在教學(xué)過程中，如果發(fā)現(xiàn)有更易于學(xué)生接受的講解方式，也會額外錄制一些教學(xué)視頻并用于下一輪的教學(xué)中。

在教學(xué)改革過程中，筆者總結(jié)了圖2所示的基于算法課程的翻轉(zhuǎn)課堂教學(xué)模式框架圖。

為更好地支持翻轉(zhuǎn)課堂教學(xué)，在授課開始的時(shí)候，筆者會在QQ上搭建一個(gè)課程討論群，用以加強(qiáng)教師與學(xué)生之間以及學(xué)生與學(xué)生之間的交流與協(xié)作。通過討論群，可以對學(xué)生的學(xué)習(xí)狀態(tài)、答疑解惑、作業(yè)提交、師生互動(dòng)等情況進(jìn)行跟蹤并提供輔助。

目前南通大學(xué)針對這門課程的教學(xué)安排是13周，每周安排3個(gè)課時(shí)。筆者基于翻轉(zhuǎn)課堂教學(xué)模式對這門課程的具體教學(xué)內(nèi)容進(jìn)行了重新安排，最終如表1所示。由于課時(shí)比較少，因此在算法的基本概念介紹和遞推方程的求解中并不安排翻轉(zhuǎn)課堂。其中在算法的基本概念中，重點(diǎn)介紹計(jì)算復(fù)雜性、時(shí)間復(fù)雜度、常用函數(shù)（對數(shù)函數(shù)、指數(shù)函數(shù)、階乘函數(shù)、取整函數(shù)等）的階及其性質(zhì)。在遞推方程的求解方法中，重點(diǎn)講解差消法、遞歸樹法、迭代法以及主定理等。

在隨后的分治法、動(dòng)態(tài)規(guī)劃法、貪心法和回溯法這4個(gè)單元中，則安排翻轉(zhuǎn)課堂，具體來說：

1）分治法單元。

該單元介紹分治法的設(shè)計(jì)與分析，一般來說該策略首先將原始問題劃分為規(guī)模更小的子問題，隨后遞歸或迭代求解每個(gè)子問題，最后將子問題的解綜合得到原問題的解。

在課前階段，讓學(xué)生借助2個(gè)經(jīng)典問題（二分搜索和歸并排序）來掌握分治法的設(shè)計(jì)與分析過程。

在課中階段，通過依次分析芯片測試、快速排序、選第k小元素等問題來加強(qiáng)學(xué)生對知識點(diǎn)的理解和應(yīng)用。

在分治法單元的最后一周，安排一次團(tuán)隊(duì)答辯。安排2個(gè)團(tuán)隊(duì)分別對提高分治法效率的2種途徑（即減少子問題的數(shù)量和在分治法執(zhí)行之前進(jìn)行必要的預(yù)處理操作），結(jié)合具體問題進(jìn)行講解。

2）動(dòng)態(tài)規(guī)劃法單元。

該單元介紹動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)與分析。動(dòng)態(tài)規(guī)劃法的求解過程是一個(gè)多階段決策過程，每一步處理一個(gè)子問題，可用于求解組合優(yōu)化問題。

在課前階段，讓學(xué)生借助矩陣鏈相乘問題來掌握其中的目標(biāo)函數(shù)設(shè)置、子問題邊界的確定、遞推方程的設(shè)定和最優(yōu)子結(jié)構(gòu)性質(zhì)的證明等。

在課中階段，進(jìn)一步通過最長公共子序列問題、投資問題、最大子段和等問題來加強(qiáng)學(xué)生對知識點(diǎn)的理解和應(yīng)用。

在動(dòng)態(tài)規(guī)劃法單元的最后一周，安排一次團(tuán)隊(duì)答辯。針對2個(gè)具體問題，對基于動(dòng)態(tài)規(guī)劃法的求解方案進(jìn)行講解。

3）貪心法單元。

該單元介紹貪心法的設(shè)計(jì)與分析。貪心法在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。

在課前階段，首先借助活動(dòng)選擇問題，讓學(xué)生了解貪心算法的設(shè)計(jì)過程。隨后借助該問題，進(jìn)一步讓學(xué)生掌握按步驟歸納的證明技巧。最后借助另一個(gè)經(jīng)典問題（裝載問題），讓學(xué)生掌握按規(guī)模歸納的證明技巧。

在課中階段，進(jìn)一步通過最小生成樹的Prime算法和哈夫曼算法來加強(qiáng)學(xué)生對知識點(diǎn)的理解和應(yīng)用。

在貪心法單元的最后一周，安排一次團(tuán)隊(duì)答辯。要求2個(gè)團(tuán)隊(duì)分別講解最小生成樹的另一個(gè)經(jīng)典算法Kruskal算法以及單源最短路徑Dijkstra算法等。

4）回溯法單元。

該單元首先介紹回溯法的設(shè)計(jì)與分析。回溯法是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解約束條件時(shí)，就回溯返回，嘗試別的路徑。隨后介紹分支限界法，該方法通過引入代價(jià)函數(shù)，對傳統(tǒng)的回溯法進(jìn)行了改進(jìn)。

針對回溯法，在課前階段，通過3個(gè)經(jīng)典的問題（n皇后問題、0-1背包問題和旅行商問題），讓學(xué)生掌握搜索空間的3種表示（n叉樹、子集樹和排列樹），并掌握常見的搜索策略（例如深度優(yōu)先、廣度優(yōu)先等）。隨后在課中階段，通過圖的著色等問題來加深學(xué)生對知識點(diǎn)的理解和應(yīng)用。

針對分支限界法，在課前階段，通過背包問題讓學(xué)生了解分支限界法，掌握代價(jià)函數(shù)和界的概念、設(shè)定方法和搜索策略。隨后在課中階段：通過最大團(tuán)問題、旅行商問題、園排列問題等來加深學(xué)生對知識點(diǎn)的理解和應(yīng)用。

由于教學(xué)時(shí)間的限制，在該單元的實(shí)際教學(xué)過程中，并未安排團(tuán)隊(duì)答辯環(huán)節(jié)。

在實(shí)施上述翻轉(zhuǎn)課堂教學(xué)模式的過程中，總結(jié)了如下經(jīng)驗(yàn)：

（1）課前階段的主要目的是讓學(xué)生完成知識的初步學(xué)習(xí)。教師需要針對本周的教學(xué)知識點(diǎn)指定學(xué)生需要預(yù)先學(xué)習(xí)的教材章節(jié)、教學(xué)課件和教學(xué)視頻，同時(shí)為一些學(xué)有余力的學(xué)生指定擴(kuò)展閱讀資料。對于發(fā)布的教學(xué)視頻來說，要求每一段視頻的時(shí)間要控制在10～20分鐘，并且僅僅是圍繞一個(gè)知識點(diǎn)或者一個(gè)具體問題來進(jìn)行講解。

（2）課前階段要求學(xué)生借助自己熟悉的高級編程語言（C++、Java或者C≠≠），對視頻中重點(diǎn)分析的1-2個(gè)經(jīng)典問題進(jìn)行編程實(shí)現(xiàn)，并提交實(shí)驗(yàn)報(bào)告。要求學(xué)生在實(shí)驗(yàn)報(bào)告中記錄下自己在學(xué)習(xí)過程和編碼過程中遇到的問題和解決方法。

（3）課中階段的主要目的是讓學(xué)生完成知識的深化和內(nèi)化。教師首先會針對課前階段布置的預(yù)先學(xué)習(xí)內(nèi)容進(jìn)行串講，重點(diǎn)分析這些算法設(shè)計(jì)與分析背后的核心思想。隨后對學(xué)生提出的疑問進(jìn)行現(xiàn)場解答。最后通過引人新的問題，借助課堂討論方式，來提高學(xué)生對課前階段所學(xué)知識的理解和應(yīng)用。

（4）課后階段則為每一個(gè)單元設(shè)計(jì)一些課程實(shí)踐項(xiàng)目，讓學(xué)生以團(tuán)隊(duì)（每個(gè)團(tuán)隊(duì)的成員限定為2-3人）的方式進(jìn)行完成。筆者在上課剛開始的時(shí)候會要求學(xué)生在2周內(nèi)完成團(tuán)隊(duì)的組建，并預(yù)先選好自己需要完成的實(shí)踐項(xiàng)目。在完成實(shí)踐項(xiàng)目后，需要提交實(shí)踐報(bào)告，內(nèi)容包括問題分析、解決方案的細(xì)節(jié)和性能分析等，并要求編碼實(shí)現(xiàn)，并對其中的核心代碼進(jìn)行說明。除此之外，在每個(gè)單元的最后團(tuán)隊(duì)答辯階段，需要完成現(xiàn)場答辯。在答辯過程中，教師應(yīng)充分發(fā)揮引導(dǎo)者和組織者的作用，避免學(xué)生在學(xué)習(xí)交流過程中出現(xiàn)沖突和討論方向產(chǎn)生偏差；同時(shí)答辯團(tuán)隊(duì)需要在答辯前一天將答辯幻燈片發(fā)送到教師郵箱，讓老師能夠?qū)Υ疝q內(nèi)容預(yù)先有一個(gè)大致的了解。最后對團(tuán)隊(duì)答辯時(shí)間和討論時(shí)間進(jìn)行限制，對一些性質(zhì)的證明建議答辯時(shí)借助板書方式進(jìn)行現(xiàn)場證明，要求每個(gè)團(tuán)隊(duì)必須至少問一個(gè)問題。

（5）對于教師來講，在每一單元完成后，都需要及時(shí)進(jìn)行教學(xué)總結(jié)、優(yōu)化教學(xué)方案和優(yōu)化教學(xué)資源等。例如：基于團(tuán)隊(duì)的答辯表現(xiàn)，將一些特別難或者特別容易的課程實(shí)踐項(xiàng)目從教學(xué)資源庫中移除掉，同時(shí)注重從程序競賽、教材和科研中搜集優(yōu)秀的課程實(shí)踐項(xiàng)目并補(bǔ)充到教學(xué)資源庫中。

（6）翻轉(zhuǎn)課堂可以將考核過程更多貫穿于整個(gè)學(xué)習(xí)階段。其特色是增加了平時(shí)的考核次數(shù)，讓學(xué)生在平時(shí)也能感受到學(xué)習(xí)的壓力，以此提高學(xué)生的學(xué)習(xí)主動(dòng)性，確保翻轉(zhuǎn)課堂能夠取得良好的教學(xué)效果。在該模式中，日常考核的內(nèi)容包括課前階段的實(shí)驗(yàn)報(bào)告、課中階段學(xué)生的課堂表現(xiàn)，以及團(tuán)隊(duì)答辯階段的實(shí)踐報(bào)告和現(xiàn)場答辯表現(xiàn)等。

3 翻轉(zhuǎn)課堂教學(xué)模式實(shí)施效果

為了充分了解上述翻轉(zhuǎn)課堂教學(xué)的實(shí)施效果，筆者在教學(xué)完成后，對2015級專碩的14名學(xué)生進(jìn)行了調(diào)查，結(jié)果表明：

（1）翻轉(zhuǎn)課堂需要學(xué)生投入更多的時(shí)間。為了完成課前階段的算法實(shí)現(xiàn)和團(tuán)隊(duì)答辯階段的實(shí)踐項(xiàng)目，需要學(xué)生查閱大量的資料和花費(fèi)大量的時(shí)間來完成代碼的編寫和調(diào)試。

（2）翻轉(zhuǎn)課堂能夠激發(fā)學(xué)生的學(xué)習(xí)激情。以討論為主的教學(xué)方式，以及新穎有趣的課程實(shí)踐項(xiàng)目，可以極大地激發(fā)學(xué)生的學(xué)習(xí)興趣和熱情。

（3）翻轉(zhuǎn)課堂能夠培養(yǎng)學(xué)生的研究和創(chuàng)新能力。在傳統(tǒng)的填鴨式教學(xué)方式中，學(xué)生僅通過閱讀教材，很難在學(xué)習(xí)的過程中發(fā)現(xiàn)問題，而在翻轉(zhuǎn)課堂教學(xué)中，學(xué)生為了完成課前階段的算法實(shí)現(xiàn)和團(tuán)隊(duì)答辯階段的實(shí)踐項(xiàng)目，必須去上網(wǎng)查找資料，和同學(xué)進(jìn)行討論，這樣就逐漸培養(yǎng)了學(xué)生的研究和創(chuàng)新能力。

（4）翻轉(zhuǎn)課堂可以培養(yǎng)學(xué)生的交流、合作和表達(dá)能力。團(tuán)隊(duì)答辯階段中，為了完成實(shí)踐項(xiàng)目，需要學(xué)生組建團(tuán)隊(duì)、分配職能、協(xié)作完成、提交項(xiàng)目實(shí)踐報(bào)告和答辯幻燈片，并最終完成現(xiàn)場答辯。該階段為學(xué)生提供了一個(gè)很好的機(jī)會和途徑，強(qiáng)化了學(xué)生的參與意識，對于培養(yǎng)學(xué)生的交流、合作和表達(dá)能力起到了積極的作用。

4 結(jié)語

算法設(shè)計(jì)與分析課程是計(jì)算機(jī)專業(yè)體系中的一門重要課程。筆者在之前的教學(xué)改革中，發(fā)現(xiàn)學(xué)生之間水平參差不齊是教學(xué)過程中面臨的最大問題，即學(xué)生之間在基礎(chǔ)知識、智力水平、興趣愛好、學(xué)習(xí)動(dòng)機(jī)和學(xué)習(xí)方法上存在較大的差異，因此提出了一系列教學(xué)改革措施來緩解上述問題，主要包括突出學(xué)習(xí)重要性、優(yōu)化教學(xué)內(nèi)容、引導(dǎo)學(xué)生自主學(xué)習(xí)、建設(shè)算法題庫、成立程序競賽協(xié)會、組織習(xí)題研討課和采用板書為主的教學(xué)手段等。在這次教學(xué)改革中，進(jìn)一步引入翻轉(zhuǎn)課堂教學(xué)模式，可以認(rèn)為是對之前教學(xué)改革的一種縱向拓展，實(shí)踐結(jié)果也證實(shí)了這種新穎的教學(xué)模式可以有效提高學(xué)生的學(xué)習(xí)主動(dòng)性和學(xué)習(xí)興趣。

為進(jìn)一步提高翻轉(zhuǎn)課堂的教學(xué)效果，今后可以從以下幾個(gè)角度去嘗試：①在翻轉(zhuǎn)課堂的實(shí)踐過程中，還可以結(jié)合地方院校學(xué)生的特點(diǎn)，注重自身教學(xué)資源（包括教學(xué)視頻、教學(xué)課件、課程實(shí)踐項(xiàng)目等）的積累和建設(shè)；②可以考慮加強(qiáng)自身網(wǎng)絡(luò)教學(xué)平臺的建設(shè)。雖然存在一些比較成熟的慕課平臺（例如Coursera、學(xué)堂在線、愛課程等），但通過自身網(wǎng)絡(luò)教學(xué)平臺的建設(shè)，可以更加靈活地搜集學(xué)生的學(xué)習(xí)行為數(shù)據(jù)，不僅可以支持翻轉(zhuǎn)課堂教學(xué)模式，還可以為隨后的SPOC（small private online course）模式提供支持。該模式可以根據(jù)學(xué)生入學(xué)基礎(chǔ)的差異以及學(xué)生專業(yè)的差異，對教學(xué)過程進(jìn)行差異化。除此之外，自身網(wǎng)絡(luò)教學(xué)平臺的運(yùn)行也可以為今后的教育大數(shù)據(jù)挖掘研究提供原始的數(shù)據(jù)積累。

（見習(xí)編輯：張勛）