在算法設計與分析課程教學中融入計算思維

張遠平

摘要：介紹了算法設計與分析課程教學的基本內容，然后從推動人類文明進步和科技發展三大科學思維之一的“計算思維”入手，闡述了計算思維在大學課程教學中的重要性。最后對在算法設計與分析教學中融入計算思維提出了幾點建議。

Abstract： Basic teaching contents of design and analysis of algorithms is introduced. Proceeding with the computational thinking——one of three scientific thinkings that have promoted human civilization and scientific development， the importance of computational thinking is stated. Finally， some suggestions for integrating computational thinking into teaching of design and analysis of algorithms are proposed.

關鍵詞： 算法設計與分析；計算思維；教學改革

Key words： design and analysis of algorithms；computational thinking；teaching innovation

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1006-4311（2016）08-0245-03

0 引言

思維能力對人類生活和科技發展的關鍵意義不言而喻。近年來，計算思維在計算機科學教學中的重要意義得到了普遍關注，眾多學者和組織參與了這一思想的討論和傳播。然而，如何合理設置課程體系，科學地落實培養過程，在教學中真正使學生的計算思維能力得到培養，我們依然面臨著嚴峻的挑戰。本文介紹了算法設計與分析課程的一般框架和計算思維的思想，并就如何在該課程教學中融入計算思維提出一些建議，希望引起更多專業人員進行探討，并引起重視。

1 算法設計與分析

計算過程的效率和計算結果的準確性是古老的研究課題。科學技術的發展使得人們一方面更容易獲得大量的信息，另一方面對這些信息的處理（計算）方法變得日趨復雜，計算量也越來越大。許多理論上可以計算的問題，由于計算過程中所需空間或者時間的限制，而變成了現實不可計算的問題，造成了雖然理論上可計算但現實條件不允許的矛盾。自20世紀中期以來，隨著各個領域算法研究工作的發展，誕生了一個新的研究領域，即算法的設計與分析。這一領域的研究成果不僅對不同學科問題提供了有效的解決方法，而且提供了一種獨特的處理問題的思維方式。

由于實際問題求解的需求以及算法的廣泛應用，算法研究領域已是包羅萬象。從最初的排序、查詢、圖算法、數值計算等，到信息處理、工程計算與模擬、金融分析、生物計算、量子計算，以及最前沿的大數據分析，計算機的應用無處不在，算法的應用也無處不在[1-5]。按照算法所處理的對象進行分類，算法設計與分析主要包括數值算法和非數值算法兩大領域。數值算法主要有多項式計算、矩陣計算、有限域計算、數論計算，方程（組）求解，優化計算等，非數值算法主要有排序、搜索、幾何問題的計算、離散結構的計算、模式匹配等。按照計算時所需數據的提供情況可分為離線算法和在線算法，前者是指計算中所需數據在計算開始時已全部提供，后者指計算開始時不提供或部分提供數據，然后在計算過程中逐步提供數據，其典型的應用是股市風險和效益的評估分析。按照計算方式進行分類，則可分為串行算法和并行算法，還可以分為智能算法、近似算法、隨機型算法、交錯型算法、非確定型算法、確定型算法等。

算法設計的任務是對各類具體問題設計高質量的算法，以及研究設計算法的一般規律和方法。常用的算法設計方法主要有回溯法、貪婪法、分治法、概率方法和近似方法等[6]。算法分析的主要任務則是對于所設計的每一個具體算法，討論它的時間和空間復雜度、相關概率、近似比和競爭比等，分析的結果既可作為評價算法質量的標準，也可為改進算法提供參考方向。

由于算法設計與分析在計算機學科中的重要地位，其基本內容已經成為計算機相關學科的一門專業核心必修課程。算法設計與分析課程的教學方式、內容和質量，必須能夠確保培養學生的學習興趣，提高學習效果，以便提高學生專業能力和綜合能力的培養，為學生高水平高層次應用和發展提供保障。

2 計算思維

計算思維是多種學科學習和研究人員所必備的基本素質，甚至與人們的生活也密切相連。科學界一般認為，計算思維、實驗思維和理論思維是推動人類文明進步和科技發展的三大科學思維方式。近些年，諸多學者從計算思維的定義、內容、特點和培養方式等多方面進行了探討。計算思維能力包括抽象能力和邏輯思維能力，必須經過系列數學和抽象程度較高的理論課程漸進、系統地訓練才能形成[7]。2006年，原美國卡耐基·梅隆大學計算機系主任，現美國基金會計算機和信息科學與工程部主任周以真（Jeannette M. Wing）教授在國際權威雜志上發表文章，明確了計算思維的一般定義：“計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動”。在此基礎上周教授對計算思維給出了更詳盡的描敘（或定義），對計算思維是什么，或不是什么的特征給出了界定，指出了計算思維是每個人的基本技能，不僅僅屬于計算機科學家[8]。

計算思維這一概念提出后，立即引起了國際計算機界的廣泛關注，已經成為當今社會計算機教育研究的重點課題，美國教育界對此給予了大力支持，卡耐基·梅隆大學成立了專門的課題進行研究，很多相關組織和團體都參與了這項研究，比如美國數學研究所（AIM）、美國國家計算機科學技術教師協會（CSTA）、美國計算機協會（ACM）等，不僅如此，計算思維還有效促進了美國國家科學基金會（NSF）重大基金資助計劃CDI（Cyber-Enabled Discovery and Innovation）的產生，CDI計劃旨在使用計算思維產生的新思想、新方法，促進美國自然科學和工程技術領域產生革命性的成果，CDI的最終研究成果將使人們的思維模式發生轉變。而這種轉變不僅延伸到了美國國家自然科學與工程，也體現在了社會經濟與技術等各個學科領域。同時，計算思維的影響也逐漸從美國延伸到了英國的教育界，在英國的愛丁堡大學開展了很多與計算思維相關的研討會，重點討論了計算思維對不同學科的影響，比如教育、建筑、醫學、生物、物理、哲學等。此外，英國的計算機學會也組織了相關學者對計算思維進行研討，提出了歐洲的行動綱領。

國內為了緊跟國際學術的研究步伐，加緊更新傳統的教學理念，開展了多次計算思維的專題研討會，參會團體包括全國各高等學校計算機教育研究組織等。研討內容主要包括如何以課程為載體講授面向學科的思維方法，以及這種講授對國家科學與教育事業發展的作用等。2010年7月，九所知名高校在西安交通大學舉辦了“C9高校聯盟計算機基礎課程研討會”，這九所知名高校分別是西安交通大學、哈爾濱工業大學、中國科枝大學、南京大學、上海交通大學、浙江大學、復旦大學、清華大學、北京大學。教育部高等學校計算機基礎課程教學指導委員會主任陳國良院士，作了“計算思維能力培養研究”的報告，并主持了該專題的討論。經大會研究討論后就增強大學生計算思維能力的培養發表了“九校聯盟（C9）計算機基礎教學發展戰略聯合聲明”，聲明中強調“旗幟鮮明地把‘計算思維能力的培養作為計算機基礎教學的核心任務[9]”。《中國大學教學》連續發表有關計算思維的文章，一批知名學者如陳國良、李廉等積極參與這一思想的闡釋與推廣[10，11]，對計算思維的理解、普及和應用，進一步對計算機學科的教學發展起到了積極的推動作用。

計算思維并不是要求人類像計算機那樣思考，它只是人類求解問題的一條途徑。計算機擁有強大的計算能力，人類擁有了計算機，也就擁有了強大的計算能力，人類應該學會利用這種力量去解決更多的問題。當今社會計算機幾乎無處不在，計算機科學的出現不僅給人類帶來了便利，更重要的是計算的概念，它被人們用來求解問題、管理日常生活以及與他人進行交流和互動。計算思維無處不在，作為一個解決問題的有效工具，人人都應掌握，處處都會被使用。因此計算思維應當是當前計算機教育需要繼續重點研究的課題，而且應當有效地融入到我們的課程教學之中。

3 算法設計與分析教學中融入計算思維

有研究指出，計算思維作為一種工具，應當被所有學校的所有課堂教學采納。采用這個工具，自然會面臨以下幾個問題：

①人所固有的能力與局限性？計算機的計算能力與局限性？②問題解決的判定條件是什么？③問題到底有多復雜？④什么樣的技術能被應用于當前的問題求解或討論之中？⑤什么樣的計算策略更有利于當前問題的解決？

對于前兩個問題，計算理論課程做了較好的解釋[12]。后三個問題則應該是算法設計與分析課程重點解釋的內容。由于計算思維的重要性，結合多年算法設計與分析的教學經驗，筆者認為在算法設計與分析教學改革中，必須要將計算思維的培養融入到教學當中，在教學中不能局限于知識的傳授，而應該注重學生思維的培養，以提高學生的創新能力。具體在教學中應該注意以下幾點：

①算法教學應脫離具體的程序設計語言。算法獨立于具體的計算機和具體的程序設計語言。雖然算法的最終具體實現需要某一種具體的編程語言，例如C++、Java等，但這些編程語言只是一種實現工具。教學中應避免把算法課變成程序語言和程序設計的教學課程。對算法的描述應主要通過某種偽代碼、甚至可以是自然語言的形式。這樣的算法描述更為直觀、清晰、易懂，并使得教師的教學和學生學習專注于算法的概念和計算思維的培養，而不是具體應該如何編程實現某一段代碼。

②復雜性理論應作為教學重點內容。計算復雜性理論是理論計算機科學的分支學科，使用數學方法對計算中所需的各種資源的耗費作定量分析，并研究各類問題之間在計算復雜程度上的相互關系和基本性質，是算法分析的理論基礎。該理論回答了一個問題到底有多復雜，并指導選擇和設計解決問題的策略。而目前在教學過程中，由于教材通常將復雜性理論部分放在教材的最后章節，由于學時等因素，對復雜性理論的教學不夠重視。而復雜性理論是培養計算思維及對各種算法深刻理解的必備基礎。所以復雜性理論在教學中應該適當提前，并作為教學的重點內容。

③教學中應注重培養學生解決問題的思維能力。在各種算法的具體教學過程中，教師應該注重培養學生面對問題時的解決辦法。例如人們往往首先通過猜測，然后經過驗證、證明、分析、完善等過程，最終解決一個問題。這個過程也是人們探究真理的常見過程。在這個過程中培養學生科學的分析問題、邏輯推理、抽象概括能力，往往要比單純地講解某一種算法有更大的意義。邏輯推理是依據一定的邏輯規則，從已知項得出未知項，或用已知項來解釋未知項。抽象是抽出事物的本質屬性或特征的過程。概括是在抽象的基礎上，把抽取出來的那些本質屬性歸結在一起進行考察的思維方法。這些都是解決問題、探討概念、發現事物規律的重要基本工具，任何一個算法思想的產生都離不開推理、抽象和概括。對這些思維能力的訓練和培養是大學計算思維和通識教育的重要組成部分。

④算法思想應滲透在整個教學課程中。發展層次理論認為思維是多層次的，逐步發展的過程。發展層次的最高層次是嚴密性或公理性，算法教學時應有意識地朝著這一方向努力。很多算法的提出往往都基于某一個實際的、有趣的問題。在教學過程中可以為學生設置不同的問題情境，有意識的培養學生多角度思考問題的能力。現實生活中通常問題的解決方式都不是唯一的，在教學過程中應有意識的培養學生的算法思想，引導學生用不同的解決方法面對不同問題，甚至是同一個問題，從而加深學生對算法思想的理解，并在解決問題的過程中體會到算法思想的意義和作用，真正意識到算法思想的重要性。

4 結束語

計算思維已經和人們的生活和各種密不可分，甚至成為了一項重要的生存能力。當今的信息社會已經離不開計算機，如何培養具有計算思維的新型人才，變成了時代向教育事業提出的課題。國家要求高校必須重視并加強大學生創新能力的開發和培養，而計算思維中蘊含了強大的創新能力，培養計算思維能力的最高目標就是為了創新[8]。但是，目前還缺少如何培養學生計算思維的系統方法。針對這一問題，本文對算法設計與分析課程教學中如何融入計算思維做了一些討論。但這方面仍然需要很多非常艱巨的工作，例如算法設計與分析教學課程體系、教學內容、實踐體系、教材等方面還需要進一步的實踐與探索。希望我們的工作，為全國算法設計與分析課程教學的建設、改革探路，為國家培養拔尖創新人才做出貢獻。

參考文獻：

[1]Donald E. Knuth，計算機程序設計藝術[M].（3版，1-3卷，蘇運霖譯），國防工業出版社，2002.

[2]Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein，Introduction to Algorithms[M]，MIT Press，2001.

[3]許忠能，等.生物信息學[M].清華大學出版社，2015.

[4]夏定純.計算智能[M].科學出版社，2008.

[5]王星.大數據分析：方法和應用[M].清華大學出版社，2013.

[6]王曉東.算法設計與分析[M].清華大學出版社，2002.

[7]王移芝，魯凌云，周圍.以計算思維為航標 拓展計算機基礎課程改革的新思路[J].中國大學教學，2012-06-15.

[8]張靜，鄔恩杰.基于計算思維能力培養的《程序設計基礎》課程教學探討[J].軟件導刊，2015-08-15.

[9]王榮良.計算思維：一種新的學科思維方式[J].中國信息技術教育，2012-06-15.

[10]陳國良，董榮勝.計算思維的表述體系[J].中國大學教學，2013（12）：22-26.

[11]李廉.關于計算思維的特質性[J].中國大學教學，2014（11）：7-14.

[12]Harry R. Lewis，Christos H. Papadimitrious，Elements of the Theory of Computation[M]，Prentice-Hall，1997.