基于立體化的算法設(shè)計與分析教學(xué)模式改革*

任建國 徐永紅 李漢倫

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

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

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

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

（一）教學(xué)模式單一

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

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

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

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

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

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

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

（五）考核方式單一

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

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

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

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

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

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

三、立體化教學(xué)模式的四個階段

（一）課前階段

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

（二）課上階段

課上采用小組討論方式，根據(jù)課前的相關(guān)準(zhǔn)備，每次課多位同學(xué)輪流講解一部分內(nèi)容，講解時可以配合ppt、演示視頻和板書等，學(xué)生在講解某類算法時可以結(jié)合其應(yīng)用背景，把抽象的算法和現(xiàn)實問題相聯(lián)系，加深對算法思想的理解和記憶。教師在講解過程中或講解結(jié)束后進(jìn)行提問和補(bǔ)充，爭取所有同學(xué)都能參與討論。此外，教師和學(xué)生在講解某類算法的思想或應(yīng)用實例時可以前后對比，聯(lián)系貫通，這樣才能更深入理解各種算法的特點(diǎ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ī)劃效率更高。

（三）課后階段

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

（四）考核階段

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

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