“算法設(shè)計與分析”課程的STT教學模式探討

郭麗清 郭一晶

摘 ?要： 為了提升“算法設(shè)計與分析”課程的教學質(zhì)量，引入STT教學模式進行教學改革。針對教學過程中存在“弱”、“難”、“雜”的問題，提出“獎”、“例”、“享”的課堂互動教學方法。教學實踐證明，該方法能有效激發(fā)學生學習興趣，提升學生課程參與度，提高學生分析問題、解決問題的能力，取得較好的教學效果。

關(guān)鍵詞： 算法; 弱難雜; STT; 獎例享

中圖分類號：G421;TP312 ? ? ? ? ?文獻標識碼：A ? ? 文章編號：1006-8228（2020）06-73-03

Abstract： In order to improve the teaching quality of "Algorithm Design and Analysis" course， this paper introduces the STT teaching mode for teaching reform. To address the problems of "weak"， "difficult" and "miscellaneous" during teaching process， the interactive classroom teaching methods of "award"， "example" and "enjoyment” are proposed. It has been proved by practice that the methods can effectively stimulate students' interest in learning， vigorously enhance students' participation in courses， improve students' ability of analyzing and solving problems， and achieve better teaching results.

Key words： Algorithms; weak; difficult and miscellaneous; STT; award; example and enjoyment

0 引言

眾所周知，程序=數(shù)據(jù)結(jié)構(gòu)+算法。算法的本質(zhì)是一個問題的解決方案。對于同一個問題，通常有多個解決方法。不同的方法，解決問題的效率差異很大。設(shè)計一個高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法[1]。

“算法設(shè)計與分析”是計算機學科的核心課程，主要研究計算機及其相關(guān)領(lǐng)域中的一些常用算法。通過本課程的學習，學生對算法的基本概念、描述方法、設(shè)計過程以及計算機領(lǐng)域解決的問題類型等有一個全盤的了解;掌握蠻力法、分治法、減治法、貪心法、動態(tài)規(guī)劃法、回溯法等算法設(shè)計技術(shù)，進而運用這些方法來解決一些常用的實際問題;同時，學生可學會分析算法、估計算法的時間復雜性和空間復雜性，以便理解并科學評估有關(guān)算法質(zhì)量，從而提高程序設(shè)計的質(zhì)量。該課程對學生將來從事計算機系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件的研究與開發(fā)提供一個廣泛扎實的計算機算法知識基礎(chǔ)。算法設(shè)計與分析是計算機學科公認的最難課程之一，如何激發(fā)學生的學習熱情，加深學生對算法設(shè)計策略的理解，進而提升教學質(zhì)量和教學效果，一直是課程教學過程中的重點。本文從當前教學中存在的問題分析著手，探討STT[2]教學模式在算法設(shè)計與分析課堂教學過程中的實際應(yīng)用，以期給同類課程教師提供一些借鑒與啟發(fā)。

1 當前教學中存在的問題

算法設(shè)計與分析是一門理論性與實踐性兼顧的課程，在學習該課程的過程中需要注意理論與實踐相結(jié)合，對理論性較強的部分，需通過多次練習加以鞏固理解，需要充分地上機練習，結(jié)合應(yīng)用實例在具體計算機環(huán)境中加深對理論知識的理解。

本課程主要采用探究研討法、講練結(jié)合等教學方式。每次講授一種新算法，先介紹算法設(shè)計策略的基本思想，然后從解決計算機中的經(jīng)典問題和生活中的實際問題入手，由簡至繁、層層遞進地講解，通過對設(shè)計策略的反復應(yīng)用，加深學生對算法設(shè)計思想的理解。此外，我們對某些經(jīng)典問題甚至采用不同算法進行解決，對于熟悉的問題，學生可以更快地理解不同算法的核心思想和設(shè)計要點，同時也讓學生更加深刻地體會到一個問題可以有不同的解決方案。即便這些都已考慮，還是由于課程難度、現(xiàn)實學情等一些因素，教學過程依然存在一些問題。

⑴ “弱”——理論學習的畏難心理，積極主動性較弱

算法是一門抽象性的學科，需要大量的理論基礎(chǔ)知識，涉及不少數(shù)學知識和相關(guān)符號。在歷年的教學過程中，了解到學生們普遍反映理論知識枯燥、算法很難學，并在學習過程中產(chǎn)生畏難情緒，影響了他們主動學習算法這門課程的積極主動性，進而影響了課程的教學質(zhì)量和教學效果。

⑵ “難”——基礎(chǔ)水平參差不齊，課程內(nèi)容設(shè)計難度大

算法是計算機相關(guān)專業(yè)學生的必修課程，一般開設(shè)在大二下學期。其先修課程包括程序設(shè)計基礎(chǔ)（如：C、C++、Java之類）、離散數(shù)學、數(shù)據(jù)結(jié)構(gòu)等。先修課程比較多，每個同學掌握程度略有差異，學生的水平參差不齊。

這樣的學情/狀況，給教學過程特別是課堂內(nèi)容設(shè)計帶來較大的難度。關(guān)注基礎(chǔ)薄弱同學，基礎(chǔ)較好接收能力較強的同學無法得到有效提高;拔高課程內(nèi)容，容易導致基礎(chǔ)較弱的同學跟不上，進一步產(chǎn)生厭學情緒，嚴重者甚至放棄該課程。為此，教師需要投入大量的時間，從海量的算法中挑選出合適的實例，構(gòu)建階梯式的學習題庫。

⑶ “雜”——理解現(xiàn)有的算法，但無法應(yīng)用于復雜的實際問題

高等教育重在培養(yǎng)應(yīng)用型人才，學習算法的核心目的是為了讓學生能夠應(yīng)用相關(guān)算法解決實際問題[3]。然而，從實際成效看，大部分學生即使已經(jīng)學習并理解現(xiàn)有的算法，但是在遇到復雜的實際問題時，很難抽象出背后的算法模型。

比如某次上機測試實驗，輸油管道問題[4]，某公司計劃建一條由東向西的主輸油管道。該管道需穿過一個有n口油井的油田。從每口油井都有一條輸油管道沿最短路經(jīng)與主管道相連。若給定n口油井的坐標位置（x，y），主管道位置選擇哪里可以使得各油井到主管道之間的輸油管道長度總和最小的位置？該問題的本質(zhì)是一個對n口油井y坐標的排序問題，進一步解析，問題可以轉(zhuǎn)化為如何快速找到y(tǒng)坐標值的中位數(shù)，該位置即為總輸油管道建立的最優(yōu)選址位置。經(jīng)過分析，我們采用快速排序[5]的原理在線性時間內(nèi)即可實現(xiàn)，具體如圖1所示。但是在有限的考核時間內(nèi)，很多學生沒有很好地完成。

2 STT教學模式探討

TTT和STT起源于英語課堂教學，TTT（Teacher Talking Time）代表教師在教學中講授中所占用的時間，STT（Student Talking Time）代表學生在課堂中發(fā)言中占用的時間。STT教學模式本質(zhì)是一種經(jīng)典的互動教學模式。在教師引導下，師生、同學之間采用對話、研討和交流的方式，形成良好的互動教學氛圍，充分調(diào)用學生的積極主動性，培養(yǎng)學生自學能力，開發(fā)學生的創(chuàng)造思維[6]。傳統(tǒng)的英語課堂以TTT為主，近幾年來不斷增加課堂的STT部分。實踐表明，適當增加教學中的STT，對英語教學質(zhì)量的提高有明顯的促進作用[2]。算法設(shè)計與分析課堂，教師為了構(gòu)建知識理論體系，經(jīng)常采用“灌輸式”教學方法，即典型的TTT為主的教學模式。

我們在教學過程中，嘗試引入STT教學模式，引導學生思考活躍學生思維，激發(fā)學生的學習熱情，發(fā)揮學生積極主動性，進而更好地理解算法設(shè)計的本質(zhì)思想。主要采用以下幾個方法。

⑴ “獎”——建立合適的獎勵機制，提升學生課堂參與度

學習的困難會降低學生的學習熱情，進而影響教學質(zhì)量。課堂激勵可以有效提升學生的學習興趣[8]。在課堂設(shè)計過程中，加大教學過程管控分值，提高學生課堂參與度。比如：對于參與專題分享的同學，平時分加3-5分。外在的激勵一定程度上，提高了學生參與的積極性。激勵理論包括外在激勵和內(nèi)在激勵。內(nèi)在激勵往往具有更穩(wěn)定、持久的驅(qū)動力。內(nèi)在激勵是指學習本身帶來給人的激勵，包括學習的興趣、自信心、成就感等。對于課堂中積極互動的同學，不管怎樣都先給予鼓勵，愿意分享想法是一種勇氣，也是一種進步。良好地課堂氛圍，會促進學生學習的興趣。思考越多，回答到點上的可能性就越大，學生的自信心、成就感也會隨之提高。

⑵ “例”——生活實例入手，激發(fā)學生學習興趣

興趣是最好的老師。在課堂中，適當增加生活的實例，通過解決實際問題，激發(fā)學生的學習興致。每次介紹新算法時，從生活的實例或歷史典故入手，引出算法設(shè)計策略的基本思想。

例如，百錢百雞問題引入蠻力法的設(shè)計的思想，然后逐步引導學生對算法進行優(yōu)化，加深對蠻力法的理解。又例如，學習動態(tài)規(guī)劃算法時，通過貨幣找零問題，溫習貪心算法的核心思想，引導學生思考如何解決不一定時最優(yōu)解問題，導入動態(tài)規(guī)劃的設(shè)計理念。對于涉及較多的數(shù)學符號、公式的經(jīng)典問題，通過對實際例子的講解，降低學生對理論學習的畏難情緒，結(jié)合課堂練習，加深學生對知識的理解和鞏固。如：經(jīng)典的TSP問題[5]，從小蜜蜂采蜜開始講解，衍生到學生畢業(yè)旅行、城市的道路交通規(guī)劃、快遞送貨、互聯(lián)網(wǎng)中的CDN加速等應(yīng)用。

這些嘗試有效地提高了學生的學習興趣，培養(yǎng)了學生分析問題、解決問題的能力。值得注意的是，在課堂中注重提問藝術(shù)，根據(jù)不同學生設(shè)置不同的問題，引導學生思考，讓學生盡可能有的說，愿意說。

⑶ “享”——任務(wù)驅(qū)動專題分享，充分發(fā)揮學生主觀能動性

采用類“翻轉(zhuǎn)課堂”[7]教學模式，結(jié)合課堂上已經(jīng)講過的內(nèi)容，提前2-3周布置相關(guān)主題并提供相關(guān)參考資料。自主組隊報名為主，教師指定為輔參與模式。準備過程中，與學生保持交流互動，引導學生深入思考，學會歸納總結(jié)，分析算法的時間復雜度和空間復雜性以及這類算法生活中適用的場景。排序問題專題分享，加深了學生對一題多解思想的理解，鞏固相關(guān)算法的設(shè)計思想。0-1背包專題分享，提供背包9講相關(guān)資料，專題小組的“小老師們”從0-1背包入手，重點分享了完全背包、多重背包、樹形背包。學生從小偷偷珠寶問題入手，逐層遞進地分析問題，在算法優(yōu)化過程，引入二進制思想，將問題“退化”為0-1背包問題的求解，樹形背包延伸到學生如何實現(xiàn)最優(yōu)總學分選課。這期分享異常精彩，收獲良多。每個人思考問題的思維差異性很大，教師因為已經(jīng)很熟悉，有時忘記當年是怎么理解這個問題。

通過“課堂翻轉(zhuǎn)”，學生分享的模式，更好地了解了學生思考方式，為后續(xù)“以學生為中心”的課堂提供了借鑒。參與分享的學生也表示，通過參與主題分享加深了自己對算法的理解，同時鍛煉了團隊協(xié)作意識。此外，每次同學分享的內(nèi)容，也拓展了本課程的學習題庫。

3 總結(jié)

算法設(shè)計與分析是計算機學科的核心課程。本文深入剖析了該課程存在的一些問題，嘗試引入STT教學模式，進行針對性的教學改革實踐。通過應(yīng)用算法解決生活實際問題、任務(wù)驅(qū)動學生專題分享、建立合適的獎勵機制等方式有效地激發(fā)了學生學習興趣，提升了學生分析問題解決問題的能力。特別是小組式的專題分享，鍛煉了學生的表達能力，增強學生的團隊合作意識。從期末考核結(jié)果看，學生成績也有所提升。在后續(xù)的教學工作中，考慮與學校ACM競賽結(jié)合，以賽促學，培養(yǎng)學生創(chuàng)新實踐能力。

參考文獻（References）：

[1] 孫俊，吳小俊，李岳陽.《計算機算法設(shè)計與分析》教學方法研究[J].科技信息，2013.23：173，217

[2] 張曼，李迎旭，李超.論英語課堂教學中的TTT和STT[J].課程教育研究，2013.10：81

[3] 張銘，耿國華，陳衛(wèi)衛(wèi)，胡學鋼.數(shù)據(jù)結(jié)構(gòu)與算法課程教學實施方案[J].中國大學教學，2011.3：56-60

[4] ?洛谷.P1862輸油管道問題[EB/OL].https：//www.luogu.org/problemnew/show/P1862

[5] 王紅梅，胡明.《算法設(shè)計與分析》（第2版）[M].清華大學出版社，2016.

[6] 孫澤文.課堂互動教學研究[D].華中師范大學，2008.

[7] 何克晶，張星明，鄭運平.算法設(shè)計與分析課程全方位實踐教學改革探索[J].計算機教育，2017.2：45-49

[8] 嚴明貴.課堂激勵是培養(yǎng)學習興趣的推動力[J].教學與管理，2012：121-123