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

任建國(guó) 徐永紅 李漢倫

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

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

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

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

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

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

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

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

（三）課時(shí)短，課程本身難度大

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

（四）互動(dòng)少，反饋不及時(shí)

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

（五）考核方式單一

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

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

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

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

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

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

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

（一）課前階段

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

（二）課上階段

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

（三）課后階段

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

（四）考核階段

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

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