戴 群

摘要:“算法設計與分析”不僅是計算機科學與技術(shù)學科的核心課程之一,也被很多高校的電子信息及數(shù)學等專業(yè)列為專業(yè)必修課程。本文從教材選擇、興趣培養(yǎng)、理論教學、科研方法及實踐能力培養(yǎng)等方面探討有效教學的方法,旨在提高教學質(zhì)量。

關(guān)鍵詞:算法設計與分析;教學研究;教學質(zhì)量

中圖分類號:G642 文獻標識碼:B

1引言

“算法設計與分析”是計算機科學與技術(shù)學科的核心課程之一,受到越來越多的重視。對于一個計算機專業(yè)的學生,學好算法課是必要且是必須的?！八惴ㄔO計與分析”這門課程的主要目的不僅是講授計算領(lǐng)域中不同問題的標準算法,更重要的是分析其算法復雜度,并且在諸多可行算法中選擇一種時間或者空間效率最高的方法。美國著名算法大師Donld Knuth認為“計算機科學就是算法的研究”,他主持設計的TeX排版系統(tǒng)被譽為是“不存在Bug的系統(tǒng)”,這是以大師嚴密的算法設計基礎為保證的。前微軟高級副總裁李開復博士認為“計算機科學實質(zhì)是人工智能”,而人工智能則是模擬人類思維的一種算法科學。計算機算法的應用已經(jīng)遍及人類社會的各個領(lǐng)域,包括計算機軟硬件機器學習、電信及互聯(lián)網(wǎng)、一般制造業(yè)、經(jīng)濟與金融業(yè)等。算法技術(shù)不僅在計算機領(lǐng)域,而且在其它理工及社會科學領(lǐng)域都有極其廣泛的應用。任何問題的求解,都離不開一般性的算法設計原則,在筆者執(zhí)教的學校,數(shù)學和信息安全兩個非計算機專業(yè)已將該課程列為必修課程。因此,提高“算法設計與分析”課程教學水平有著極其深遠的意義和重要的作用。

2教材選擇

近年來,國內(nèi)引進了一些優(yōu)秀的國外教材,其中的《算法導論》是國際上被引用頻率最高而且知名度也最高的專著,但是由于它篇幅過長,在國外多用于兩個學期的教學課程,因此難以將該教材系統(tǒng)地用于學時有限的本科教學;《算法設計與分析》是美國工程院院士UIIman等三位大師合著的優(yōu)秀教材,該書的目的是將算法領(lǐng)域的基礎研究結(jié)果進行綜合,重點在于對算法思想過程的理解,而不是算法的實現(xiàn)細節(jié)和具體的編程技巧。但是該書內(nèi)容和習題難度都較大,因此更適合作為研究生教材。國內(nèi)的專家王曉東和周培德所編寫的教材也很優(yōu)秀。這些教材都被我們重點推薦給學生作為參考書。

出于上述考慮,我們最終選擇了沙特學者M.H.Alsuwaiyel所著的《算法設計技巧與分析》作為教材,該書基本覆蓋了傳統(tǒng)算法設計的主要內(nèi)容,此外還包含了概率算法和近似算法等一些基本內(nèi)容,這些內(nèi)容在傳統(tǒng)教材中并不多見,是一些高端算法經(jīng)常使用的方法。雖然該書不是歐美傳統(tǒng)名校教材,但作者在南加州大學攻讀獲得碩士和博士學位,因此該書吸收了歐美優(yōu)秀教材的風格,且文筆簡潔流暢。該書的內(nèi)容及習題難度適中,便于課堂教學及自學,是一本適合本科教學的好書。

如果一個本科生能夠?qū)W好本教材,并在后面的碩士階段,學好UIIman的《算法設計與分析》,之后再將《算法導論》學習好,則必將打下堅實的算法理論基礎,為終身的職業(yè)生涯所受用。

3興趣培養(yǎng)

本課程的教學對象是大學理工科三年級學生,要求他們不僅具備數(shù)學分析、概率及線性代數(shù)的基礎,而且具備離散數(shù)學和數(shù)據(jù)結(jié)構(gòu)等計算機專業(yè)基礎知識。很多學生剛學過數(shù)據(jù)結(jié)構(gòu),翻開算法教材,有似曾相識的感覺。教材中確實有部分章節(jié)如數(shù)據(jù)結(jié)構(gòu),排序算法,圖的遍歷等取材于數(shù)據(jù)結(jié)構(gòu)課程。因此會有些學生學習熱情不高,認為是在學習重復的課程。

針對這一情況,首先我們會教育學生兩課程的目的是不一樣的。數(shù)據(jù)結(jié)構(gòu)的目的是教會學生如果對現(xiàn)實世界中的事物及對其信息處理過程建立數(shù)據(jù)模型;而算法設計課程的重點是算法的效率問題,其主題是算法的空間和時間復雜度,主要論述如何運用算法技術(shù)改進已有一些算法的效率,或者對復雜問題進行求解。

近年來,計算機硬件和軟件技術(shù)發(fā)展迅速,CPU、外存、內(nèi)存的性能在持續(xù)提高,價格卻大幅度下跌。因此有很多人認為,軟件的效率已經(jīng)不再重要了,只要提高計算機系統(tǒng)的配置就足夠了。這種觀點顯然是錯誤的。

我們在第一節(jié)的緒論課中引用《算法導論》的例子,深入淺出地闡明了算法效率的重要性。設有兩個排序算法:其一是插入排序,時間復雜度為c1 n*n, c1是一個不依賴于n的常數(shù);其二是歸并排序,時間復雜度為c2 nlog n,c2是一個不依賴于n的常數(shù),一般情況下c1< c2。n是待排序數(shù)列的長度。對于這兩個實質(zhì)上屬于不同數(shù)量級的算法,很多人并未真正感覺到log n比n優(yōu)化多少,甚至當n較小時,插入排序比歸并排序還要快速一些。但是我們必須認識到,當n逐漸增大到一定數(shù)值以后,無論c1比c2小多少,歸并排序均比插入排序快速。在大規(guī)模數(shù)據(jù)集上排序結(jié)果的對比,則效果更為顯著。假若在高性能計算機A(10億指令/秒)上運行插入排序,而在低速計算機B(1千萬指令/秒)上運行歸并排序。此時硬件條件是機器A比機器B快了近100倍;軟件先決條件是 c1值為2, c2值為50;數(shù)據(jù)集的規(guī)模n為100萬。

計算得到:

機器A運行時間為2*(100萬*100萬)/10億=2000秒

機器B運行時間為 50*100萬*lg(100萬)≈100秒

結(jié)果是驚人的,用了快100倍的機器處理相同的數(shù)據(jù)集,反而慢幾乎20倍。如果數(shù)據(jù)集大10倍為1000萬,那么機器A要算2.3天,機器B只要20分鐘,這一差距是令人震驚的。

事實上,算法技術(shù)的發(fā)展沒能跟上硬件的發(fā)展,其發(fā)展空間還很大,盲目崇尚硬件建設而忽視算法技術(shù)的觀點是錯誤的。

在電信應用中,雖然硬件和軟件技術(shù)發(fā)展很快,但是用戶的需求更是呈爆炸式增長。一個國家網(wǎng)內(nèi)就可能有成百萬實時在線用戶,每秒幾十萬次用戶交互發(fā)生,夜間有成千萬的話單記錄要處理。當一臺內(nèi)存中存放近百萬用戶資料,則浪費16個字節(jié)就是浪費16M空間。如果記錄的數(shù)據(jù)結(jié)構(gòu)及處理算法設計不合理,則內(nèi)存很容易不夠用,大量工作任務會被拋棄。要在這樣的平臺軟件上構(gòu)建軟件,必須對每個字節(jié)空間、每個計算機指令的使用優(yōu)化到位。否則,即便有先進的計算機系統(tǒng),一般的軟件技術(shù)是無法承受高性能、高容量計算的需要的。算法技術(shù)能支持開發(fā)人員在軟件設計階段從理論層面保障系統(tǒng)的效率達到最優(yōu)。

經(jīng)首次引論性教學,絕大多數(shù)同學認識了算法課程重要性,明確了學習目的,獲得了較好的教學效果。

4理論教學

課程教學組在教材內(nèi)容上選擇了以下內(nèi)容:

(1) 算法分析基本概念,數(shù)學預備知識。這些都是本課程工具性方法。

(2) 堆和不相交理論。介紹了能有效實現(xiàn)優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)。

(3) 歸納法、分治、動態(tài)規(guī)劃。介紹了計算機技術(shù)中十分重要的遞歸為主題的設計技術(shù),遞歸要求能夠?qū)⒋鈫栴}抽象為遞推表達式,確定初試值和遞推終止條件后就能將復雜問題化解為嵌套的簡單問題。

(4) 貪心算法。介紹了如何求解最優(yōu)化問題。

(5)NP完全問題。介紹不確定性圖靈機在P時間內(nèi)能解決的問題,這類論題對于培養(yǎng)學生將來思考問題復雜度是個導論。

(6) 回朔法。介紹有組織的窮盡搜索算法,對一些問題尤其是解空間很大的問題有效。我們介紹了3著色、8皇后等經(jīng)典問題。

(7) 概率算法和近似算法。一般性介紹近20年來算法研究迅猛發(fā)展的領(lǐng)域,以擴展學生知識面,但不做考核要求。

其他內(nèi)容如數(shù)據(jù)結(jié)構(gòu)、圖遍歷等是數(shù)據(jù)結(jié)構(gòu)和圖論課的內(nèi)容,本課程內(nèi)不做講解,供學生預習課程時選讀;對于域指定問題的迭代改進和計算幾何技術(shù)等高級課題,推薦學生根據(jù)興趣自學。

近年,越來越多的國內(nèi)高校主張雙語教學。我們也有這樣的規(guī)劃,但是考慮課程有一定深度,三年級本科生英語運用還有限,為此達到最好的教學效果,在教學中先采用中文教學。但是我們鼓勵學生同步閱讀英文版教材,以更好地適應未來科研和國際化軟件研發(fā)的需要。

5科研方法及實踐能力培養(yǎng)

科研式教育并不是新生事物。在二十年前,我國清華大學、中國科技大學等名校就對高年級學生講授研究生課程,并進行導師制研教結(jié)合型教學,使得很多學生讀研時就能取得優(yōu)秀的成果。作者所執(zhí)教的是重點工科院校,有很多有利的因素便于我們展開科研式教學:一是有超過60%的學生主觀上有本科畢業(yè)后繼續(xù)深造的愿望;二是學校有豐富的圖書館資源,能全文檢索CNKI、碩博士論文、IEEE、ACM、ELSERVIER、SPRINGER等中外優(yōu)秀電子數(shù)據(jù)庫。在教學中,作者也將在科研中讀到的一些新穎實用且難度適中的論文摘錄下來介紹給學生,并將自己研究生階段的學習方法介紹給學生。除了閱讀教材,我們還鼓勵學生讀一些高端的雜志,例如計算機學科領(lǐng)域的四大學報,ACM期刊,Software Experience and Practice,Information Processing Letter等刊物,從其中檢索感興趣的論題。讀核心期刊有幾點好處:這些刊物審稿嚴格,文章無論是學術(shù)性、前瞻性、理論正確性及寫作水平都有保證;減少檢索的開銷。讀者可以先在這些高水平雜志中找到自己感興趣的主題后,再廣泛檢索與主題相關(guān)的其它刊物或會議文章。引導學有余力的本科生讀高水平論文并不是過高要求,算法設計及數(shù)據(jù)結(jié)構(gòu)教材中大部分章節(jié)內(nèi)容其實也都是來源于前二十至五十年的國際知名算法學術(shù)期刊,其中選擇ACM、IEEE及ISAM雜志內(nèi)容的比例最高?，F(xiàn)在的一些學術(shù)期刊中刊出的優(yōu)秀算法,過幾年就會被大量的引用或?qū)嶋H應用,也許再過十至二十年后就會被引入未來的教材之中。

我們認為,在本科高年級展開研究式教學對學生長遠發(fā)展有好處。對打算深造的同學,可以潛移默化地引導他們思索自己未來的發(fā)展方向,有很多成功的學者就是在大學受到某門課程老師的影響而走上科研道路的?？茖W研究是一個漫長的過程,很多工科博士生學習到第三、四年后才開始發(fā)表一級論文,很多碩士生畢業(yè)前才急忙撰寫可發(fā)表成果。而同時有些博士生入學兩年就能取得豐碩的成果,很重要的因素是他們在本科高年級階段就培養(yǎng)了研究型思維,為以后深造明確了方向并作好了理論準備。如果本科階段就培養(yǎng)研究型學習方法,那么在日后深造過程中多出成果就是水到渠成的事。而如何培養(yǎng)學生良好的研究習慣,正是我們教師要不斷探索的論題。

重視理論而實踐不足,是我國高校普遍存在的問題。

在國際上,知名的軟件鮮有來自中國人的原創(chuàng)。所以我們要更加重視培養(yǎng)學生實踐能力。

實驗環(huán)節(jié),我們布置了基本的排序、遞歸、貪心、回溯等論題的實驗,鼓勵學生用不同的編程語言實現(xiàn),不僅僅是單純的算法實現(xiàn),最好能夠編制出實用美觀的界面,將算法更友好地呈現(xiàn)出來。無論以后的工作或者深造,目標是可應用或者可發(fā)表的成果,都需要研發(fā)者具有較高的實踐能力。我們認為實踐與理論教育是并重的。

6結(jié)束語

通過四年的教學實踐,學生對此課程實踐的參與度越來越高。通過教育方法的不斷改進,學生的課程成績也一屆好于一屆。更為重要的是,通過啟發(fā)引導式教育,很多同學開始萌發(fā)研究型思維,課余經(jīng)常向老師提問,有的問題有較高難度,老師都要回去研究資料才能解答。在來自本校新入學的碩士生中,不少同學反映受益于此課,有些同學讀研究生后不久就在一級學報上發(fā)表了算法類論文,這也正是我們當初所期待的。我們教師仍然要不斷提高自身科研水平,并將研究成果及方法引進課堂,提高教學效果和質(zhì)量。

教學中,還發(fā)現(xiàn)一個現(xiàn)象,數(shù)學系的學生比計算機系的考試成績要高一些。最簡單的因素,是他們理論思維能力更強,如何因材施教,改進教學方法及增強工科學生學習本課程能力,是我們課程教學組今后要探索與研究的方向。

參考文獻:

[1] M.H.AlsuwAIyel. 算法設計技巧與分析[M]. 北京:清華大學出版社,2004.

[2] Thomas H.Cormen. 算法導論[M]. 北京:高等教育出版社,2002.

[3] Alfred V. Aho, John E. Hopcroft, Jeffery D. Ullman. 算法設計與分析(影印版)[M]. 北京:中國電力出版社,2005.