岳珂娟，洪 偉

（湖南第一師范學(xué)院 信息科學(xué)與工程學(xué)院，湖南 長沙 410205）

翻轉(zhuǎn)課堂在最小生成樹問題教學(xué)中的實(shí)踐

岳珂娟，洪 偉

（湖南第一師范學(xué)院 信息科學(xué)與工程學(xué)院，湖南 長沙 410205）

最小生成樹問題是算法分析與設(shè)計課程中的一個重要內(nèi)容。由于其內(nèi)容本身比較難，加上傳統(tǒng)的教師“講”，學(xué)生“聽”為主的教學(xué)方式，使得學(xué)生學(xué)習(xí)的主動性比較差，也很難達(dá)到預(yù)期的教學(xué)效果。通過探索翻轉(zhuǎn)課堂在最小生成樹問題教學(xué)實(shí)踐中的應(yīng)用，基于翻轉(zhuǎn)課堂的教學(xué)模式對教學(xué)內(nèi)容進(jìn)行重新設(shè)計和組織的教學(xué)改革效果表明，這種教學(xué)模式非常適合最小生成樹問題的教學(xué)。

翻轉(zhuǎn)課堂；最小生成樹；自主學(xué)習(xí)

引言

最小生成樹問題是貪心算法的一個經(jīng)典例題，也是算法分析與設(shè)計這門課程中的一個重要的教學(xué)內(nèi)容。傳統(tǒng)的教學(xué)方法以教師“講”，學(xué)生“聽”為主，并通過上機(jī)實(shí)驗(yàn)和課后答疑來幫助學(xué)生加深對這個問題的理解。這樣的教學(xué)方式不能調(diào)動學(xué)生學(xué)習(xí)的主動性，也很難達(dá)到預(yù)期的教學(xué)效果[1]。

我們將“翻轉(zhuǎn)課堂”這種新的教學(xué)模式應(yīng)用于最小生成樹問題的教學(xué)實(shí)踐，解決傳統(tǒng)教學(xué)中面臨的困難，在翻轉(zhuǎn)課堂的框架內(nèi)對教學(xué)內(nèi)容進(jìn)行重新設(shè)計，教學(xué)效果表明這種教學(xué)模式非常適合最小生成樹問題的教學(xué)。

一、最小生成樹問題教學(xué)中面臨的困難

最小生成樹問題的教學(xué)過程主要包含了以下個步驟：最小生成樹問題的描述；最小生成樹性質(zhì)的證明；Prime算法和Kruskal算法的描述；Prime算法和Kruskal算法的實(shí)現(xiàn)，程序的編寫。這樣的教學(xué)效果往往很難達(dá)到教學(xué)的預(yù)期目標(biāo)，主要原因包括以下幾個：

（1）缺少課前預(yù)習(xí)的環(huán)節(jié)，學(xué)生僅靠課堂有限的幾十分鐘時間要吸收大量的新知識比較困難。即便教師下達(dá)了課前預(yù)習(xí)的指令，由于沒有布置具體的預(yù)習(xí)任務(wù)，學(xué)生只是盲目地翻看一下教材，對知識點(diǎn)的理解仍然非常淺顯。

（2）最小生成樹算法本身比較難，僅依靠教材內(nèi)容的學(xué)習(xí)難以還原算法的邏輯細(xì)節(jié)，所以大部分學(xué)生對算法的理解停留在死記硬背的階段，知其然而不知其所以然。

（3）部分學(xué)校在開設(shè)算法分析與設(shè)計這門課程之前，已經(jīng)開設(shè)了數(shù)據(jù)結(jié)構(gòu)這門課程，從圖論的角度講解了最小生成樹問題。在算法分析與設(shè)計這門課程中則要求學(xué)生從貪心法的角度理解這個問題，并且要分析算法的時間復(fù)雜度，學(xué)習(xí)的側(cè)重點(diǎn)和學(xué)習(xí)目標(biāo)有所不同，教學(xué)設(shè)計上也要有區(qū)別。

（4）傳統(tǒng)的教學(xué)方式通常都是先講解最小生成樹算法的基本理論，然后講解算法的實(shí)現(xiàn)，課堂教學(xué)后馬上要求學(xué)生獨(dú)立完成相應(yīng)的算法實(shí)現(xiàn)代碼[2]。學(xué)生和學(xué)生之間，缺乏互相討論和學(xué)習(xí)的環(huán)節(jié)，導(dǎo)致實(shí)驗(yàn)課的效果并不好，部分同學(xué)會無法完成實(shí)驗(yàn)課的教學(xué)目標(biāo)。

（5）以教師傳授知識為主的傳統(tǒng)教學(xué)方法，難以激發(fā)學(xué)生的自主學(xué)習(xí)性[3]，不利于知識面的拓展。學(xué)生學(xué)習(xí)完最小生成樹算法之后，可能對Prime算法和Kruskal算法掌握得比較好，但是對于算法的發(fā)展和歷史，以及求解最小生成樹的其他方法一無所知，不利于學(xué)習(xí)興趣的培養(yǎng)。

二、翻轉(zhuǎn)課堂的教學(xué)模式

翻轉(zhuǎn)課堂是指重新調(diào)整課堂內(nèi)外的學(xué)習(xí)模式，將學(xué)習(xí)的決定權(quán)從教師轉(zhuǎn)移給學(xué)生[4]。在這種教學(xué)模式下，教師的角色從“教”轉(zhuǎn)變?yōu)椤皩?dǎo)”和“答”，學(xué)生的角色從“聽”轉(zhuǎn)變?yōu)椤皢枴盵5]。即學(xué)生在課前自主完成知識的學(xué)習(xí)，課堂則變成教師與學(xué)生之間，以及學(xué)生與學(xué)生之間互動的場所，包括答疑解惑、知識的運(yùn)用等，從而達(dá)到更好的教學(xué)效果。

隨著高校信息化建設(shè)的發(fā)展，大多數(shù)學(xué)校已經(jīng)具備在線學(xué)習(xí)的平臺，可以提供翻轉(zhuǎn)課堂所需要的軟硬件環(huán)境。同時網(wǎng)絡(luò)的發(fā)展，尤其是學(xué)校圖書館科技文獻(xiàn)資料的信息化建設(shè)，也為學(xué)生查閱資料和自主學(xué)習(xí)提供良好的技術(shù)支撐。通過以上對最小生成樹問題教學(xué)中存在的問題，以及翻轉(zhuǎn)課堂教學(xué)模式的分析，我們嘗試?yán)梅D(zhuǎn)課堂的教學(xué)模式對最小生成樹問題的教學(xué)過程進(jìn)行重新設(shè)計，調(diào)動學(xué)生自主學(xué)習(xí)的積極性，探索以學(xué)生“問”為主的課堂教學(xué)方式。

三、翻轉(zhuǎn)課堂的建設(shè)

（一）教學(xué)模式的總體設(shè)計

翻轉(zhuǎn)課堂構(gòu)建包括兩個角色和三個階段。兩個角色分別是教師和學(xué)生，三個階段分別是課前、課中和課后[6]。在課前，教師根據(jù)教學(xué)任務(wù)和教學(xué)目標(biāo)，對教學(xué)內(nèi)容進(jìn)行知識點(diǎn)劃分和歸納，以知識點(diǎn)為單元，制作教學(xué)視頻或PPT，搜集相關(guān)的學(xué)習(xí)資源（包括數(shù)字圖書、網(wǎng)絡(luò)課程視頻或?qū)W習(xí)資料），布置課前學(xué)習(xí)的任務(wù)。這些資源通過網(wǎng)絡(luò)上傳到校園學(xué)習(xí)平臺，學(xué)生通過學(xué)習(xí)平臺觀看教學(xué)視頻，完成相應(yīng)的學(xué)習(xí)任務(wù)并反饋給教師。教學(xué)視頻的主要目的是讓學(xué)生自學(xué)課程內(nèi)容的主要知識點(diǎn)，考慮到學(xué)生的自學(xué)能力有限，視頻的內(nèi)容要重點(diǎn)突出，講解要簡單清晰，每一段視頻的時間一般不超過15分鐘。課堂中，教師針對教學(xué)內(nèi)容進(jìn)行主題講解，并針對學(xué)生的提問開展課堂討論，最后通過提問引導(dǎo)學(xué)生進(jìn)行擴(kuò)展知識點(diǎn)的學(xué)習(xí)。課后，教師進(jìn)行教學(xué)內(nèi)容的總結(jié)分析、作業(yè)布置、在線答疑和成績評定，學(xué)生完成課后作業(yè)，并通過實(shí)踐練習(xí)鞏固學(xué)習(xí)內(nèi)容。具體的教學(xué)模式如圖1所示。

圖1 翻轉(zhuǎn)課堂教學(xué)模式的總體設(shè)計

（二）基于翻轉(zhuǎn)課堂的最小生成樹問題的教學(xué)設(shè)計

將翻轉(zhuǎn)課堂的教學(xué)模式應(yīng)用在最小生成樹問題的教學(xué)中，需要對課前、課中和課后的教學(xué)內(nèi)容和教學(xué)形式進(jìn)行更加詳細(xì)的設(shè)計，包括知識點(diǎn)的歸納，學(xué)習(xí)任務(wù)的設(shè)置、課堂講解內(nèi)容的準(zhǔn)備、課堂討論的主題，實(shí)驗(yàn)教學(xué)的安排，以及考核評價的標(biāo)準(zhǔn)。同時，每一個環(huán)節(jié)，我們都為學(xué)有余力的學(xué)生提供了相應(yīng)的學(xué)習(xí)資料并給予引導(dǎo)，以滿足不同層次學(xué)生的學(xué)習(xí)要求。

1.課前組織

課前學(xué)習(xí)的主要目的是讓學(xué)生能夠快速進(jìn)入教學(xué)內(nèi)容的主題，并抓住學(xué)習(xí)的重點(diǎn)，理解最小生成樹問題中主要的知識點(diǎn)。因此，我們在錄制的教學(xué)視頻中只體現(xiàn)三個內(nèi)容，即算法的應(yīng)用背景和問題的提出，Prim算法的描述和實(shí)現(xiàn)，Kruskal算法的描述和實(shí)現(xiàn)。布置的學(xué)習(xí)任務(wù)包括復(fù)習(xí)最小生成樹相關(guān)的概念，掌握Prim算法和Kruskal算法的工作原理（包括圖示、算法描述和代碼實(shí)現(xiàn)）。為了掌握學(xué)習(xí)任務(wù)的完成情況，我們設(shè)置了選擇題和判斷題來檢查和最小生成樹有關(guān)的圖論中的基本概念的學(xué)習(xí)情況，設(shè)置了問答題來檢查學(xué)生對Prim算法和Kruskal算法的掌握情況。同時，我們提供包含全部知識點(diǎn)的PPT，幫助學(xué)生提前預(yù)習(xí)課堂上教師需要講解的內(nèi)容。除此以外，我們還為學(xué)習(xí)能力比較強(qiáng)的學(xué)生提供了經(jīng)典的網(wǎng)絡(luò)課程的視頻或網(wǎng)站鏈接，包括清華大學(xué)嚴(yán)蔚敏老師的數(shù)據(jù)結(jié)構(gòu)課程，北京大學(xué)張銘老師的數(shù)據(jù)結(jié)構(gòu)與算法分析課程，麻省理工學(xué)院算法導(dǎo)論公開課。

2.課堂講解

學(xué)生通過課前的學(xué)習(xí)一般能掌握50%～60%的教學(xué)內(nèi)容，剩余的內(nèi)容則需要教師利用課堂的教學(xué)時間進(jìn)行重點(diǎn)講解，讓學(xué)生對貪心法求解最小生成樹問題有一個全面和完整的理解。主題講解包括如下幾個內(nèi)容：貪心法的基本概念，手工求最小生成樹的例題（后面的定理證明會多次使用這個例題），證明最小生成樹問題的最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)。其中最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)的證明是重點(diǎn)也是難點(diǎn)，對大部分學(xué)生來說，這兩個性質(zhì)的證明很難通過課前的學(xué)習(xí)自己掌握。教師的講解，可以讓學(xué)生充分的理解為什么最小生成樹問題可以采用貪心法求得最優(yōu)解。接下來是學(xué)習(xí)算法的描述和實(shí)現(xiàn)，由于算法的基本原理和實(shí)現(xiàn)方法已經(jīng)在課前學(xué)習(xí)中完成，根據(jù)課前學(xué)習(xí)的反饋結(jié)果，這部分內(nèi)容的學(xué)習(xí)可以采取教師講解學(xué)生提問，或?qū)W生講解教師提問的方式進(jìn)行，對學(xué)習(xí)內(nèi)容進(jìn)行充分的討論。在課堂教學(xué)的最后，我們以提問的方式引導(dǎo)學(xué)生進(jìn)行知識的擴(kuò)展學(xué)習(xí)，例如：是否可以用動態(tài)規(guī)劃化法求解最小生成樹問題、最小生成樹是否唯一、最小生成樹算法的歷史、其他求最小生成樹的方法。

3.課后總結(jié)

課后總結(jié)是課堂教學(xué)完成之后非常重要的一個環(huán)節(jié)，這個階段教師可以結(jié)合最小生成樹問題的教學(xué)要點(diǎn)和前期的教學(xué)反饋對學(xué)習(xí)內(nèi)容進(jìn)行一個提綱式的總結(jié)，并在總結(jié)的基礎(chǔ)上引導(dǎo)學(xué)生對知識點(diǎn)做更高層次的提煉。比如：為什么可以用貪心法求解最小生成樹問題，對照最小生成樹問題的求解過程，描述貪心法的解題步驟。學(xué)生通過對這些問題的思考，可以進(jìn)一步加深對貪心法求解最小生成樹問題的理解。

4.作業(yè)布置

根據(jù)翻轉(zhuǎn)課堂的教學(xué)模式和算法設(shè)計課的教學(xué)特點(diǎn)，學(xué)生的作業(yè)主要以兩種形式體現(xiàn)。一種是在課前的自主學(xué)習(xí)中，以書面答題的方式完成；一種是在課后學(xué)習(xí)中以實(shí)踐上機(jī)并撰寫實(shí)驗(yàn)報告的方式體現(xiàn)。考慮到個別學(xué)生編程能力較差，無法獨(dú)立完成整個算法的代碼編寫，我們在這次的實(shí)踐教學(xué)中鼓勵學(xué)生以小組為單位進(jìn)行程序的編寫。小組成員可以分工合作，并在編寫代碼的過程中進(jìn)行討論，共同完成上機(jī)實(shí)踐的任務(wù)。小組的實(shí)驗(yàn)報告要體現(xiàn)每個學(xué)生在實(shí)驗(yàn)中承擔(dān)的具體工作，并記錄討論的內(nèi)容。

5.成績考核

整個學(xué)習(xí)過程的考核由課前的任務(wù)完成情況（占30%）、課堂討論情況（占20%）、課后作業(yè)的完成（占20%），以及實(shí)驗(yàn)的完成情況（占30%）四部分組成。其中實(shí)驗(yàn)的完成情況包括實(shí)驗(yàn)中參與的具體工作和完成質(zhì)量，以及實(shí)驗(yàn)報告的質(zhì)量。

四、教學(xué)效果分析

將翻轉(zhuǎn)課堂的教學(xué)模式應(yīng)用在最小生成樹問題的教學(xué)中，教學(xué)效果最明顯的變化就是學(xué)生由被動地接受知識轉(zhuǎn)變?yōu)橹鲃拥貙W(xué)習(xí)知識。通過教師提供的教學(xué)視頻、PPT、網(wǎng)絡(luò)學(xué)習(xí)資源，學(xué)生在老師的指導(dǎo)下自主學(xué)習(xí)最小生成樹問題的主要知識點(diǎn)。大部分學(xué)生可以很好地完成老師布置的課前學(xué)習(xí)任務(wù)，當(dāng)老師在課堂上進(jìn)行主題內(nèi)容的講解時，學(xué)生對新知識點(diǎn)的學(xué)習(xí)效率有了明顯的提高。例如，以往的教學(xué)安排是先講解完貪心法求解最小生成樹問題的理論，然后講解算法的代碼實(shí)現(xiàn)，學(xué)生對前一個知識點(diǎn)還沒有完全吸收，就要理解代碼的編寫方法就很困難。而采取了翻轉(zhuǎn)課堂的教學(xué)模式之后，學(xué)生已經(jīng)在課前學(xué)習(xí)中理解了算法的基本思想，并學(xué)習(xí)了代碼實(shí)現(xiàn)的方法，課堂上通過老師的講解以及同學(xué)之間的討論可以快速地掌握這部分的學(xué)習(xí)內(nèi)容。由于課前布置的任務(wù)已經(jīng)要求學(xué)生掌握Prim算法和Kruskal算法的工作原理，教師在課堂內(nèi)的講解將重點(diǎn)放在了貪心選擇性質(zhì)的證明上，這樣避免了和數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容上的重復(fù)，讓學(xué)生重新從算法的角度理解來最小生成樹問題。

實(shí)驗(yàn)部分的教學(xué)由獨(dú)立完成轉(zhuǎn)變?yōu)榭梢孕〗M合作完成，使得編程基礎(chǔ)差的學(xué)生克服了畏難情緒。這部分學(xué)生和小組其他成員合作，不但可以較好地完成自己承擔(dān)的那部分工作內(nèi)容，還通過小組討論掌握了整個算法的實(shí)現(xiàn)方法。

同時，我們在課前、課中和課后的每一個環(huán)節(jié)，都為學(xué)生提供了可以進(jìn)行知識擴(kuò)展的的學(xué)習(xí)資料和指導(dǎo)。學(xué)習(xí)能力較強(qiáng)的學(xué)生對這部分內(nèi)容非常感興趣，課后也和教師進(jìn)行了討論，對最小生成樹問題的理解也更加深刻。

結(jié)語

本文對算法分析與設(shè)計這門課程中的最小生成樹問題教學(xué)中面臨的困難進(jìn)行了詳細(xì)的分析，將翻轉(zhuǎn)課堂的教學(xué)模式應(yīng)用在最小生成樹問題的教學(xué)中。我們分課前、課中和課后三個階段，對理論教學(xué)和實(shí)驗(yàn)教學(xué)進(jìn)行了重新設(shè)計，在實(shí)際教學(xué)中取得了較好的教學(xué)效果。這種教學(xué)模式也可以推廣到其他算法的教學(xué)中，為算法分析與設(shè)計這門課程的教學(xué)改革實(shí)踐提供了一個非常有價值的參考依據(jù)。

參考文獻(xiàn)：

[1]封富君,李新社,姚俊萍.算法設(shè)計與分析課程教學(xué)方法探討[J].大學(xué)教育,2014(18):149-150.

[2]馮月華.《數(shù)據(jù)結(jié)構(gòu)》課程改革下的一堂教學(xué)實(shí)例——最小生成樹[J].隴東學(xué)院學(xué)報,2014(3):111-115.

[3]陳翔.面向不同層次學(xué)生的算法設(shè)計與分析課程教學(xué)改革探索[J].計算機(jī)教育,2014(18):19-22.

[4]吳一塵,張亮,趙文進(jìn).翻轉(zhuǎn)課堂在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用[J].計算機(jī)教育,2016(2):55-57.

[5]趙興龍.翻轉(zhuǎn)課堂中知識內(nèi)化過程及教學(xué)模式設(shè)計[J].現(xiàn)代遠(yuǎn)程教育研究,2014(2):55-61.

[6]丁智國.翻轉(zhuǎn)課堂在軟件體系結(jié)構(gòu)課程教學(xué)中的實(shí)踐[J].計算機(jī)教育,2017(3):68-71.

Practice of Flipped Classroom in the Teaching of Minimum Spanning Tree Problem

YUE Ke-juan,HONG Wei

(School ofInformation Science and Engineering,Hunan First Normal University,Changsha,Hunan 410205)

The minimum spanning tree problem is one of the important contents of algorithm analysis and design. The content is difficult,and the traditional teaching method focuses on“teaching and listening”,which cannot arouse the student’s learning initiative,so it is difficult to achieve the desired teaching effect.This paper explores the application of flipped classroom in the teaching practice of minimum spanning tree problem.Based on the flipped classroom,we redesign and organize the teaching contents,and the teaching effect shows that this teaching method is very suitable for the minimum spanning tree problem.

flipped classroom;minimum spanning tree;autonomous learning

G642

A

1674-831X（2017）03-0076-04

[責(zé)任編輯：胡 偉]

2017-02-24

湖南省哲學(xué)社會科學(xué)基金項目（16YBA094）；湖南省教育廳科學(xué)研究項目（15C0282）

岳珂娟（1977-），女，湖南邵陽人，湖南第一師范學(xué)院講師，博士研究生，主要從事算法分析與設(shè)計研究；洪偉（1976-），女，湖南岳陽人，湖南第一師范學(xué)院講師，主要從事算法分析與設(shè)計研究。