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

岳珂娟，洪 偉

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

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

岳珂娟，洪 偉

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

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

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

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.課前組織

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

2.課堂講解

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

3.課后總結(jié)

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

4.作業(yè)布置

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

5.成績考核

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

四、教學效果分析

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

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

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

結(jié)語

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

參考文獻：

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

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

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

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

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

[6]丁智國.翻轉(zhuǎn)課堂在軟件體系結(jié)構(gòu)課程教學中的實踐[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

[責任編輯：胡 偉]

2017-02-24

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

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