《算法設計與分析》課程教學改革探討

郭良敏

摘要：《算法設計與分析》課程是計算機相關專業(yè)碩士研究生的專業(yè)基礎課程，該文基于該課程的特點和教學中存在的問題，從教學內(nèi)容、教學方法、實踐以及課程考核四方面進行一些討論。

關鍵詞：算法設計與分析；教學內(nèi)容；教學方法；實踐；考核

中圖分類號：G64 文獻標識碼：A 文章編號：1009-3044（2016）35-0120-02

Discussion about Algorithm Design and Analysis Teaching Reform

GUO Liang-min

（School of Mathematics and Computer Science， Anhui Normal University， Wuhu 241000， China）

Abstract： The course of algorithm design and analysis is a basic specialty course for graduated students majored in computer science and related fields. According to the course features and the existing problems in teaching， the teaching content， teaching method， practice and course assessment are discussed in the paper.

Key words： Algorithm design and analysis； Teaching content； Teaching method； Practice； Assessment

《算法設計與分析》課程是計算機相關專業(yè)重要的一門專業(yè)基礎課程，要求學生能通過對本課程的學習，理解主要算法的基本思想，掌握算法的設計方法和分析方法，并能將所學算法應用到實際問題中，從而解決遇到的實際問題。

該課程具有內(nèi)容抽象、知識范圍廣、實踐性強等特點，因此，學生的學習難度大，學習興趣不高。教師在課程內(nèi)容的選擇上與前沿科學研究的聯(lián)系不是很緊密，教學方法和考核方式也相對單一。針對上述問題，本文主要從教學內(nèi)容、方法、實踐和考核四方面展開討論。

1 教學內(nèi)容的整合

教學內(nèi)容除了包含經(jīng)典算法[1]（遞歸、分治法、動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法）的設計理論外，我們還應將隨機算法、近似算法、現(xiàn)代啟發(fā)式算法、并行算法、分布式算法等與前沿聯(lián)系緊密的內(nèi)容融入教學中。教學的重點是經(jīng)典算法的原理，要讓學生理解，并且可以具體實現(xiàn)；難點是如何靈活運用合適的算法去解決遇到的實際問題，即培養(yǎng)學生對所學算法的實際應用能力。

另外，需要將新的相關科研動向融入教學中[2]，尤其是在講解現(xiàn)代啟發(fā)式算法、并行算法、分布式算法等時，增強學生的學習興趣，讓學生感到學有所用，從而提高教學效果，最終達到使學生可以用基本理論去解決實際問題的目標。

具體的教學內(nèi)容安排如下：第一部分是算法概述，包括基本概念、描述算法與算法設計、算法分析的基本原則、復雜性分析；第二部分是分治與遞歸，包括遞歸概念和分治法的思想、二分搜索技術、矩陣的快速乘法、合并排序、快速排序、線性時間選擇、最接近點對問題；第三部分是動態(tài)規(guī)劃，包括矩陣連乘問題、動態(tài)規(guī)劃算法的基本要素、最長公共子序列問題、0-1背包問題、作業(yè)調度問題、圖像壓縮問題；第四部分貪心算法，包括活動安排問題、貪心算法的基本要素、最優(yōu)裝載、哈夫曼編碼、最小生成樹、單源最短路徑；第五部分是回溯法，包括回溯法的算法框架、裝載問題、批處理作業(yè)調度、0-1背包問題、n皇后問題、圖的m著色問題、旅行售貨員問題、圓排列問題；第六部分是分支限界，包括分支限界法的算法框架、單源最短路徑問題、裝載問題、0-1背包問題、批處理作業(yè)調度、旅行售貨員問題；第七部分是隨機算法，包括數(shù)值計算問題的隨機算法、舍伍德算法、拉斯維加斯算法、蒙特卡羅算法；第八部分是近似算法，包括NP完全性理論、頂點覆蓋問題、旅行售貨員問題；第九部分是分布式算法，包括分布式系統(tǒng)、分布式計算模型、分布式算法的設計基礎、遍歷算法、選舉算法、容錯技術；第十部分是現(xiàn)代啟發(fā)式算法，包括啟發(fā)式算法的基本概念、模擬退火算法、遺傳算法、蟻群算法、人工神經(jīng)網(wǎng)絡算法；第十一部分是并行算法，包括并行計算機、并行算法的基本概念、非數(shù)值計算問題的并行算法、數(shù)值計算問題的并行算法。

2 改革教學方法

一是采用以“幻燈片+黑板+計算機”的授課模式，即以電子教案幻燈片、板書和算法的動態(tài)演示作為教學內(nèi)容的展現(xiàn)方式。用幻燈片主要展示靜態(tài)的文字，如定義、基本框架或步驟，板書主要用于分析算法的原理和效率，方便與學生進行交流，算法的動態(tài)演示可以更直觀地展示算法的執(zhí)行過程，從而讓學生更容易地去掌握和理解算法的原理和執(zhí)行步驟。

二是對同一問題，如背包問題、皇后問題、作業(yè)調度問題、資源分配問題等，有不同的算法可以求解。對于這類問題的講解，我們應該以問題為主線，分析和比較不同算法的特點和效率[4]，并讓學生編寫程序實現(xiàn)，理論聯(lián)系實際，通過不同程序的運行結果，從而更容易地理解對同一的問題的不同實現(xiàn)算法。

三是我們主要采用啟發(fā)式的教學方式，即變填鴨式的教學為雙向互動式的教學，采取以探究解決實際應用問題為主的引導式教學，啟發(fā)學生在理解問題的基礎上，進行新的算法思路的探索與討論，引導學生深入思考，培養(yǎng)學生的自我創(chuàng)新能力。

四是對于非經(jīng)典的算法可先通過簡單的、有趣的實例來說明，便于學生了解算法的大致思想，然后再通過閱讀相關科技文獻的方法加深對算法的理解。這樣不僅可以讓學生較容易地掌握相關算法，還可以讓其了解相關領域的研究狀況。

3 強化實踐環(huán)節(jié)

將算法轉換成實際的程序來獲得實際問題的解，這是我們學習算法的最終目的，通過多動手編程，可以讓學生加深對理論知識的理解。考慮到學生水平的參差不齊，特別是動手編程的能力，我們給予實驗內(nèi)容多種不同的選擇方案[3]，不同的選擇方案對應著不同的實現(xiàn)難度，例如，可將實驗內(nèi)容按難易程度分為基礎型、拔高型、挑戰(zhàn)型。對于基礎型的實驗一般較容易，要求學生必須完成，對于拔高型和挑戰(zhàn)型的實驗，學生可以根據(jù)自身的能力進行選做，對于選做的學生，我們可以依據(jù)他們的完成情況在最終的考核成績上予以體現(xiàn)。

4 優(yōu)化考核方式

考核方式應該多樣化，更應該注重評判學生平時課堂上的積極性，作業(yè)的完成效果，學生的創(chuàng)新能力，即注重對學生的過程性考核。利用過程性考核和最終的理論測試考核相結合的方式來綜合評價學生。例如，過程性考核和理論測試考核各占50%，其中，在過程性考核中，平時課堂上的積極性（由到課率、回答問題情況，參與討論情況決定）占50%，作業(yè)的完成效果（由作業(yè)完成的時間質量和內(nèi)容質量，以及拔高型和挑戰(zhàn)型作業(yè)的完成質量決定）占40%，學生的創(chuàng)新能力（由學生參與課題的情況及已獲得的成果，特別是與本課程相關的成果決定）占10%。

5 結束語

本文主要從《算法設計與分析》課程的教學內(nèi)容、教學方法等方面闡述了一些想法。但要更好地提高教學效果，還需教師在教學過程中不斷地進行經(jīng)驗總結，根據(jù)實際情況對內(nèi)容、方法等做出較為及時地調整。

參考文獻：

[1] 王曉東. 計算機算法設計與分析（第3版）[M]. 電子工業(yè)出版社， 2007.

[2] 劉文萍， 陳世紅， 郭小平. 教師領導力在計算機專業(yè)研究生創(chuàng)新能力培養(yǎng)中的應用[J].計算機教育， 2013， 23： 42-45.

[3] 陳寶平. 《算法設計與分析》課程教學的探索與實踐[J]. 現(xiàn)代計算機， 2012： 37-40.

[4] 孫亞紅. 《算法設計與分析》課程教學中計算思維的培養(yǎng)研究[J]. 電腦知識與技術， 2012，8（16）：3910-3911.