在算法設(shè)計與分析課程教學(xué)中融入計算思維

張遠平

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

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.

關(guān)鍵詞： 算法設(shè)計與分析；計算思維；教學(xué)改革

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

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

0 引言

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

1 算法設(shè)計與分析

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

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

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

由于算法設(shè)計與分析在計算機學(xué)科中的重要地位，其基本內(nèi)容已經(jīng)成為計算機相關(guān)學(xué)科的一門專業(yè)核心必修課程。算法設(shè)計與分析課程的教學(xué)方式、內(nèi)容和質(zhì)量，必須能夠確保培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)習(xí)效果，以便提高學(xué)生專業(yè)能力和綜合能力的培養(yǎng)，為學(xué)生高水平高層次應(yīng)用和發(fā)展提供保障。

2 計算思維

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

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

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

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

3 算法設(shè)計與分析教學(xué)中融入計算思維

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻：

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

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

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

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

[5]王星.大數(shù)據(jù)分析：方法和應(yīng)用[M].清華大學(xué)出版社，2013.

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

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

[8]張靜，鄔恩杰.基于計算思維能力培養(yǎng)的《程序設(shè)計基礎(chǔ)》課程教學(xué)探討[J].軟件導(dǎo)刊，2015-08-15.

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

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

[11]李廉.關(guān)于計算思維的特質(zhì)性[J].中國大學(xué)教學(xué)，2014（11）：7-14.

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