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

郭麗清　郭一晶

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

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

中圖分類號(hào)：G421;TP312? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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ì)是一個(gè)問題的解決方案。對(duì)于同一個(gè)問題，通常有多個(gè)解決方法。不同的方法，解決問題的效率差異很大。設(shè)計(jì)一個(gè)高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法[1]。

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

1 當(dāng)前教學(xué)中存在的問題

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

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

⑴ “弱”——理論學(xué)習(xí)的畏難心理，積極主動(dòng)性較弱

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

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

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

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

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

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

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

2 STT教學(xué)模式探討

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

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

⑴ “獎(jiǎng)”——建立合適的獎(jiǎng)勵(lì)機(jī)制，提升學(xué)生課堂參與度

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

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

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

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

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

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

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

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

3 總結(jié)

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

參考文獻(xiàn)（References）：

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

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

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

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

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

[6] 孫澤文.課堂互動(dòng)教學(xué)研究[D].華中師范大學(xué)，2008.

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

[8] 嚴(yán)明貴.課堂激勵(lì)是培養(yǎng)學(xué)習(xí)興趣的推動(dòng)力[J].教學(xué)與管理，2012：121-123