“算法設計與分析”課程教學中若干實踐與思考

石潤華 仲紅

摘要：“算法設計與分析”是計算機專業(yè)的核心課程。該文分別從培養(yǎng)目標、學習興趣、積極思考、教學方式、理論與實驗、科研與教學等多方面探討該課程的教學實踐，并引出若干思考。這對提高這門課程的教學效果與教學質量有著重要意義。

關鍵詞：算法設計；算法分析；教學研究；教學實踐

中圖分類號：G642文獻標識碼：A文章編號：1009-3044(2012)01-0246-03

Several Teaching Practices and Thoughts on Algorithms Design and Analysis

SHI Run-hua, ZHONG Hong

（School of Computer Science and Technology, Anhui University, Hefei 230039, China）

Abstract: Algorithms Design and Analysis is one of core courses in Computer Science and Technology. This paper discussed its several teaching practices from Training Objects, Interest of Study, Active Thoughts, Teaching Method, Theory and Experiment, Scientific Research and Teaching, respectively, and then presented several thoughts. It is significant to improve the teaching effect and quality of Algorithms Design and Analysis for these practices and thoughts.

Key words: algorithm design, algorithm analysis, teaching research, teaching practice

“算法設計與分析”是計算機科學與技術學科中核心課程之一，主要研究一些基本算法的設計策略及算法分析的方法。算法（Algorithm）一詞來自19世紀一位波斯數(shù)學家，它就是計算的步驟和法則，也就是一系列的將輸入轉換為輸出的計算步驟[1]。也可以簡單理解為算法是一序列解決問題的清晰指令，也就是說，能夠對一定規(guī)模的輸入，在有限時間內獲得所要求的輸出。算法作為計算機軟件技術中的重要組成部分，其發(fā)展對提高計算機的使用效率以及拓寬其應用領域起著重要的作用[2]。目前，在一些211或985高校，算法是本科生的必修課程，也是研究生的核心課程。因為它的重要性，以及有著相當?shù)碾y度和深度，通常作為計算機領域博士生入學的必考內容之一。

盡管“算法設計與分析”課程在計算機科學中有著非常重要的地位，但學習起來并不像那些僅僅需要死記硬背的課程，學好算法不僅僅要求能理解人家已有的對具體問題的求解策略（算法），還要能夠能動地利用已學過的算法策略去解析新的問題。理解算法是一回事，運用它去解決問題是另一回事。特別對于一些數(shù)學基礎薄弱，缺少抽象思維能力的學生來說，能理解算法就已經(jīng)很不容易了，更何況要利用它去解決問題、分析問題。這使得他們在學習過程很吃力，很難學好它，從而排斥乃至抵制學習算法。此時，教就顯得很重要，教得好能提高學生的學習興趣，正確指引他們學習的方向，逐步培養(yǎng)他們解決問題、分析問題的能力；教不好可能適得其反，反而使得他們感到枯燥無味。

目前，在教授“算法設計與分析”課程中，存在如下共性問題[3,4]：培養(yǎng)目標單一，教學內容固化，教學方法僵化。結果勢必是：學生學得很吃力，老師教得也很累。筆者及同課題組多位同事，多年從事不同專業(yè)不同層次的與算法相關的教學工作，在教學過程中不斷學習，在學習過程中用心積累，在積累過程中不斷完善。特別地，針對以上存在的具體問題，不斷思考，努力創(chuàng)新，進行了若干實踐，取得了不錯的效果。

1若干實踐與思考

經(jīng)過多年的實踐教學，我們認為以下幾點值得同行們借鑒和思考。

1.1培養(yǎng)目標的多樣化

算法始終貫穿整個計算機的發(fā)展歷程。甚至有學者提出“計算機科學就是算法的研究”。理論上，只要是研究算法的內容都可以作為“算法設計與分析”課程的授課內容，因而該課程所覆蓋的內容非常廣：既有一些基礎算法的設計策略及相應的分析方法，例如分治算法、貪心算法、動態(tài)規(guī)劃算法、回溯法、分支限界法，又有一些特殊算法，例如圖論算法、幾何算法、組合算法、密碼算法、遺傳算法、蟻群算法等。另外針對不同的計算模型，算法研究的內容也不盡相同，例如有并行算法、分布式算法、概率算法、量子算法、云計算乃至普適計算環(huán)境下的算法。正因為算法所涉及的內容很廣，所以不可能在有限的時間內向學生傳授所有的東西，只能根據(jù)具體的培養(yǎng)目標選擇相應的教學內容。

為了克服培養(yǎng)目標單一，以免教學內容固化，我們構建了多級培養(yǎng)目標。首先我們構建了一個總體目標：“通過系統(tǒng)學習，使得學生掌握算法設計與算法分析的常用方法；培養(yǎng)學生由具體到抽象的邏輯思維能力，培養(yǎng)他們計算的思維、計算的習慣”。進而，針對不同的專業(yè)不同的層次，我們制定了相應的分級培養(yǎng)目標。分級培養(yǎng)目標更具體，但都要為總體目標服務。正是因為分級目標的不同，導致了所選用的教材及所授課的內容也不一樣。

對于非本專業(yè)的本科層次，例如信息管理、數(shù)學、電子與信息等專業(yè)，學習該課程的目的主要在于理解和認識，因而其分級培養(yǎng)目標為：“使得學生能夠理解一些基本算法設計的思想，及相應的時空復雜性，幫助他們進一步認識和理解計算機，掌握計算的規(guī)律，初步培養(yǎng)他們計算的思維和習慣，能夠從計算的視角去觀察世界”。也即，側重點是算法設計。我們選用自編教材，總學時36，所涉及的主要內容是一些基礎算法設計的方法，例如分治、貪心、動態(tài)規(guī)劃、回溯、分支限界，以及一些常用的算法，例如查找、排序、選擇、匹配等。

對于本專業(yè)的本科層次，包括計算機科學與技術，軟件工程，網(wǎng)絡工程三個本科專業(yè)，其分級培養(yǎng)目標為：“通過對計算機算法系統(tǒng)的學習，掌握算法設計的主要方法，培養(yǎng)學生分析算法復雜度的初步能力，鍛煉其邏輯思維能力和想象力，并使之了解算法理論的發(fā)展。為獨立設計算法和對算法進行復雜性分析奠定堅實的基礎”。對此，我們的教學側重點是算法設計，兼顧算法分析。我們選用王曉東編著《計算機算法設計與分析》教材。通過大量具體實例，重點學習分治、動態(tài)規(guī)劃、貪心、回溯、分之限界、概率等算法的設計思想、求解步驟、分析方法。此外，我們也適當增加了一些算法復雜性分析的方法的內容。所用學時54+24，增加了24個機時的實驗課，實驗課采用自編講義。

對于本專業(yè)研究生層次，已經(jīng)具備一定的計算機科學與技術素養(yǎng)，而且其中相當一部分學生因本科期間修過算法相關課程，已經(jīng)具備一定的算法設計與分析的能力，但也有少數(shù)學生在本科階段沒有系統(tǒng)接受過算法課程的學習。因而我們的側重點是算法分析，兼顧算法設計，并拓展算法研究內容，要求他們掌握一些常用的算法分析的方法，所選用的教材是中文版《算法導論》（潘金貴譯）。它的主要內容是研究計算機應用中常常遇到的實際問題的解法，研究設計和分析各種算法的基本原理、方法和技術。與本科層次相比，增加了一些算法分析的高級方法，以及針對于一些高級數(shù)據(jù)結構的算法。總學時72。其分級培養(yǎng)目標是：“掌握算法設計與算法分析的常用方法，以便運用這些方法去獨立設計解決各類實際問題的算法；利用已有的算法去解決計算機科學與工程領域中較為復雜的實際問題；對已有的算法進行改進，使之能更快、更有效地解決問題”。

另外，對于本專業(yè)的博士層次，也開設了算法相關的選修課程，例如，智能計算、自然計算、量子計算等課程。在我們的教學體系中，宏觀上有一個粗線條的總體培養(yǎng)目標，具體到不同對象，又有不同的分級培養(yǎng)目標。分級培養(yǎng)目標更具體，形成階梯之勢，都為總體目標服務。

1.2激發(fā)學生的興趣

在我們的教學過程中，始終把激發(fā)學生的學習興趣放在首要位置。但怎樣能激發(fā)大學生的學習興趣呢？實際上，這不僅僅是這門課程需要思考的問題，也是整個大學教育都需要思考的問題[5,6]。顯然，為了激發(fā)大學生的學習熱情，僅僅采用小學、中學時的那種“增強科學的神秘感，展示技術的力量”的方法行不通。那種因為我不知道所以要學的方式很難再驅使大學生。經(jīng)過我們的調查發(fā)現(xiàn)，多數(shù)學生對學習失去興趣，主要原因有二：一是缺少專業(yè)理想（進而缺少學習動力）；二是因不知而不學（即對所學的科目缺乏了解，缺少積累，更不知道學有什么用，從而失去學習興趣）。

因此為了激發(fā)他們的學習興趣，需要引導他們，樹立遠大的專業(yè)理想，繼而對所在學科、所學內容，能從宏觀上把握、認識、了解、喜愛、乃至著迷。在教授專業(yè)知識的同時，我們也很注重以下幾點：

幫助學生樹立遠大的專業(yè)理想。在科學探索上，人類有兩大永恒的主題：一是探索外太空；二是探索生命的奧秘。而計算機科學與技術給這兩大領域的探索帶來了很大的變化，獲得了一些了不起的成就。啟示學生應該多思考“怎樣利用計算機來涉及這兩大主題，怎樣使自己融入其中，乃至做出推動整個人類文明進步的工作，在人類的文明史上留下自己的烙印”。

簡要介紹計算機的發(fā)展歷程，展望未來的計算技術與未來的世界。理解什么是計算，拓展計算的范疇。實際上，計算無處不在。但怎樣用計算機來計算？也即“怎樣抽象模型，形式定義，設計合適的數(shù)據(jù)結構，加上具體的算法策略，最后程序實現(xiàn)，得到想要的結果”，這一過程實質上是一種在計算機中模擬具體物理實在（或系統(tǒng)）的動態(tài)過程，從而更好地探詢這些復雜系統(tǒng)的內在規(guī)律。對于千千萬萬的具體問題，我們應該從哪里著手？怎樣深入分析乃至實施最終的計算？或許“算法設計與分析”中將會有答案。它能指引我們用更好的方法求解具體問題，并且能夠培養(yǎng)我們計算的思維和習慣。

系統(tǒng)概述地介紹“算法設計與分析”的主要內容，以及它在整個計算機科學與技術中的地位。偶爾介紹一些算法在計算機科學中扮演重要角色的例子。例如，密碼破譯中算法與高性能計算機之間的博弈。在授課之初，就應該讓學生明確“算法設計與分析”所覆蓋的主要知識和技能。為什么要學習該門課程？學習該課程后，我們能做些什么？應該怎樣學？”。

1.3引導學生積極思考

在教學過程中，引導學生積極思考，也至關重要，能使學習由被動變主動。經(jīng)過多年實踐教學，我們認為“多提問，提好問”是引導學生積極思考的重要措施。但問的問題不能很隨意，需要經(jīng)過精心設計。為了讓學生積極思考，教師在教學之余需要多設計問題，設計好問題。問題設計得好不好，有沒有吸引力尤為關鍵。筆者每章每節(jié)均會留下一些問題，讓學生思考，當然也有課堂提問，鼓勵學生及時作答。結果最為明顯的效果是“主動與我互動的學生多了，學生間的交流與討論也多了，認真聽課的多了，作業(yè)完成的質量提高了，學習的氛圍讓我更滿意了”。例如，講授分治算法的某些實例時，分的階段多為二分（均分），此時若引入：“能否三分或多分？若多分結果（或復雜性）又如何？”，“用分治算法求解具體實例時，怎樣改進算法所需的時間復雜性？”；在學習自然歸并排序時，筆者經(jīng)常提出“是否存在自然冒泡排序？或在插入排序（或折半插入排序）中，是否可以一次插入多個有序的數(shù)？是否也能改進其時間復雜度”；學完矩陣連乘問題（動態(tài)規(guī)劃算法求解）時，喜歡提出“矩陣連乘的每一種計算方式對應著一種計算成本（也即一個整數(shù)），若有n個矩陣連乘，則至少對應著Ω(2n)個整數(shù)，該問題實質上是要從Ω(2n)個數(shù)中選擇最小數(shù)（對應最佳成本）。那么是否意味著存在比最壞時間為線性還要優(yōu)的選擇算法？”；“在概率算法中，學習計算π值的隨機算法后，能否設計計算線段長度（等于 2或其它無理數(shù)）的隨機算法？”。

另外，給學生推薦一些好的課外讀物也有積極的作用。我們推薦的課外讀物不僅是一些教輔讀物，還有一些有關計算機、算法乃至其它自然科學的人物傳記、科學史話、科幻預言等。例如《宇宙、量子和人腦》、《宇宙的起源》、《揭開生命的奧秘》等書或視頻。

總之，課堂教學固然很重要，但課堂之外的工作也非常重要，其中多設計問題，設計好問題很關鍵。它能引導學生積極思考，變被動學習為主動學習。

1.4教學方式多樣化

在傳統(tǒng)教學中，那種填鴨式的教學方式，只會使學習“算法”相關的課程變得枯燥，學生只能被動接受，缺少主動思考，更談不上所謂的創(chuàng)新能力的培養(yǎng)。教的根本是學，因而教學方式要能適應學生的需要。所學的內容日新月異，所采用的教學方式當然也要與時俱進。

在我們的教學過程中，鼓勵教學方式的多樣化：以多媒體和板書為主，結合其它教學方式。多媒體課件的開發(fā)應用，極大地豐富了教學手段。但開發(fā)、設計出具有個性化的課件需要花費教師大量的課外時間。尤其是動與靜的結合，具體與抽象的變換，需要精心設計。另外，多媒體教學也有局限性，很難滿足“內容的有限與思想的無限”之間的矛盾。而教是一個動態(tài)的過程。為了體現(xiàn)及時性，必要的板書尤為重要。實際上，板書更自由，跨度廣，前后關聯(lián)更緊密。此外，啟發(fā)式教、自主式學、分組討論等其它教學形式也是必要的補充。

1.5理論與實驗相輔相成

在“算法設計與分析”課程的理論教學的同時，我們也很重視相應的實驗教學。理論與實驗相輔相成，相得益彰。實驗能對理論加以驗證，進而能加深對理論的理解，反過來，理論又能指導實驗。

針對不同的專業(yè)不同的層次，我們設計了不同的實驗內容，分別以實驗課和課外作業(yè)的形式開展。在所有實驗教學及作業(yè)中，我們設計了四類實驗：驗證類、基礎類、綜合類、設計類。前三類均由老師給定相應的實驗內容，后一類實驗內容由學生獨立設計、開展、實施、驗證。整個實驗進程由淺及深，內容覆蓋面廣，涉及算法設計、算法實現(xiàn)、算法改進等內容。整個實驗（特別是后一類實驗）的開展，取得了不錯的成效。加深了學生對理論知識的把握和更深層次的感悟。使學生在學習過程中更能發(fā)揮主動性、能動性。主導自己的學習目的，修正自己的學習行為，更新自己的學習內容乃至學習方式。

1.6科研與教學并重

教學不能游離于科研之外，教學與科研并重，相互促進，有益補充。良好的科研會使老師對某一專業(yè)研究有較深的理解，能更好地把所學知識融入其中（也即學有何用），從而對教的內容、方式、方法有更深的理解、更好的感悟。例如，筆者在教學的同時，堅持科研工作。研究方向為信息安全，重點研究密碼算法，這為我的教學工作提供了很多素材，特別是使我對算法有著更深層次的理解。能夠適時地把所研究的密碼算法乃至信息領域最新的理論和實驗成果介紹給學生，讓他們明白學以致用的地方，激發(fā)他們學習專業(yè)知識的興趣，培養(yǎng)崇尚科學的品質。

有了自己的科研方向及積累，結合學生已掌握的知識結構，就可以指導學生完成一些創(chuàng)新項目或參加一些全國或國際上的競賽。例如，全國信息安全大賽、國際ACM大賽。這勢必又能提高學生的學習興趣，進而幫助自己的教學工作更全面的開展。

另外，老師在科研上的出色工作，必定幫助他在學生中樹立更高的威信。反過來，老師的威信一定程度上能夠促使學生認真學習。

2結束語

“算法設計與分析”是一門理論性與實踐性兼顧的課程，是計算機科學技術中面向設計、處于核心地位的教育課程。筆者多年從事本科、研究生“算法設計與分析”課程的教學工作，在培養(yǎng)目標、學習興趣、積極思考、教學方式、理論與實驗、科研與教學等多方面，進行了有益的嘗試，取得了一些積極的成效。今后還希望在網(wǎng)站資源、考核方式、培養(yǎng)興趣小組等方面繼續(xù)嘗試和探討。

參考文獻:

[1]盧開澄,譚明術.計算機算法設計與分析[M].北京,中國鐵道出版社,1998.

[2]劉波.“算法設計與分析”教學探討[J].高等理科教育,2007(4):78-80.

[3]戴群.“算法設計與分析”本科課程教學研究[J].計算機教育,2009(18):70-72.

[4]張銘,耿國華,陳衛(wèi)衛(wèi),胡學鋼.數(shù)據(jù)結構與算法課程教學實施方案[J].中國大學教學,2011(3):56-60.

[5]魏青.《C語言》教學中學生學習興趣的培養(yǎng)[J].電腦知識與技術,2010,6(21):5806-5807.

[6]杜丙新,秦國防.基于興趣驅動的數(shù)據(jù)結構課程教學探索[J].電腦知識與技術,2011,7(21):5171-5172, 5174.