面向計(jì)算思維培養(yǎng)的算法教學(xué)案例

李 旭，趙秀巖，康 麗，沈 嵐，姚春龍

（大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 大連 116034）

0 引 言

計(jì)算機(jī)基礎(chǔ)課程是高等院校非計(jì)算機(jī)專業(yè)學(xué)生的計(jì)算機(jī)入門課程，旨在培養(yǎng)學(xué)生利用計(jì)算機(jī)去獲取、分析、加工、處理、傳遞信息，解決實(shí)際問題的思路和能力，為將來使用計(jì)算機(jī)解決各自專業(yè)問題打下良好的基礎(chǔ)。然而，根據(jù)多年的授課情況看，學(xué)生在學(xué)完整門課程后雖然能夠了解和掌握大學(xué)計(jì)算機(jī)基礎(chǔ)課程的基本知識和技能，但是往往不能系統(tǒng)、全面地認(rèn)識和應(yīng)用這些知識，在后續(xù)的專業(yè)學(xué)習(xí)中遇到問題時(shí)，想不到用計(jì)算機(jī)知識去解決，或者想使用計(jì)算機(jī)卻不知道如何應(yīng)用學(xué)過的知識。因此，為了更好發(fā)揮計(jì)算機(jī)基礎(chǔ)課程在高校人才培養(yǎng)課程體系中的基礎(chǔ)支撐作用，培養(yǎng)出適合時(shí)代需要的具有創(chuàng)新思維和綜合應(yīng)用能力的各領(lǐng)域?qū)I(yè)人才，開展從“基于知識的技能傳授”向“基于應(yīng)用的思維能力培養(yǎng)”轉(zhuǎn)變的計(jì)算機(jī)基礎(chǔ)課程教學(xué)改革是必要且迫切的。

2006年3月，美國卡耐基·梅隆大學(xué)計(jì)算機(jī)科學(xué)系主任周以真首次提出并定義計(jì)算思維的概念，周教授認(rèn)為計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計(jì)、人類行為理解等涵蓋計(jì)算機(jī)科學(xué)廣度的一系列思維活動[1]。計(jì)算思維代表著一種普遍的認(rèn)識和一類普適的技能，在科學(xué)技術(shù)日新月異的信息時(shí)代，我們每一個(gè)人都應(yīng)該熱心于它的學(xué)習(xí)和運(yùn)用。然而目前對于計(jì)算思維能力培養(yǎng)的認(rèn)識，一定程度上還停留在對國外思想的吸收和消化階段。如何讓計(jì)算思維能力培養(yǎng)在課程教學(xué)中真正落地是需要深入探討和解決的問題。

1 傳統(tǒng)算法教學(xué)中存在的問題

獨(dú)立思考和解決問題的能力是高校人才培養(yǎng)的目標(biāo)之一。美國著名心理學(xué)和計(jì)算機(jī)專家西蒙指出：當(dāng)一個(gè)人接受一項(xiàng)任務(wù)，但又不知道如何去完成它時(shí)，他面臨的就是一個(gè)問題。西蒙將問題解決看做人類認(rèn)知的三類信息加工過程之一。為解決某一特定問題而設(shè)計(jì)的確定的有限的步驟稱為算法。算法設(shè)計(jì)與分析在培養(yǎng)學(xué)生獨(dú)立思考、分析問題和解決問題能力方面具有重要作用。

然而在傳統(tǒng)的算法教學(xué)中，教師往往將教學(xué)重點(diǎn)放在算法的解釋上，教學(xué)方法通常采用“介紹—舉例—演示”三部曲教學(xué)法。算法解釋生澀乏味、案例選取不接地氣沒有吸引力，學(xué)生感覺沒有實(shí)際應(yīng)用價(jià)值。這種授課方式下往往是老師講、學(xué)生聽，留給學(xué)生主動思考的空間少，久而久之使學(xué)生思維退化，導(dǎo)致懶學(xué)甚至厭學(xué)。

在面向思維培養(yǎng)的計(jì)算機(jī)基礎(chǔ)教學(xué)改革實(shí)施以來，我們充分認(rèn)識到算法教學(xué)對培養(yǎng)學(xué)生解決問題能力的重要性，認(rèn)識到傳統(tǒng)的算法教學(xué)之所以效果不佳其根本原因在于沒有掌握算法的本質(zhì)——問題的建模、分解、抽象和自動化，在問題求解過程中沒有充分調(diào)動學(xué)生的主觀能動性、激發(fā)學(xué)生的求知欲。

圖1 泥濘城市

2 面向思維培養(yǎng)的算法教學(xué)改革與實(shí)踐

在實(shí)際生活中，圖的最小花費(fèi)生成樹問題在城市水管、天然氣管道規(guī)劃、最少通信線路鋪設(shè)以及物流公司的最小成本分析等領(lǐng)域有著廣泛的應(yīng)用，它也是算法設(shè)計(jì)中貪婪法的一個(gè)典型問題。以最小花費(fèi)問題為例說明面向思維培養(yǎng)的算法教學(xué)改革與實(shí)踐。

2.1 通俗易懂的案例選取

泥濘城市[2]案例描述如下：假設(shè)有一座城市還未鋪上道路，下雨之后要在這座城市中行走是一件非常困難的事情，地面被雨水浸濕，滿是泥濘，車輛紛紛陷入泥沼之中，人們的鞋子上沾滿了污泥。于是市長痛下決心，一定要在一些道路砌上石磚，但是錢必須用在刀刃上，他不想浪費(fèi)經(jīng)費(fèi)，因此他下達(dá)了以下兩個(gè)要求：

（1）必須鋪設(shè)足夠的道路，讓每個(gè)人都能從家里沿著鋪好的道路到達(dá)別人的房子。

（2）所花費(fèi)的經(jīng)費(fèi)越少越好。在兩棟房子之間的道路上鋪上的石磚數(shù)代表了鋪路所需要的費(fèi)用。

2.2 以問題為驅(qū)動引導(dǎo)學(xué)生主動思考、自主解決問題

通過設(shè)計(jì)一連串問題，問題之間有層次漸進(jìn)關(guān)系，逐步引導(dǎo)學(xué)生深入思考、歸納總結(jié)，進(jìn)而找出并描述解決問題的步驟。對于泥濘城市案例，設(shè)計(jì)的問題如下：

（1）設(shè)想這座小城僅有5棟房子和7條路（圖1）。為了連接所有的房子，且要使用最少的石磚，房子之間的每個(gè)方塊代表需在此鋪上一塊石磚，哪些道路必須鋪上石磚？

（2）將這5棟房子連接起來，至少需要鋪幾條路？

（3）如果已經(jīng)選擇在房子A、B和B、C之間分別鋪設(shè)石磚，直接從房子A到房子C的道路還要不要鋪設(shè)？

（4）如果添加一條道路，使設(shè)計(jì)方案中產(chǎn)生了一個(gè)“循環(huán)路線”，即從一條路離開一棟房子后還能走另外一條路回到這棟房子，這條道路還要不要添加？

（5）鋪設(shè)方法是唯一的么？你能想到的使用最少石磚數(shù)的鋪法有幾種？

（6）請用自然語言把你鋪設(shè)最少石磚的方法描述出來。

（7）如果用圓圈表示地圖中的房子，用線條和數(shù)字表示地圖中的道路，計(jì)算機(jī)科學(xué)家們稱這種結(jié)構(gòu)為圖。在圖中，圓圈代表的房子稱為節(jié)點(diǎn)，節(jié)點(diǎn)之間的線條代表泥濘的道路，每條道路的長度用線條旁的數(shù)字標(biāo)明。請畫出與上述地圖相對應(yīng)的圖結(jié)構(gòu)。這種將房子縮寫成節(jié)點(diǎn)、道路表示為線條和數(shù)字的過程稱為問題建模。

（8）在圖中，如果從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)有路徑相連，我們稱這兩個(gè)頂點(diǎn)是連通的。如果圖中任意兩點(diǎn)都是連通的，該圖被稱為連通圖。那么上述求地圖中連接所有房子的最少石磚數(shù)是不是已經(jīng)轉(zhuǎn)化為求連通圖的總長最短的路徑問題？在計(jì)算機(jī)科學(xué)中該類問題被定義為最小生成樹問題。該問題之所以被稱為“最小”是因?yàn)樗髶碛凶钚〉氖u總數(shù)，“生成”代表了每一棟房子都和另外一棟連接起來，最終得到的正確方案的形狀看起來則像一棵“樹”——如果你從任一棟房子出發(fā)，都會有一條或多條道路從這里“分叉”出去，而這每一條分支稍后又會有其他的分支，但是兩條分支永遠(yuǎn)無法回指或相交，如果你讓他們相交了，說明將有兩條道路能通往同一棟房子，則其中的一條必是浪費(fèi)石磚的選擇。

（9）如圖2所示的大一點(diǎn)城市的布局圖，請畫出與布局圖相對應(yīng)的圖結(jié)構(gòu)。

圖2 大一點(diǎn)的泥濘城市

（10）是否能應(yīng)用剛才設(shè)計(jì)出的最少石磚數(shù)算法，找出大一點(diǎn)城市的石磚鋪設(shè)方法？這個(gè)算法對于更大規(guī)模的相同問題是否依然有效？

（11）請用流程圖描述鋪設(shè)最少石磚數(shù)的算法，即用流程圖描述最小生成樹算法。

（12）你是否還能找出其他方法解決該問題？請用流程圖把解決步驟描述出來。

（13）解決最小花費(fèi)問題，上述算法的執(zhí)行步驟一樣嗎？哪種方法更優(yōu)，請說明原因。

對于問題（1）這樣小規(guī)模的最小花費(fèi)問題，學(xué)生通常很快就能得出最少需鋪設(shè)7塊石磚的最優(yōu)方案，也會回答出連接5棟房子，至少需要鋪設(shè)4條路。問題（3）和問題（4）能夠讓學(xué)生充分思考并明確設(shè)計(jì)方案中一定不能存在循環(huán)線路。通過問題（5）和（6）的引導(dǎo)和提問，學(xué)生通常能自主歸納總結(jié)出以下兩種鋪設(shè)最少石磚的方法：①從一張空白地圖開始，按照路徑長度從小到大添加道路，逐步增加石磚直到全部房子都被連接起來，注意增加路徑時(shí)不能將兩個(gè)已經(jīng)連接的房子再用其他道路連接起來，產(chǎn)生“循環(huán)”線路。當(dāng)路徑長度相同時(shí)，改變添加路徑的順序，會產(chǎn)生不同的最終布局，但是最后的結(jié)果依然能保持需要石磚的總數(shù)最少。②從一個(gè)房子開始，遍歷與該房子或已連接房子相連接的其他房子，使用連接路徑中的最小長度添加道路，逐步增加石磚直到全部房子都被連接起來，注意增加路徑時(shí)不能產(chǎn)生循環(huán)線路。

問題（7）引導(dǎo)學(xué)生通過抽象、簡化建立能刻畫該類實(shí)際問題的一般模型，如圖3所示，使學(xué)生水到渠成地得出問題（8）的結(jié)論：該問題即為求解連通圖的總長最短的路徑問題。

圖3 問題建模

問題（9）和（10）引導(dǎo)學(xué)生驗(yàn)證算法的正確性和有效性，歸納總結(jié)出求解該類問題的普適算法。問題（11）和（12）要求學(xué)生用流程圖準(zhǔn)確、規(guī)范地描述出算法的步驟，自主“實(shí)現(xiàn)”計(jì)算機(jī)中經(jīng)典的Kruskal算法或Prim算法。問題（13）引導(dǎo)學(xué)生通過比較執(zhí)行步數(shù)判定算法的性能。

3 結(jié) 語

上述實(shí)例展示了面向計(jì)算思維培養(yǎng)的算法教學(xué)改革，在不改變教學(xué)大綱和內(nèi)容的基礎(chǔ)上，通過改進(jìn)教學(xué)方法，有意識地將與思維培養(yǎng)相關(guān)的問題分解、抽象和自動化的方法自然地融入到教學(xué)中，培養(yǎng)了學(xué)生獨(dú)立思考、主動參與、實(shí)際探究的能力。

精心設(shè)計(jì)的教學(xué)案例，以及學(xué)生與老師“風(fēng)云際會”的互動過程大大增加了學(xué)生對知識的興趣，開啟他們探索知識的航程。通過對我校非計(jì)算機(jī)專業(yè)開展面向思維的算法教學(xué)改革實(shí)踐，學(xué)生的課堂活躍度大大提升，學(xué)習(xí)積極性、主動性高漲。