“算法設(shè)計與分析”本科課程教學(xué)研究

戴 群

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

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

中圖分類號:G642 文獻(xiàn)標(biāo)識碼:B

1引言

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

2教材選擇

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

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

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

3興趣培養(yǎng)

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

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

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

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

計算得到:

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

機(jī)器B運(yùn)行時間為 50*100萬*lg(100萬)≈100秒

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

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

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

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

4理論教學(xué)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6結(jié)束語

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

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

參考文獻(xiàn):

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

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

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