馬小虎

摘 要：介紹了新生研討課《計(jì)算思維》的主要教學(xué)內(nèi)容，給出了一些典型實(shí)例，探討了如何講授好該課程的一些教學(xué)方法。

關(guān)鍵詞：計(jì)算思維；教學(xué)內(nèi)容；典型實(shí)例；教學(xué)方法

1 教學(xué)內(nèi)容

《計(jì)算思維》課程是我們近年來給一年級(jí)新生開設(shè)的一門新生研討課，在實(shí)際講授該課程時(shí)我們采用了由唐培和、徐奕奕和王日鳳編著的《計(jì)算思維導(dǎo)論》作為參考教材。該參考教材主要教學(xué)內(nèi)容包括七章，這七章內(nèi)容可概括如下[1]：

第一章主要介紹計(jì)算思維的基本概念，學(xué)習(xí)計(jì)算思維的目的和意義，國(guó)內(nèi)外研究計(jì)算思維的基本情況，計(jì)算思維的學(xué)習(xí)方法。

第二章主要討論狹義計(jì)算思維的理論與技術(shù)基礎(chǔ)。其主要內(nèi)容包括：數(shù)據(jù)與符號(hào)在機(jī)器內(nèi)部是如何表示的，圖靈機(jī)及其計(jì)算思想，馮諾依曼機(jī)及其工作原理，非傳統(tǒng)計(jì)算方法與技術(shù)，還介紹了可計(jì)算性問題與計(jì)算復(fù)雜性問題。

第三章專門討論計(jì)算思維的邏輯基礎(chǔ)，主要介紹了布爾代數(shù)、命題邏輯、謂詞邏輯以及邏輯演算。

第四章重點(diǎn)介紹了計(jì)算思維的方法學(xué)。其主要內(nèi)容包括：?jiǎn)栴}求解過程、數(shù)學(xué)模型、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、程序設(shè)計(jì)方法論，分析與討論了時(shí)空概念、抽象、局部化與信息隱藏、精確、近似與模糊、折中與中庸之道以及問題描述方法。

第五章重點(diǎn)介紹了計(jì)算思維的算法基礎(chǔ)。這一章首先介紹算法的基本概念、算法的性質(zhì)、算法的描述、算法的簡(jiǎn)單分析方法等，然后介紹算法設(shè)計(jì)的基本思想與方法，最后介紹了幾個(gè)常用的經(jīng)典算法。

第六章討論了程序設(shè)計(jì)中的特定思維。主要內(nèi)容包括：數(shù)據(jù)的類型與本質(zhì)、變量的特定含義、有窮與無窮、程序的基本控制結(jié)構(gòu)、問題求解的本質(zhì)過程、效率與可讀性、程序的構(gòu)造特性等內(nèi)容。

第七章主要介紹了計(jì)算思維在其他學(xué)科中的應(yīng)用。比如：有限元分析與計(jì)算、數(shù)值天氣預(yù)報(bào)、蒙特卡洛方法等內(nèi)容。

2 典型實(shí)例

計(jì)算思維課程中具有大量的經(jīng)典案例。下面以經(jīng)典的遞歸算法和圖論方法給出兩個(gè)實(shí)例進(jìn)行說明如下：

例1：漢諾塔問題

題目：把A桿上的全部64個(gè)金盤借助B桿全部移到C桿上，并仍保持原有順序疊好。操作規(guī)則：每次只能移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

算法分析：

1）以C桿作為中介桿，將A桿n-1個(gè)金盤移動(dòng)到B桿

2）將A桿中唯一剩下的一個(gè)金盤移動(dòng)到C桿（此時(shí)A桿為空桿，取代C桿地位）

3）以A桿為中介，將B桿n-1個(gè)金盤移動(dòng)到C桿

從以上分析可以看出漢諾塔問題是一個(gè)典型的遞歸問題。

當(dāng)n=1時(shí)，需要移動(dòng)2^1-1=1次盤子，當(dāng)n=2時(shí)，需要移動(dòng)2^2-1=3次盤子，當(dāng)n=3時(shí)，需要移動(dòng)2^3-1=7次盤子，當(dāng)n=64時(shí)，則需要移動(dòng)2^64-1=18446744073709551615次盤子，假設(shè)計(jì)算機(jī)每秒可移動(dòng)1000萬個(gè)盤子，那么也需要花費(fèi)大約58490年的時(shí)間。

例2：過河問題

題目：農(nóng)夫需要把狼、羊、菜和自己運(yùn)到河對(duì)岸去，只有農(nóng)夫能夠劃船，除農(nóng)夫之外每次只能運(yùn)一種東西，如果沒有農(nóng)夫看著，羊會(huì)偷吃菜，狼會(huì)吃羊。請(qǐng)考慮一種方法，讓農(nóng)夫能夠安全地安排這些東西和他自己過河。

算法分析：設(shè)一個(gè)四維向量（a，b，c，d）。令1表示在河的這邊，0表示在河的另一邊。a代表人，b代表狼，c代表羊，d代表菜。則人狼羊菜在河這一邊的狀態(tài)可用分量為1和0的四維向量表示。排除不可能的狀況，比如狼和羊在一邊（0，1，1，0），羊和菜在一邊（0，0，1，1）。則由窮舉法可知，最后可得到十個(gè)不同的四維向量。（1，1，1，1）為初始狀態(tài)，（0，0，0，0）為結(jié)果狀態(tài)。人為變化的主體，所以相鄰兩個(gè)向量第一個(gè)分量不同。

由圖可知，一共有兩種方案，兩種方案都需要七次才能把所有東西運(yùn)過河。

方法一（紅線）：步驟1將羊帶到對(duì)岸；步驟2人獨(dú)自回去；步驟3將菜帶到對(duì)岸；步驟4人將羊帶回；步驟5將狼帶到對(duì)岸；步驟6人獨(dú)自回去；步驟7將羊帶到對(duì)岸

方法二（黑線）：步驟1將羊帶到對(duì)岸；步驟2人獨(dú)自回去；步驟3將狼帶到對(duì)岸；步驟4人將羊帶回；步驟5將菜帶到對(duì)岸；步驟6人獨(dú)自回去；步驟7將羊帶到對(duì)岸可以推廣到更加復(fù)雜的情況。這就是經(jīng)典算法中的圖論方法。

3 教學(xué)方法

《計(jì)算思維》課程是我們?yōu)橐荒昙?jí)新生開設(shè)的研討課，選該課程的同學(xué)來自各個(gè)學(xué)院的不同專業(yè)，學(xué)生們一般沒有什么計(jì)算機(jī)基礎(chǔ)知識(shí)，更沒有編程基礎(chǔ)，所以在講授該課程時(shí)，講的是解決實(shí)際問題的思想和方法，而不是程序設(shè)計(jì)。該課程應(yīng)該注重培養(yǎng)學(xué)生的思想、方法、意識(shí)、興趣和能力，二不是灌輸一大堆概念與知識(shí)。通常由主講老師先講授第一章與第五章內(nèi)容，然后，由學(xué)生分組完成其他章節(jié)的演講，該新生研討課學(xué)校規(guī)定學(xué)生總?cè)藬?shù)限定在30人之內(nèi)，以便每個(gè)學(xué)生都至少有一次機(jī)會(huì)上臺(tái)演講一個(gè)主題，事先認(rèn)真做好PPT，講完以后，由主講老師負(fù)責(zé)點(diǎn)評(píng)。通過這種師生互動(dòng)、學(xué)生為主角的方式，同學(xué)們的積極性得到了充分的調(diào)動(dòng)，有些同學(xué)還查閱了大量的教材之外的內(nèi)容，做出了非常漂亮的PPT，演講得也非常熟練、非常成功。

4 結(jié)束語

《計(jì)算思維》課程是一門新開設(shè)的新生研討課，我們還在不斷探索、實(shí)踐中，其教學(xué)內(nèi)容與教學(xué)方式還在不斷完善之中。在這里僅對(duì)我們已經(jīng)開展的一些實(shí)踐工作做一些初步總結(jié)，以便能跟同行們一起交流、一起提高。

參考文獻(xiàn)

[1]唐培和，徐奕奕，王日鳳編著.計(jì)算思維導(dǎo)論[M].桂林：廣西師范大學(xué)出版社，2012.