任建國 徐永紅 李漢倫

（1.江蘇師范大學智慧教育學院；2.江蘇師范大學生命科學學院）

算法理論是計算機科學的重要研究內(nèi)容，并且在計算機出現(xiàn)前的很長一段時間內(nèi)，人們就已對算法有了深入的研究，并將其應(yīng)用到實際生活中。根據(jù)算法的定義，它是執(zhí)行不同功能所需的預定義的、獨立且有限的指令序列，其規(guī)則可以追溯到公元前300 年，最早被發(fā)現(xiàn)刻在巴比倫的泥板上。最早和最基本的算法是古代人用來記錄他們的谷物和牛的一系列標記方案，隨之而來的是數(shù)字系統(tǒng)的出現(xiàn)，以及隨后算盤、代數(shù)和變量的演變，產(chǎn)生了參與制定評估系統(tǒng)的符號和規(guī)則，后來算法在計算機程序和機械應(yīng)用中找到了自己的位置?！八惴ā?algorithm)一詞的起源被認為是由波斯天文學家和數(shù)學家穆罕默德·本·穆薩·阿爾·花 剌 子 模(Abu Abdulloh Muhammad ibn Muso al-Xorazmiy)(約公元850 年)提出，他的工作包括向西方世界介紹數(shù)字系統(tǒng)中的十進制位，以及有史以來第一個線性和二次方程的系統(tǒng)解。我們今天所知道的算法是隨著機械工程和過程的出現(xiàn)和興起才被應(yīng)用的。在最初的形式中，算法為邏輯代數(shù)提供了基礎(chǔ)，在計算中使用變量。最早的算法例子包括數(shù)論中最大公約數(shù)的歐幾里得函數(shù)、阿基米德對π 的逼近以及厄拉多塞對素數(shù)的計算。第一個使用算法這個術(shù)語的最初形式的人是12 世紀的英國哲學家阿德拉德(Adelard of Bath)，他在翻譯阿爾·花剌子模的阿拉伯作品時使用了算法這個術(shù)語。算法進化的一系列重大成就出現(xiàn)在19 世紀，其中第一項是由英國數(shù)學家喬治·布爾建立的，他還撰寫了《思維定律》并建立了布爾代數(shù)。1847 年，布爾將邏輯與計算統(tǒng)一起來，形成了二進制代數(shù)，這是今天計算邏輯的基礎(chǔ)。隨著60 年代末個人電腦的出現(xiàn)，算法也有所改進。算法在我們?nèi)粘Ｉ钪械拿恳粋€時刻都有應(yīng)用，例如，在智能手機上，其相機拍攝的照片的色彩平衡由一組算法定義，這些算法根據(jù)場景識別顏色并平衡對比度。隨著處理能力的提高，算法的復雜性和計算能力也在增長。

算法設(shè)計在各學科的夾縫中找到了立足之地，它是數(shù)學與工程技術(shù)糅合而成的怪異混合體?，F(xiàn)在，為人類設(shè)計算法的工作也面臨相同的境遇——找不到一個現(xiàn)成的歸屬學科。今天的算法設(shè)計不僅需要借助計算機科學、數(shù)學和工程技術(shù)，還需要得到統(tǒng)計學、運籌學等相關(guān)領(lǐng)域的幫助。此外，我們不僅需要考慮計算機算法設(shè)計與人類思維活動之間的關(guān)系，還需要認真研究認知學、心理學、經(jīng)濟學等學科。作為高校計算機專業(yè)的一門核心專業(yè)課程，教學目的是通過課程學習后能理解各種算法的思想，掌握算法復雜性的分析方法以及算法評判的準則。由于課程的實踐性和應(yīng)用性較強，學生需要根據(jù)具體實例設(shè)計出具有一定精度和效率的算法，并通過上機編程實現(xiàn)。不同類型的算法通常對應(yīng)和解決一類特定的問題，并且都有各自的適用條件和局限性。[1]首先要深入理解算法的思想，就離不開高等數(shù)學、線性代數(shù)、離散數(shù)學和概率統(tǒng)計等數(shù)學知識。在理解遞歸、分治、動態(tài)規(guī)劃和回溯等重要思想后，通過練習課后習題和競賽試題提高問題分析能力、程序設(shè)計能力?；谡n程的特殊性，傳統(tǒng)的以課堂和教師為中心的教學模式難以滿足教學要求，[2]因此，迫切需要改變教學方式，以實踐運用為目的，以學生為中心，以培養(yǎng)創(chuàng)新意識為導向，以加強問題分析能力為主線，以算法設(shè)計策略為知識單元，結(jié)合高校教育工作的現(xiàn)狀，追蹤國際當前研究熱點和技術(shù)水平，為學生的后續(xù)學習和深造打下堅實基礎(chǔ)。

一、傳統(tǒng)教學現(xiàn)狀及存在問題

（一）教學模式單一

算法設(shè)計與分析課程傳統(tǒng)的教學模式主要包括兩個環(huán)節(jié)：課堂教學和期末考核。課堂教學以教師講解為主，學生課堂參與度較低，獨立思考不足。期末考核方式單一，以試卷形式為主，無法全面考核學生的實踐應(yīng)用能力和創(chuàng)新能力，[3-4]對于兼具理論性與實踐性的算法分析與設(shè)計課程缺少多樣化和立體化，難以有效發(fā)揮教學的作用。培養(yǎng)學生學習主動性是提高教學質(zhì)量的關(guān)鍵，包括學生在學習過程中主動提出新問題、新算法。

（二）未考慮不同學生的基礎(chǔ)

程序匯編語言、數(shù)據(jù)結(jié)構(gòu)等課程是算法設(shè)計與分析課程的基礎(chǔ)，[5]在設(shè)計算法解決實例問題的過程中，離不開數(shù)學，如問題規(guī)模、復雜性的分析等，更離不開數(shù)據(jù)結(jié)構(gòu)，不同學生的基礎(chǔ)可能差別較大，基礎(chǔ)較薄弱的學生可能出現(xiàn)課上難以聽懂或掌握某個算法后難以編程實現(xiàn)的情況。傳統(tǒng)教學模式缺乏對不同基礎(chǔ)學生的區(qū)分對待，未將學生作為教學主體，教學彈性和靈活性不足。

（三）課時短，課程本身難度大

課程的內(nèi)容兼具深度和廣度，對學生的抽象思維能力、邏輯思維能力、靈活運用算法解決問題的能力要求較高，且由于課程重在理解，死記硬背的學習方法難以奏效。課程的學習不僅要掌握算法設(shè)計的方法，還要能解決實際應(yīng)用問題，這對學生的邏輯思維和數(shù)學有一定要求。[6]在課堂學習中，面對抽象的算法思想和枯燥的數(shù)學推導，基礎(chǔ)不牢的學生無法跟上教師的進度，造成一知半解和學習興趣的喪失。在課時普遍不足的情況下，課程教學很難涉及所有的算法思想和經(jīng)典實例問題。

（四）互動少，反饋不及時

課下學生很少反饋學習情況，教師不能及時追蹤學生的掌握情況。由于課時短以及學生基礎(chǔ)參差不齊，對于某類算法，學生可能還未進行充分的實例編程練習就進入下一類算法類型的學習，從而無法充分消化，導致滾雪球情況的發(fā)生。師生的互動是保證教學質(zhì)量的重要環(huán)節(jié)，教師應(yīng)及時跟進和了解學生理論知識部分的掌握情況，同時關(guān)注學生在上機實踐過程中遇到的問題和困難，及時引導、糾正錯誤。

（五）考核方式單一

傳統(tǒng)的考核方式重理論輕實踐，原因在于，平時的教學中在實踐部分的投入不夠，學生的編碼訓練不足，在最終考核時難以將算法理論和算法思想落實到實踐運用中。因此應(yīng)改革考核方式，加大實踐比重，同時在教學過程中引導學生多閱讀優(yōu)秀代碼和程序設(shè)計方法，從練習模仿別人的程序開始逐漸過渡到獨立設(shè)計完整程序，以練促學。

二、算法設(shè)計與分析教學模式改革的必要性

與其他專業(yè)性課程相比，算法設(shè)計與分析課程需要構(gòu)建一套系統(tǒng)性的教學體系，其中實踐環(huán)節(jié)是關(guān)鍵，沒有實踐，學習毫無意義。每學完一個新算法或新題目，都應(yīng)該把它運用起來，這將有助于長期的記憶和更深的理解。當學會一個新算法后，及時做幾道相關(guān)練習題。練習應(yīng)該分兩個階段進行。首先是當你第一次學習某個新算法的時候。在這個階段，應(yīng)該專注于真正理解所涉及的內(nèi)容以及所用的算法為什么有效。第二階段是在你對這些概念感到滿意之后。在這一點上，你應(yīng)該給自己計時，爭取越來越快的解決時間。在課程開始的幾天，根據(jù)問題的難度，可能要花費15-45 分鐘內(nèi)設(shè)計出有效算法解決一個問題。在課程開始后的幾周后，這個時間應(yīng)該開始減少。經(jīng)過一兩個月的持續(xù)練習(不僅僅是時間流逝)，學生應(yīng)該能夠按時解決相當數(shù)量的問題。在學習的前期，學生首先要閱讀別人已實現(xiàn)的算法，這一過程應(yīng)專注于理解它為什么以這樣的方式實現(xiàn)，而不是試圖記住確切的代碼。

為保證每個環(huán)節(jié)的順利進行，提高教學質(zhì)量，迫切需要對傳統(tǒng)單一、被動的教學模式進行改革，構(gòu)建一套立體化的教學體系，充分發(fā)揮教師、網(wǎng)絡(luò)、教材和算法競賽的作用。該立體化教學模式的四階段框架圖如圖1 所示。

在教學過程中，教師始終需要將“復雜問題簡單化”的理念貫穿于教學的四個階段，通過挖掘算法本質(zhì)和列舉通俗易懂的事例使學生深刻理解和掌握原理和概念。以動態(tài)規(guī)劃為例，動態(tài)規(guī)劃是一種通過將復雜問題分解成更簡單的子問題來解決復雜問題的方法，思路是先解決子問題并記住它們的結(jié)果，利用子問題的結(jié)果來快速解決復雜的問題。比如，在一張紙上寫下“1+1+1+1+1+1+1+1 =”，計算機結(jié)果為8，接著在左邊寫下另一個“1+”很快就得到9 這個答案，利用動態(tài)規(guī)劃的思想，得到9 的過程不需要把之前的過程重新計算一遍，因此簡單地說它是一種“記住結(jié)果以節(jié)省時間”的方式。以上是動態(tài)規(guī)劃的直觀理解，另一個重要的問題是理解該策略的適用場景，以及哪些情況不適用。如上所述，如果一個問題可以分解成子問題，這些子問題可以分解成小得多的子問題，并且其中一些子問題有重疊(即需要計算以前計算的值)，且問題的主要目標是通過存儲子問題的結(jié)果來減少值的計算的重復，這時可以考慮動態(tài)規(guī)劃。需要指出，動態(tài)規(guī)劃不應(yīng)與遞歸相混淆，遞歸是一種通過用函數(shù)的其他值直接或間接表示該函數(shù)的值來尋找解的方法，這種函數(shù)被稱為遞歸函數(shù)，它遵循自上而下的方法。動態(tài)編程只不過是帶有記憶的遞歸，即計算和存儲值，這些值可以在以后訪問以解決再次出現(xiàn)的子問題，從而使代碼更快并降低時間復雜性，這里的基本思想是通過有效利用空間來節(jié)省時間。遞歸算法代碼直觀簡潔，而動態(tài)規(guī)劃使用空間來存儲子問題的解供后續(xù)的計算使用，從而節(jié)省時間。

綜上所述，在教學中應(yīng)先以通俗易懂的例子介紹算法原理和要點，之后逐步引申，同時注意不同算法之間的聯(lián)系和區(qū)別，逐漸設(shè)計出高效的算法。充分理解原理是靈活運用的前提，算法類型和數(shù)據(jù)對象可以千變?nèi)f化，當遇到一個無法用現(xiàn)有算法和數(shù)據(jù)結(jié)構(gòu)很好解決的新問題時，怎樣構(gòu)造有效的問題求解方法是學習過程中的重點問題，只有掌握了算法設(shè)計的思想，才能設(shè)計出解決問題的算法。

三、立體化教學模式的四個階段

（一）課前階段

課前階段是課上階段的必要準備，離散數(shù)學、數(shù)據(jù)結(jié)構(gòu)或c++等相關(guān)課程知識不扎實的學生可以充分利用課前階段及時進行相關(guān)內(nèi)容的回顧和補漏，提高課上學習效率。此外，教師每次上課前提前幾天下發(fā)本次課程的相關(guān)學習內(nèi)容，給學生預留充分的時間明確學習方向和學習重點，學生在課前做好相關(guān)準備工作，提前熟悉教材和教學內(nèi)容。同時，教師引導學生充分利用網(wǎng)絡(luò)資源，對于難點問題通過查閱相關(guān)書籍和觀看網(wǎng)絡(luò)教學視頻等方式解決。同時建立網(wǎng)絡(luò)學習交流平臺或群組，方便師生間的互動交流、及時反饋和跟蹤學習情況。

（二）課上階段

課上采用小組討論方式，根據(jù)課前的相關(guān)準備，每次課多位同學輪流講解一部分內(nèi)容，講解時可以配合ppt、演示視頻和板書等，學生在講解某類算法時可以結(jié)合其應(yīng)用背景，把抽象的算法和現(xiàn)實問題相聯(lián)系，加深對算法思想的理解和記憶。教師在講解過程中或講解結(jié)束后進行提問和補充，爭取所有同學都能參與討論。此外，教師和學生在講解某類算法的思想或應(yīng)用實例時可以前后對比，聯(lián)系貫通，這樣才能更深入理解各種算法的特點和對具體問題的適用性。比如具有最優(yōu)子結(jié)構(gòu)的0-1 背包問題，[7-8]動態(tài)規(guī)劃是解這一類問題的常用方法，由于問題本身的性質(zhì)，貪心算法卻只能得到局部最優(yōu)解而不能產(chǎn)生整體最優(yōu)解。對于單船最優(yōu)裝載問題，利用重量最輕的貨物先裝船的貪心策略，最終可以產(chǎn)生最優(yōu)解，且該方法比動態(tài)規(guī)劃效率更高。

（三）課后階段

課后學生通過上機對典型問題進行編程練習，題目選取從易到難，循序漸進，逐步培養(yǎng)算法分析和設(shè)計的方法和技巧，避免一開始產(chǎn)生畏難心理而失去興趣。在逐漸熟悉算法原理后學生應(yīng)嘗試獨立設(shè)計和編寫完整代碼，養(yǎng)成良好的程序設(shè)計習慣。對于學有余力的學生，教師鼓勵其參加天池、挑戰(zhàn)杯、百度之星等國內(nèi)競賽和ACM/ICPC、kaggle 等國際競賽，旨在加深對算法的理解、加強學術(shù)交流、培養(yǎng)團隊協(xié)作精神、逐步培養(yǎng)程序設(shè)計思維的同時將所學付諸實踐。教師則以“教練”和“導師”的身份對學生開展指導，提供賽事上的建議和幫助。學生通過查看比賽排行榜還可以對自身水平有一個定位，明確努力方向。教師還應(yīng)引導學生查閱算法設(shè)計領(lǐng)域的最新研究成果，了解最新的研究熱點和動態(tài)。

（四）考核階段

考核方式采用試卷與論文相結(jié)合的方式，試卷為輔，測查學生對基本理論知識的掌握，論文為主，檢驗學生的實踐應(yīng)用能力和創(chuàng)新能力。試卷以算法分析題為主，主要分析算法的性能和復雜性。學生首先應(yīng)能根據(jù)問題特點把其歸為某一類特定問題，并能找到對應(yīng)的算法，如背包問題可以用動態(tài)規(guī)劃、回溯法等，另外算法的適用性需要根據(jù)具體問題進行具體分析。論文的方向可以是對實際應(yīng)用問題用算法進行實現(xiàn)或解決，并思考算法的改進和優(yōu)化方法，這就要求對算法的原理有較深入的理解。此外，問題的解決最終還是要落實到代碼上，因此充分的上機實操也是必不可少的環(huán)節(jié)。論文形式的考核方式雖然對學生來說有一定難度，但能很好地激發(fā)學生去主動思考、積極創(chuàng)新，對所學算法活學活用。

在目前的教學模式中，很多學習內(nèi)容集中在課上完成，而要依靠有限的上課時間難以達成課程的教學要求。本文提出的立體化教學模式把學習內(nèi)容分散到四個階段，分別為課前階段、課上階段、課后階段和考核階段，每個階段同等重要且均是不可缺失的學習環(huán)節(jié)。做好每個階段相應(yīng)的任務(wù)對切實掌握程序設(shè)計的方法和提高對實際問題的分析解決能力具有重要作用，是使學生在知識、方法、應(yīng)用、創(chuàng)新四個方面能力全方位提高的必要途徑。