《算法設計與分析》課程さ奈侍馇動遞進啟發式教學方法探討

董永生 鄭林濤 劉森 王琳

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

關鍵詞：算法設計與分析;問題驅動的遞進啟發式教學;分治法;動態規劃;貪心算法

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

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

1?分治法的問題驅動遞進啟發式教學方法

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

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

2?動態規劃的問題驅動遞進啟發式教學方法

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

在給學生講解動態規劃的時候，還要通過分析0-1背包問題，直觀分析和強調動態規劃的重疊子問題性質。讓學生真正對動態規劃的最優子結構性質和重疊子問題性質有比較深刻的認識?？傊瑒討B規劃算法的問題驅動遞進啟發式教學方法是通過直觀的問題驅動，以遞進的方式，對學生進行問題啟發和算法啟發，以提高學生對動態規劃算法的算法直觀分析和設計能力。

3?貪心算法的問題驅動遞進啟發式教學方法

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

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

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

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

4?小結

本文針對計算機科學與技術專業本科生的《算法設計與分析》課程，提出了問題驅動的遞進啟發式教學方法。該教學方法主要分兩個層次：問題層次和算法層次，并采用遞進的方式進行教學，并分別以分治法、動態規劃和貪心算法為例，對該問題驅動遞進啟發式教學方法進行了描述。問題驅動遞進啟發式教學方法是通過直觀的問題驅動，以遞進的方式，對學生進行問題啟發和算法啟發，以提高學生的算法直觀分析和設計能力。

參考文獻：

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

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

[3]錢龍霞，王正新，張韌，洪梅，盧揚.基于問題驅動的啟發式教學方法在研究生評估類課程中的應用研究.教育教學論壇，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.

基金資助：河南省高等學校青年骨干教師培養計劃（項目編號：2017GGJS065）

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