李 旭,趙秀巖,康 麗,沈 嵐,姚春龍
(大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 大連 116034)
計(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é)中真正落地是需要深入探討和解決的問題。
獨(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 泥濘城市
在實(shí)際生活中,圖的最小花費(fèi)生成樹問題在城市水管、天然氣管道規(guī)劃、最少通信線路鋪設(shè)以及物流公司的最小成本分析等領(lǐng)域有著廣泛的應(yīng)用,它也是算法設(shè)計(jì)中貪婪法的一個(gè)典型問題。以最小花費(fèi)問題為例說明面向思維培養(yǎng)的算法教學(xué)改革與實(shí)踐。
泥濘城市[2]案例描述如下:假設(shè)有一座城市還未鋪上道路,下雨之后要在這座城市中行走是一件非常困難的事情,地面被雨水浸濕,滿是泥濘,車輛紛紛陷入泥沼之中,人們的鞋子上沾滿了污泥。于是市長痛下決心,一定要在一些道路砌上石磚,但是錢必須用在刀刃上,他不想浪費(fèi)經(jīng)費(fèi),因此他下達(dá)了以下兩個(gè)要求:
(1)必須鋪設(shè)足夠的道路,讓每個(gè)人都能從家里沿著鋪好的道路到達(dá)別人的房子。
(2)所花費(fèi)的經(jīng)費(fèi)越少越好。在兩棟房子之間的道路上鋪上的石磚數(shù)代表了鋪路所需要的費(fèi)用。
通過設(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ù)判定算法的性能。
上述實(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í)積極性、主動性高漲。