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

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

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

中圖分類號：G642.

文獻標識碼：A

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

收稿日期：2019-11-27

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

作者簡介：季曉慧（1977-），女，黑龍江七臺河人，副教授，博士，主要從事計算機教學(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

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

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

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

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

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

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

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

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

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

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

3結(jié)論

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

參考文獻：

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

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

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

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

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

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