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

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

0 引 言

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

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

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

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

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

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

圖1 泥濘城市

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

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

2.1 通俗易懂的案例選取

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

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

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

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

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

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

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

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

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

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

（6）請(qǐng)用自然語(yǔ)言把你鋪設(shè)最少石磚的方法描述出來(lái)。

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

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

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

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

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

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

（12）你是否還能找出其他方法解決該問(wèn)題？請(qǐng)用流程圖把解決步驟描述出來(lái)。

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

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

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

圖3 問(wèn)題建模

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

3 結(jié) 語(yǔ)

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

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