《算法設(shè)計與分析》課程さ奈侍馇動遞進(jìn)啟發(fā)式教學(xué)方法探討

董永生 鄭林濤 劉森 王琳

摘?要：為了使計算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生從本科階段具有良好的算法設(shè)計思維和能力，本文提出了問題驅(qū)動的遞進(jìn)啟發(fā)式教學(xué)方法。本文的撰寫目的不是為了提供高大上的理論上的教學(xué)方法，而是給出一種具體的、可操作的教學(xué)方法，即，本文分別以分治法、動態(tài)規(guī)劃和貪心算法為例，對該問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法進(jìn)行了描述。問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法是通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法啟發(fā)，以提高學(xué)生的算法直觀分析和設(shè)計能力。

關(guān)鍵詞：算法設(shè)計與分析;問題驅(qū)動的遞進(jìn)啟發(fā)式教學(xué);分治法;動態(tài)規(guī)劃;貪心算法

算法設(shè)計與分析是普通高校計算機(jī)科學(xué)與技術(shù)專業(yè)的核心基礎(chǔ)課程，算法設(shè)計與分析課程一直是大多數(shù)本科生比較苦惱的一門專業(yè)課程。圖靈獎得主Donald?E.Knuth曾說：計算機(jī)科學(xué)就是算法研究[1]。事實(shí)上，計算機(jī)科學(xué)每個領(lǐng)域的發(fā)展都要靠有效的算法設(shè)計。作者在教學(xué)過程中一直選用的教材是王曉東教授編著的《計算機(jī)算法設(shè)計與分析》[2]，因此本文的很多描述都是以該教材作為基準(zhǔn)。由于該課程需要較多的數(shù)學(xué)知識，因此有相當(dāng)一部分學(xué)生對該課程有恐懼感，學(xué)習(xí)興趣不高。另外，該課程是計算機(jī)科學(xué)與技術(shù)專業(yè)大學(xué)二年級的必修課，一般選課人數(shù)較多。為了提高學(xué)生們對該課程的學(xué)習(xí)興趣和對課程中主要算法的掌握能力，本文提出了問題驅(qū)動的遞進(jìn)啟發(fā)式教學(xué)方法。

問題驅(qū)動的啟發(fā)式教學(xué)方法已在研究生評估類課程中得到了應(yīng)用[3]。而本文的主要創(chuàng)新是，作者根據(jù)自己多年講授本科生的《算法設(shè)計與分析》課程的教學(xué)經(jīng)驗(yàn)，總結(jié)出了針對本科生《算法設(shè)計與分析》課程的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法。本文的撰寫目的不是為了提供高大上的理論上的教學(xué)方法，而是給出一種具體的、可操作的教學(xué)方法。本文中的方法通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法啟發(fā)，以提高學(xué)生的算法直觀分析和設(shè)計能力。具體地，下面，我們將分別以分治法、動態(tài)規(guī)劃和貪心算法為例，對該問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法進(jìn)行了描述。

1?分治法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法

在講解分治法時，為了給學(xué)生一種直觀的理解，需要通過一些具體化的例子來進(jìn)行講解。例如，可以先設(shè)置一個具體的背景，例如，警察要到一個單位去排查犯罪嫌疑人，已知該犯罪嫌疑人的身高是1.75米，然后讓學(xué)生思考如何才能快速給出排查結(jié)果，也就是說警察如何做才能快速排查完？然后給學(xué)生講解正式的折半查找算法。接下來拋出問題：對于給定的n個元素，如何實(shí)現(xiàn)快速排序？對于這個問題，網(wǎng)上有一個視頻，該視頻是通過跳舞的方式，實(shí)現(xiàn)快速排序。通過這個方式可以啟發(fā)學(xué)生對分治法的興趣。最后再詳細(xì)講解分治法思想和算法步驟。

在講解分治法的算法步驟之后，還要對分治法的算法復(fù)雜度進(jìn)行深入的講解，通常學(xué)生們是記憶教材上給出的通用公式[2]。然而，這種死記硬背的方法，時間長了，卻容易忘記。為了較好地讓學(xué)生掌握分治法的復(fù)雜度，可以采用麻省理工學(xué)院教材上的方法，通過遞歸樹的啟發(fā)式講解，來分析分治法的復(fù)雜度[4]，而且還比較容易得到教材上的算法復(fù)雜度公式?？傊?，分治法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法是通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法復(fù)雜度啟發(fā)，以提高學(xué)生對分治法的算法直觀分析和設(shè)計能力。

2?動態(tài)規(guī)劃的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法

在講解動態(tài)規(guī)劃算法時，為了給學(xué)生一個直觀的理解，我們可以先引入一個日常生活中的例子，例如，當(dāng)我們和朋友坐在酒店聚餐的時候，面對一桌子菜的時候，我們是如何選擇食物進(jìn)餐的？事實(shí)上，我們?nèi)粘＿M(jìn)餐的時候，都是葷素搭配著吃飯，有些對飲食更講究的人，還會考慮如何搭配更有營養(yǎng)。這種選擇就是一種動態(tài)規(guī)劃的思想。然后引入兩個例子，一個是矩陣連乘積問題，另一個是最大字段和問題。在講解矩陣連乘積時，本文建議先分析遞歸關(guān)系，讓學(xué)生思考兩個連乘積的矩陣序列的數(shù)乘次數(shù)和兩個矩陣序列乘積之后得到的矩陣的數(shù)乘次數(shù)之間的關(guān)系，同時讓學(xué)生思考兩個矩陣序列各自的子序列是否也滿足類似的性質(zhì)，從而引出動態(tài)規(guī)劃算法的基本要素之一“最優(yōu)子結(jié)構(gòu)”性質(zhì)。最后，在講解如何通過遞歸關(guān)系計算相應(yīng)的最優(yōu)值（最小數(shù)乘次數(shù)）。在講解最大字段和的時候，本文建議盡量避免直接講解規(guī)范化的數(shù)學(xué)描述，可以通過股民炒股需要計算一年當(dāng)中哪個時間段的收益最高來講解。這樣做，可以讓學(xué)生對最大字段和問題有一種“在身邊”的感覺，從而讓學(xué)生感覺該問題不至于那么深奧。

在給學(xué)生講解動態(tài)規(guī)劃的時候，還要通過分析0-1背包問題，直觀分析和強(qiáng)調(diào)動態(tài)規(guī)劃的重疊子問題性質(zhì)。讓學(xué)生真正對動態(tài)規(guī)劃的最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題性質(zhì)有比較深刻的認(rèn)識?？傊瑒討B(tài)規(guī)劃算法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法是通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法啟發(fā)，以提高學(xué)生對動態(tài)規(guī)劃算法的算法直觀分析和設(shè)計能力。

3?貪心算法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法

在講解貪心算法時，為了給學(xué)生提供一種形象的解釋，需要重點(diǎn)強(qiáng)調(diào)“貪心”。然而，為了避免學(xué)生為了“貪心”而貪心，需要引入一些中性或具有更加積極向上的例子。因此在講解貪心算法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法時，可以從如下兩個層次展開教學(xué)：

（1）問題層次：首先通過“危難時刻”拋出問題：2018年7月19日，遼寧省錦州南火車站一位81歲老人突然倒地不起。候選答案之一是直接撥打120，等待醫(yī)護(hù)人員到來。連一個候選答案是：現(xiàn)在有一位懂醫(yī)學(xué)知識的女大學(xué)生見義勇為，同時撥打120。讓學(xué)生思考如何選擇處理方法更為合理：本實(shí)例可以起到間接鼓勵學(xué)生“見義勇為”的效果。然后給出日常生活中的實(shí)例：其一是通過“餓漢進(jìn)餐”，介紹“貪心選擇”。進(jìn)而通過“收銀員找零”講解收銀員找零中的“貪心選擇”做法。接下來是教材中的活動安排問題，并通過活動安排問題的數(shù)學(xué)模型，以及背包問題的數(shù)學(xué)模型，讓學(xué)生由淺入深從問題層次上對“貪心算法”的適用范圍有所了解。

（2）算法層次：針對上述三個不同層次的問題，開始講解“貪心算法”。首先是從直觀本能角度講解貪心選擇，事實(shí)上，從人性的本能做出的“見義勇為”的行為，屬于貪心算法的貪心選擇策略。因?yàn)樵诶先说沟氐哪且豢?，能夠做出的最?yōu)的選擇是現(xiàn)場有懂醫(yī)術(shù)的乘客，能夠采取一些急救措施，例如掐人中穴或者人工呼吸等，同時撥打急救電話。而不是打急救電話，并干等救護(hù)車的到來，因?yàn)檫@樣可能會錯過一些搶救時機(jī)。接下來，從量化的角度講解收銀員找零問題的貪心算法：假設(shè)有面值為50元、20元、10元、5元，2元，1元的紙幣，需要找給顧客85元現(xiàn)金，為使付出的紙幣的數(shù)量最少，首先選出1張面值不超過85元的最大面值的紙幣，即50元，再選出1張面值不超過35元的最大面值的紙幣，即20元，依次選擇下去，收銀員總共付出4張紙幣。這個例子可以讓學(xué)生從量化的角度來理解收銀員是如何做“貪心”選擇的。最后，從規(guī)范的算法角度對活動安排問題的貪心算法進(jìn)行講解。此時，需要首先建立“活動安排問題”的規(guī)范的數(shù)學(xué)模型中，然后提煉出“貪心算法”，并分析算法的復(fù)雜度。

在講解過活動安排問題的貪心算法之后，需要給學(xué)生強(qiáng)調(diào)：貪心算法在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。進(jìn)一步，盡管貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解?？傊?，貪心算法的問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法是通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法啟發(fā)，以提高學(xué)生的算法直觀分析和設(shè)計能力。

4?小結(jié)

本文針對計算機(jī)科學(xué)與技術(shù)專業(yè)本科生的《算法設(shè)計與分析》課程，提出了問題驅(qū)動的遞進(jìn)啟發(fā)式教學(xué)方法。該教學(xué)方法主要分兩個層次：問題層次和算法層次，并采用遞進(jìn)的方式進(jìn)行教學(xué)，并分別以分治法、動態(tài)規(guī)劃和貪心算法為例，對該問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法進(jìn)行了描述。問題驅(qū)動遞進(jìn)啟發(fā)式教學(xué)方法是通過直觀的問題驅(qū)動，以遞進(jìn)的方式，對學(xué)生進(jìn)行問題啟發(fā)和算法啟發(fā)，以提高學(xué)生的算法直觀分析和設(shè)計能力。

參考文獻(xiàn)：

[1]M.H.Alsuwaiyel，Algorithms?Design?Techniques?and?Analysis.Publishing?House?of?Electronics?Industry，2013.

[2]王曉東.計算機(jī)算法設(shè)計與分析.北京：電子工業(yè)出版社，2018（第5版）.

[3]錢龍霞，王正新，張韌，洪梅，盧揚(yáng).基于問題驅(qū)動的啟發(fā)式教學(xué)方法在研究生評估類課程中的應(yīng)用研究.教育教學(xué)論壇，2016-3（11）：172-173.

[4]Thomas?H.Corman，Charles?E.Leiserson，Ronald?L.Rivest，Clifford?Stein，Introduction?to?Algorithms（3rd?Ed.），The?MIT?Press，2012.

基金資助：河南省高等學(xué)校青年骨干教師培養(yǎng)計劃（項(xiàng)目編號：2017GGJS065）

作者簡介：董永生，男，副教授。