季曉慧 姚國清 張玉清 夏軍寶 鄭春梅

摘要：討論了算法設(shè)計與分析教學(xué)過程中對學(xué)生計算思維能力培養(yǎng)的具體方法及將在線評測系統(tǒng)引入編程實踐教學(xué)中的具體應(yīng)用方法等。

關(guān)鍵詞：算法設(shè)計與分析;計算思維;在線評測;考試

中圖分類號：G642.

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）04-0070-02

收稿日期：2019-11-27

基金項目：2019年度中國地質(zhì)大學(xué)（北京）一流課程建設(shè)項目

作者簡介：季曉慧（1977-），女，黑龍江七臺河人，副教授，博士，主要從事計算機(jī)教學(xué)和科研工作。

Cultivating the Computational Thinking and Practical Programming Abilities in Algorithm Design and Analysis Teaching

JI Xiao-hui，YAO Guo-qing，ZHANG Yu-qing，XIA Jun-bao，ZHENG Chun-mei

（School of Information Engineering，China University of Geosciences，Beijing 100083，China）

Abstract：This paper gave out the methods on cultivating the computational thinking ability in algorithm design and analysis teaching.Methods that uses online judge system in cultivating practical programming ability in algorithm design and analysis were also discussed.

Key words：Algorithm Design and Analysis;Computational Thinking;Online Judge;Examination

算法被譽(yù)為計算機(jī)學(xué)科的靈魂，是支撐計算機(jī)科學(xué)的核心和基石，是計算機(jī)科學(xué)研究的永恒主題[1]。因此算法設(shè)計與分析課程也處于計算機(jī)科學(xué)與技術(shù)學(xué)科的核心位置，是計算機(jī)學(xué)科最重要的專業(yè)基礎(chǔ)課之一，在國內(nèi)外各大高校計算機(jī)專業(yè)課中都處于核心地位。算法設(shè)計與分析課程講授使用計算機(jī)解決實際問題時可以采用的經(jīng)典方法，如遞歸與分治法、動態(tài)規(guī)劃法、貪心法、回溯法、分支界限法等，并講授各種算法的基本原理、復(fù)雜性分析、實現(xiàn)方法和應(yīng)用實例等。通過該課程的學(xué)習(xí)，使學(xué)生掌握常用的算法設(shè)計分析、實現(xiàn)和比較方法以及計算復(fù)雜性分析理論和評價算法性能的標(biāo)準(zhǔn)，培養(yǎng)學(xué)生的問題抽象和建模能力以及能夠針對具體實際問題設(shè)計出高效算法的實踐能力。算法設(shè)計與分析課程既包含抽象的理論，又強(qiáng)調(diào)算法的實踐，對于提升學(xué)生的邏輯思維能力和編程解決實際問題的能力有著非常重要的意義[2]，能為學(xué)生進(jìn)一步分析和解決計算機(jī)科學(xué)與技術(shù)領(lǐng)域的復(fù)雜工程問題奠定良好基礎(chǔ)。

算法設(shè)計與分析課程兼具理論性與實踐性強(qiáng)的特點(diǎn)，實際教學(xué)中易出現(xiàn)要么過于強(qiáng)調(diào)理論而忽略編程實踐要么過于強(qiáng)調(diào)編程實踐而忽略算法背后的計算思維的情況;或者存在讓學(xué)生編程實踐過程中缺乏有代表性、趣味性強(qiáng)或者有實際意義的題目的情況，進(jìn)而學(xué)生對課程沒有興趣;并且算法設(shè)計與分析課程對前序課程，比如《數(shù)據(jù)結(jié)構(gòu)》《離散數(shù)學(xué)》《程序設(shè)計語言》等有依賴性，而這些前序課程本身也有一定難度，會存在學(xué)生基礎(chǔ)不夠牢固的情況，進(jìn)而影響學(xué)生對課程的理解。針對上述問題，可以在教學(xué)過程中注重以下幾個方面：

1 注重學(xué)生計算思維能力的培養(yǎng)

計算思維由美國卡內(nèi)基·梅隆大學(xué)周以真（JeannetteM.Wing）教授于2006年第一次明確提出并將其解釋為“‘運(yùn)用計算的基礎(chǔ)概念求解問題、設(shè)計系統(tǒng)和理解人類行為的一種方法”，并預(yù)見計算思維將成為像讀、寫、算一樣，每個人必備的認(rèn)知技能。有學(xué)者認(rèn)為計算思維是計算機(jī)科學(xué)最具有基礎(chǔ)性和長期性的思想，涉及邏輯地組織和分析數(shù)據(jù)、分解問題，算法設(shè)計、程序化的執(zhí)行技巧，并且可以將問題解決過程拓展到社會和人文領(lǐng)域[3]。計算思維能力具體包括以下9個能力點(diǎn)：問題的符號表示、問題求解過程的符號表示、邏輯思維抽象思維、形式化證明、建立模型、實現(xiàn)類計算、實現(xiàn)模型計算、利用計算機(jī)技術(shù)[4]。而算法設(shè)計與分析解決問題的過程是：理解和把握問題背景及其相關(guān)知識，并用符號化的語言對所求解問題進(jìn)行表示;設(shè)計解決問題的方法并用符號化的語言描述方法;分析所提方法的復(fù)雜度并進(jìn)行適當(dāng)改進(jìn);選擇能夠表達(dá)問題并與解決方法相適應(yīng)的數(shù)據(jù)結(jié)構(gòu);編寫代碼;迭代調(diào)試;最終完成計算機(jī)的問題求解?？梢娝惴ㄔO(shè)計與分析過程覆蓋了計算思維所要求的能力點(diǎn)，是計算思維的具體體現(xiàn)。因此需要在具體的教學(xué)過程中強(qiáng)化上述思維過程，將計算思維的培養(yǎng)融入教學(xué)當(dāng)中，以提高學(xué)生的計算思維能力。

具體在教學(xué)過程中應(yīng)注意以下幾點(diǎn)：（1）板書與多媒體教學(xué)相結(jié)合。即宜用板書一步一步地介紹算法求解某一問題的具體步驟，以讓學(xué)生更好地掌握該算法求解問題的具體計算思維過程;（2）算法講授過程中，學(xué)生上機(jī)實踐前，不使用具體的編程語言。宜用偽代碼、流程圖等形式進(jìn)行算法的講述，使學(xué)生暫時不被具體的編程細(xì)節(jié)所累，而是專注于算法思想及其計算思維的理解;（3）強(qiáng)調(diào)算法復(fù)雜性分析及算法對比。算法講授過程中注意對算法及其求解具體問題時的復(fù)雜性進(jìn)行分析，培養(yǎng)學(xué)生對算法的分析能力，并注意引導(dǎo)學(xué)生對所學(xué)算法與已學(xué)過算法進(jìn)行對比，以使學(xué)生養(yǎng)成評價算法的習(xí)慣;（4）注意對前序課程知識的鞏固及后序知識的擴(kuò)展。算法是計算機(jī)程序設(shè)計的靈魂，許多算法在前序課程的數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計基礎(chǔ)等已經(jīng)講授，如快速排序、堆排序、最小生成樹、單源最短路徑算法等，需要在授課過程中進(jìn)一步指明這些算法思想，使學(xué)生強(qiáng)化這些算法背后的計算思維，保持學(xué)習(xí)的連貫性及扎實性。許多算法，如回溯法、分支限界法等又是后續(xù)課程，如人工智能課程的重要知識點(diǎn)，授課過程中也應(yīng)向?qū)W生進(jìn)行擴(kuò)展，以提高學(xué)生對課程的重視，為后續(xù)課程的學(xué)習(xí)打下良好基礎(chǔ)。

2 注重學(xué)生實踐編程能力的培養(yǎng)

計算機(jī)相關(guān)學(xué)科在算法設(shè)計與分析授課過程中除了注重計算思維的培養(yǎng)，也要注重對學(xué)生實踐編程能力的培養(yǎng)，做到理論與實踐并重、理論能夠用于實踐，使學(xué)生真正具備使用計算機(jī)解決實際應(yīng)用問題的能力。在線評測系統(tǒng)是一套 能對程序源代碼進(jìn)行自動評判的計算機(jī)應(yīng)用軟件，其通過對學(xué)生用網(wǎng)頁瀏覽器提交到服務(wù)器的源代碼進(jìn)行在線編譯，生成可執(zhí)行文件并產(chǎn)生輸出，并將輸出與服務(wù)器數(shù)據(jù)庫中的測試數(shù)據(jù)中的輸出文件進(jìn)行逐字節(jié)的對比來判斷學(xué)生提交程序的正確性，同時對耗時、耗費(fèi)內(nèi)存等方面進(jìn)行評測，并將評測結(jié)果保存在數(shù)據(jù)庫中且返回給用戶。其除對源代碼進(jìn)行評判之外，還具有用戶管理、題庫管理、在線比賽及在線討論等功能，已被眾多高校用于計算機(jī)輔助教學(xué)[5]。在線評測系統(tǒng)具有嚴(yán)謹(jǐn)、通過對已求解題目數(shù)量的累積及所在排名的實時查看激發(fā)學(xué)生的上機(jī)實踐自主性及實踐編程興趣、能形成學(xué)生之間的討論和交流氛圍等特點(diǎn)，因此十分適于算法設(shè)計與分析課程的實踐教學(xué)。

在使用在線評測系統(tǒng)進(jìn)行算法設(shè)計與分析的題庫建設(shè)上可以采用以下幾種方式：（1）將教材經(jīng)典問題轉(zhuǎn)化為適于進(jìn)行在線評測的實踐題目;（2）挖掘整理在線評測系統(tǒng)中的原有題目，將其中與算法設(shè)計與分析課程知識點(diǎn)結(jié)合緊密的題目用于課程實踐;（3）鼓勵優(yōu)秀學(xué)生結(jié)合課程所學(xué)知識點(diǎn)為題庫出新題，新題一旦被采用可以以加分作為鼓勵。

在具體實踐上，每次包含簡單、中等難度及難題三類，以讓不同層次的學(xué)生都能得到訓(xùn)練。并將每次實踐完成情況按所通過題目的數(shù)量進(jìn)行排序，折算后計人最終成績，以加強(qiáng)學(xué)生對編程實踐的重視。實踐過程中，教師要以抽查等方式了解學(xué)生掌握情況，及時發(fā)現(xiàn)問題并予以糾正。在線評測系統(tǒng)還用于學(xué)完所有算法后的綜合上機(jī)考試，題目覆蓋所有知識點(diǎn)，要求在平時上機(jī)實踐的兩倍時間內(nèi)完成指定題目。

算法設(shè)計與分析要求以時間復(fù)雜度盡量低的方法及程序解決實際問題，因此對同一問題的不同算法分析與對比尤為重要，需要學(xué)生在學(xué)完所有算法后對某一典型問題采用不同算法進(jìn)行求解并予以分析比較并完成綜合報告。學(xué)生的最終成績由平時成績（出勤、討論及講解、課后作業(yè)）20%+上機(jī)實踐及報告55%+綜合上機(jī)10%+綜合報告15%=100%進(jìn)行評定。

3結(jié)論

算法設(shè)計與分析課程兼具理論與實踐性，教學(xué)過程中需要既注重計算思維能力的培養(yǎng)，又注重實踐編程能力的培養(yǎng)?？梢酝ㄟ^板書與多媒體教學(xué)相結(jié)合、算法講授過程中，，學(xué)生上機(jī)實踐前，不使用具體編程語言、強(qiáng)調(diào)算法復(fù)雜性分析及算法對比及注意對前序課程知識的鞏固及后序知識的擴(kuò)展等方式培養(yǎng)學(xué)生的計算思維能力;通過將在線評測系統(tǒng)應(yīng)用到編程實踐中，培養(yǎng)學(xué)生的實踐編程能力。最終為學(xué)生以高性能的算法解決實際應(yīng)用問題打下良好基礎(chǔ)。

參考文獻(xiàn)：

[1]王紅梅，胡明.算法設(shè)計與分析（第2版）[M].北京：清華大學(xué)出版社，2013：7.

[2]張遠(yuǎn)平，邱麗娜在算法設(shè)計與分析課程教學(xué)中融入計算思維[J].價值工程，2016（8）：245-247.

[3]狄長艷，周慶國，李廉.新工科背景下對于計算思維的再認(rèn)識[J]中國大學(xué)教學(xué)，2019（7）：47-53

[4]教育部高等學(xué)校計算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會.高等學(xué)校計算機(jī)科學(xué)與技術(shù)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)[M].北京：機(jī)械工業(yè)出版社，2010：25-36.

[5]季曉慧，張玉清.C程序設(shè)計教學(xué)中的在線評測系統(tǒng)應(yīng)用[J].電腦知識與技術(shù)，2014，10（7）：1465-1466.

[通聯(lián)編輯：王力]