計算思維與實踐編程能力培養并重的算法設計與分析教學

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

摘要：討論了算法設計與分析教學過程中對學生計算思維能力培養的具體方法及將在線評測系統引入編程實踐教學中的具體應用方法等。

關鍵詞：算法設計與分析;計算思維;在線評測;考試

中圖分類號：G642.

文獻標識碼：A

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

收稿日期：2019-11-27

基金項目：2019年度中國地質大學（北京）一流課程建設項目

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

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

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

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

1 注重學生計算思維能力的培養

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

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

2 注重學生實踐編程能力的培養

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

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

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

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

3結論

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

參考文獻：

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

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

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

[4]教育部高等學校計算機科學與技術教學指導委員會.高等學校計算機科學與技術專業人才專業能力構成與培養[M].北京：機械工業出版社，2010：25-36.

[5]季曉慧，張玉清.C程序設計教學中的在線評測系統應用[J].電腦知識與技術，2014，10（7）：1465-1466.

[通聯編輯：王力]