前言:想要寫出一篇引人入勝的文章?我們特意為您整理了發散思維在計算機算法教學的重要性范文,希望能給你帶來靈感和參考,敬請閱讀。
摘要:分析計算機算法的特點,論證發散思維在計算機算法教與學中的重要性,并通過實例,從想象力和發散思維的角度,探討計算機算法的教與學以及如何培養算法構思中的發散思維能力。
關鍵詞:計算機算法;發散思維;構思能力;教學
0引言
在計算機算法領域,要想取得顯著的原創成果,必須具備如下3種能力:①想象力,在千頭萬緒的各種可能性中,若沒有豐富的想象力,就不可能找到有效的甚至奇妙的方法;②敏銳的邏輯領悟力,能敏銳地把握某種想法與所要解決問題之間的內在邏輯聯系;③深入的思路能力,也就是沿一條長長的思維脈絡深入思考下去的能力。這3種能力缺一不可。如何取得?天分在這里有很大的作用,但在平時思考算法問題、在讀懂他人算法的過程中有意識地加以培訓,也是有效途徑。計算機科學專業與其他專業有顯著的不同點,這些不同點導致了在教與學方面的某些根本不同。其他專業大都由這兩點主導,一是著重于對概念原理的理解和掌握,二是長年知識經驗的積累非常重要。這兩點在計算機科學專業當然也具有意義,但不擁有主導意義。計算機科學專業最核心的方面,一是思維方式和觀念的更新,二是思維能力的強大。一般說來,側重于概念和原理理解的教學較容易把握,而在思維方式思維能力上,要想取得顯著的教學效果則有難度,尤其是在國內高校課程多課時緊的情況下[1]。例如,計算機算法課程的核心就是思維能力的培訓,缺少思維能力,概念原理再怎么掌握都沒有實質價值。同時,計算機算法課程也是計算機科學的最核心課程。人工智能的發展依賴于思維方式和觀念的更新,而無論什么樣的思維方式和觀念,都必須以思維能力為基礎,故人工智能的發展也必須建立在強大的算法功力上。計算機算法有一個不同于其他課程的重要特點——需要一連串的思維,這一連串的思維由許多關鍵點構成,這些關鍵點彼此依序而行又動態關聯。思路運行的任一時刻,所有關鍵點都必須同時印在腦海里,且必須同時都有透徹的理解,并在需要的時候可以將此時的思路與前面的任何關鍵點關聯起來[2]。任何疏忽遺漏或一知半解都會導致整個思路的失敗。這正是復雜算法難以理解掌握的根本原因。相較于其他課程,計算機算法課要想取得顯著的教學效果,其難度要大得多。
1發散思維和計算機算法簡述
心理學研究認為發散思維(又稱輻射思維或擴散思維)是指大腦在思維時呈現的一種擴散狀態的思維模式,它表現為思維視野廣闊,思維呈現出多維發散狀。如“一題多解”“一事多寫”“一物多用”等方式。不少心理學家認為,發散思維是創造性思維的最主要特點,是測定創造力的主要標志之一。具體到計算機算法中,發散思維需要具備兩點,一是想象力,二是多角度。按通常的思路難以想到的方法和解決問題的途徑,若能有效運用發散思維,就可能迎刃而解。發散思維有三大特性:流暢性、變通性、獨特性。流暢性反映的是發散思維的速度和數量特征,具體到計算機算法中,就是掌控一連串長的思路的能力,這個能力的取得相當有難度,需要長時間培訓。變通性就是克服人們頭腦中某種僵化的思維框架,按照某一新的方向來思索問題的過程,表現出多面性和多樣性。在計算機算法中,變通性天分在這方面具有重要作用,后天的刻苦訓練也有顯著效果,二者必須結合。獨特性是指人們在發散思維中做出不同尋常的異于他人的新奇反應的能力。獨特性是發散思維的最高目標。在計算機算法中,獨特性是指獨立解決前人所不能解決超難問題的能力,這當然也是算法的最高境界。筆者主要著重于前兩點。事實上,計算機算法并無具體的定律規則可循,針對不同的問題,各種可能的算法千差萬別,因而算法課程教學要想取得成效也是相當的不易。先驅們創造了許多算法(針對具體問題)和算法思維方式(通用性不具體針對),但遇到新問題根本不可能照搬照套,教師只是將一些概念方法灌輸給學生是沒有用的,必須使學生能運用這些概念方法解決問題,其中想象力和思維能力的培養尤為重要。這些不僅需要教師在教學中通過實例培訓學生這方面的能力,還要有意識地引導、點撥學生,使他們能在自己的學習過程中有意識地訓練這種能力。作為學生,要想得到強大的算法功力,僅靠教師和課堂遠遠不夠,還需要自學。集多年開發和教學的雙重經驗,筆者在長年對計算機算法進行精心研究的基礎上,揭示了算法教與學中的一些關鍵技巧,遵循這些技巧,不僅能大大提高算法的教學效果,同時也為提高軟件開發人員復雜思路的構思能力提供了切實有效的途徑。此外,注意從趣味性吸引和多種不同的方法思路的角度,來講解計算機算法問題,也可以達到消除算法枯燥乏味的目的。
2史上重大的發散思維成果剖析
發散思維就是創新,就是創造性想象力,就是想別人想不到、想別人所不敢想。當然,發散思維必須以堅實的知識基礎和邏輯思維基礎做后盾,方法要切實可行,而不是漫無邊際的遐想。1)人工智能圍棋。眾所周知,人工智能早就能戰勝國際象棋特級大師,但圍棋由于變化超大,人工智能圍棋進展一直不大,多年一直停留在業余棋手的水平。近兩年才獲得了根本的突破,不僅接連戰勝頂尖世界冠軍,而且很快將人類頂尖棋手甩開了很長的距離。能做到這些,正是由于思維方式的根本性改變,也就是發散思維的成果。如在蒙特卡羅樹搜索算法上思維方式的改變,將機器的學習過程從學習人類棋譜開始的框框中解脫出來,摒棄了人類棋譜的影響,通過機器人從零水平開始的對弈來實現自我提高。2)伽羅華群論。在科學史上在運用發散思維尤其是獨特性的發散思維方面,最經典的例子,當屬法國伽羅華發明群倫,這是獨特性發散思維的光輝頂點。在高次方程的根式解上,前人一直將途經放在如何直接開發出高次方程的求根公式上,經過較長歷史時期的探索,二次、三次乃至四次方程的求根公式先后被攻克,但到了五次方程,一直未有進展。伽羅華另辟蹊徑,他不是著眼于如何去找到求根公式,而是運用對稱性和排列組合原理發明了一套全新的理論,即群論,用這套理論去間接判斷方程是否可能具有根式解,取得了前所未有的成功。3)質數判定。在很長的時期,判斷一個數是否是質數,一直被認為是困難的,就是因為沒有多項式時間算法。直到2002年,印度3位科學家M.Agrawal、N.Kayal以及N.Saxena發明了AKS質數測試算法,可以絕對準確地快速判斷一個數是否質數。檢查一個正整數N是否為質數,最簡單的方法就是試除法,將該數N用小于等于根號N的所有素數去試除,若均無法整除,N則為素數。印度科學家從根本上突破了這種思維限制。他們的算法最終得到了學界的認可,它是正確和完整的多項式時間算法。他們的成功表明,在算法領域,發散思維能導致無限的可能性。4)張益唐陳景潤。發散思維的多角度性有兩個方面,一是在同一個方法上深挖下去,另一個是發掘出一個全新的完全不同的方法。一個是靈感,一個是思維的深度和廣度。計算機算法實力需要的也是這方面的功力。許多高難度數學問題的解決,與計算機算法的思維方式是一致的,甚至就是一種算法的設計開發過程。例如,陳景潤完成哥德巴赫猜想的1+2,運用的一直是前人所用到的篩法,但陳景潤在深度和廣度上進行了發掘,取得了前人所未能取得的成就。據部分數學家認為,陳景潤已經將篩法的深度和廣度開發到了極致,再無可能更進一步了。這個例子說明了發散思維所能帶來的無限可能性。
3發散思維算法實例研究
1)Hamilton環算法。Hamilton環為著名的NP完全問題,因而在計算機算法研究中占據重要地位。學界對該算法的研究主要是基于Posa提出的旋轉—延展法。長期以來,對該問題算法的大量研究,都是以Posa的旋轉—延展法為基礎。該方法的基本要點是:對于n個節點的無向圖,每次選取1個節點,試圖構成Hamilton環。比如首先選取節點a,再選取節點b,b與a有一條邊相連。然后在剩余節點中找到1個與b相連的節點……以此類推,可以得到1個節點串abcd...efghij,該節點串中相鄰兩節點均有1條邊相連。再在剩余節點中找到1個與節點j相連的節點;若找不到這樣的節點,但剩余節點中有節點k與節點c相連,而節點j與b相連。此時將節點串的一部分旋轉一下,得到abjihgfe...dc,然后加上k得到abjihgfe...dck,稱此方法為旋轉。若是k與c相連,但j與a相連,可將原節點串ja相連,斷開bc,得到bajihgfe...dc,然后加上k,得到bajihgfe...dck,稱此方法為延展。不難發現,這個旋轉—延展法很死板,只能在1個固定點上進行旋轉和延展,當圖形邊數稀少時,旋轉和延展的條件很難滿足。盡管多年來對此問題算法的研究有很大進展,但對于稀疏圖形,成功率一直不理想。筆者在長年研究的基礎上,運用發散思維,從根本上改變了Posa的方法。鑒于Posa的方法是每次加進1個節點,旋轉和延展都在固定的端點進行,從而使運算受到了極大的限制。筆者的方法是,一次性全部加入n個節點,構成1個環,相鄰節點可能沒有邊相連,也就是該環有斷點,稱這樣的環為虛環。每次操作從某斷點切掉一截,插入到環的另一個地方。切和插的原則是,盡可能使斷點數變小,且在切和插之前就可以進行旋轉和延展。大量實驗表明,本方法大大提高了計算效率[3]。根據算法編制了程序,計算圖形是隨機產生的,筆者盡可能產生難算的稀疏圖形,實驗數據見表1(computer:HPPC,CPU:Intel1G,Memory:1G)同樣,成功計算國際著名網站上的圖形[4],計算時間與表格中數據相當。得到的結果與給出的答案不同,因為每個圖形有多個不同的Hamilton環。2)經典的二叉樹數據結構和算法題。國內外計算機專業數據結構和算法的經典教材,幾乎都要講到這樣一個算法題,或作為習題,或作為例題[5]:對于任何一棵二叉樹T,如果其葉子節點數為n0,度數為2的節點數為n2,則n0=n2+1。這是一個典型的數據結構和算法類的問題,盡管屬于基礎簡單類別,但相當具有代表性,大量本專業的學生甚至老師,都不能清晰透徹地解決該問題。下面是教科書上關于此題的經典證法。證明:設n為二叉樹T中的節點總數,n1為度數為1的節點數,因為二叉樹中所有節點的度數均小于或等于2,故n=n0+n1+n2。另一方面,除了根節點外,其余節點都有1個分支進入,而分支都是由度數為1或度數為2的節點射出的,則n=n1+2n2+1,故n0+n1+n2=n1+2n2+1,解得n0=n2+1。當筆者講到這個問題時,總是首先讓學生自己看,爭取自己能看懂。這也是講解較有深度和難度的算法問題的基本方法:學生首先必須自己預習,才可能有收獲。然而,此題雖然簡單,但學生往往普遍反映看不懂。于是,筆者將本題目進行了如下修改:假設孔子的所有男性后代,包括孔子本人,要么有1個兒子,要么2個兒子,要么1個兒子也沒有。假設有1個兒子的人數為10萬,2個兒子的人數為20萬,求1個兒子也沒有的孔子男性后代的人數。不用說,沒學生能做出。于是筆者進一步講解道:這相當于由孔子開始的1棵二叉樹,根節點是孔子。在這棵樹上,只有孔子一人不做兒子,因為孔子的父親不在這棵樹上,其他每個人都要做兒子。于是所有人的總數等于兒子的總數加1,即n0+n1+n2=n1+2n2+1。此等式左邊是所有人的總數,右邊是兒子的總數加1,解后得n0=n2+1。學生終于明白了。請注意此時并不意味學生就真的透徹搞懂了該問題,稍微變換一下此題目,學生還是不會。這也是算法這門課的根本特點,稍有難度的算法很難讓學生順暢接受。此題非常有趣,深入挖掘此題極其有利于學生數據結構和算法功力的提高和加深理解。筆者總結了該問題4種完全不同的解法,每種解法都能以不同方式加強學生對數據結構和算法的理解。解法1:兒子總數加1法。也就是上面所述的方法。解法2:滿樹法。任何1個二叉樹,都是通過切掉一些滿二叉樹的后代所得到。分兩種情況:①切掉的滿二叉樹的根節點是獨子,②切掉的滿二叉樹的根有1個親兄弟。我們很容易得到,對于1個滿二叉樹,n0=n2+1。對第1種情況,由于切掉的滿二叉樹是獨子,故切掉后,它的父節點由原來的度數1變為度數0,也就是葉節點的個數增加了1個。切掉的滿二叉樹的葉節點的個數比度數為2的節點的個數多1個,正好抵消,也就是相當于:每切掉1個滿二叉樹,葉節點與度數為2的節點減少的數目正好一樣,也就是說他不影響兩者之間的大小差關系。對第2種情況,由于切掉的滿二叉樹有一兄弟,故切掉后,他們的父節點由原來的度數2變為度數1,也就是度數為2的節點的個數減少了1個。切掉的滿二叉樹的葉節點的個數比度數為2的節點的個數多1個,正好抵消,同樣也就是相當于:每切掉1個滿二叉樹,葉節點與度數為2的節點減少的數目正好一樣,同樣不影響兩者之間的大小差關系。由于最初的滿二叉樹n0=n2+1,故最后剩下的那棵樹亦滿足n0=n2+1,得證。解法3:頭胎二胎法。我們用一步一步增加節點的方法形成二叉樹,每次增加1個節點。最初只有1個根節點。因為這個根節點的度數為0,顯然,此時n0=n2+1。以后每加1個節點,相當于某個節點添了個兒子。有2種類型的兒子:頭胎和二胎。若是頭胎,相當于父節點的度數由0變為1,也就是減少了1個度數為0的節點,但新添的兒子正好度數為0,故n0和n2都沒有改變。若是二胎,相當于度數為2的節點增加了1個,而度數為0的節點也增加了1個,就是新添的兒子度數為0,故兩者的大小差依然不變。從而n0=n2+1一直保持。解法4:借兒子法。請注意借兒子法,首先必須證明,只要存在有節點擁有2個兒子,那就總可以將兒子借出去。因為,這是一棵樹,無論如何,它總有葉子節點,從而總有能借兒子的節點。將有2個兒子的節點的兒子借1個給某葉節點,注意這時候可能會連同該兒子的后代也就是那個子樹一起借出。每借出1個,相當于度數為2的節點(借出者)減少了1個,而度數為0的節點(借入者)也減少了1個。從而兩者之差沒有改變。到最后,因為只剩下度數為1的節點和葉節點,很容易得到此時n0=1,而n2=0,于是n0=n2+1。因為兩者之差一直沒有改變,故最初的關系也是n0=n2+1。毫無疑問,對于此問題,若是學生自己能想出或透徹理解這4種解法,對于計算機算法所必需的想象力和縝密的思維力,都是極大的鍛煉和提高。
4結語
計算機軟件專業的核心是復雜思路的構思能力。這一能力從根本上體現在對算法的理解和設計上,因此,算法教學在計算機軟件專業中起著舉足輕重的作用,同時具備強大的算法功力亦是軟件開發人員最重要的素質。然而,算法課難講難學,無論是教學和學習,都難有固定的規則可循。筆者在多年實踐研究的基礎上,從發散思維的角度論述了如何鍛煉和培訓這方面的實力,既可供教學時參考,亦可為軟件開發人員培訓提供借鑒。
作者:杜立智 單位:武漢科技大學