【李家同】我的教育專欄(361)為何我們要注意演算法?
張貼日期:2022/5/26
資訊教育中,演算法應該是相當基礎而且重要的。如果我們要利用電腦,就需要寫程式,但是針對一個問題,可以有不同的方法來解決。假設我們有以下17個數字,1、5、11、17、23、27、32、36、41、46、49、52、57、59、63、66、73。假設我們要問,這17個數字中有沒有59,最簡單的方法就是從第一個數字看起,直到找到59為止。如果用這個方法,以這個例子而言,需要比較14次之多。
因為我們知道這17個數字是已經排序好的,所以我們有一個聰明的方法,那就是從第8個數字36開始比較,59大於36,所以我們可以忽略掉前面7個數字。然後我們看第12個數字52,59大於52,所以我們只要看比52大的數字。我們比較第15個數字63,發現59小於63,我們就回頭去找大於52而小於63的數字,它們只有兩個,所以我們就找到了。用這種方法,4次就找到了。
這是資訊系學生一定會用的一種演算法,演算法其實就是教軟體工程師如何設計好的程式,可以比較快解決問題。
再舉一個例子,有一種排序的方法叫做bubble sort,如果要將500萬個數字排序,這種方法需要8.6小時。如果用quick sort,只要0.41秒。我們可以說quick sort快了7萬6千倍左右。
也許有人會說,我們要很快地得到答案,只要買一個非常快的電腦就可以了。但非常快的電腦,必定非常貴,而且一定比較耗電。我們要知道,耗電是一個嚴重的事情,假如我們的手機是非常耗電的,每天都要充電,對個人以及國家都不是好事。
好的演算法可以使我們用比較便宜而又省電的電腦。要知道,即使使用非常快的電腦,如果用了一個很不好的演算法,其結果也是不會好的。
大家都在使用Google,可以想見的是,Google公司必須要用非常快速的字串比對演算法。有很多學者從事字串比對演算法的研究,有好幾位都在Google工作,可見得演算法是相當重要的。如果我們要寫的程式不是普通的程式,不能不懂演算法。
要學好演算法,同學們一定要有邏輯思考的能力。我們幾乎可以說,演算法本身是一種數學,因為要證明這個演算法有用,是必須要非常嚴謹的。在數學上,我們一直要證明某一個定理,在演算法的研究上,我們要很嚴謹地證明這個演算法是有效的。
研讀演算法有一個好處,那就是使得我們的學生比較會抽象地思考,而且會比較嚴謹。
演算法有一個功能。假設一位老師想出一個方法來解決問題,他請一位同學來寫這個程式。這位老師可以將他的想法寫成一個演算法,學生看到了這個演算法以後,可以寫出程式,而這個程式是完全符合老師要求的。因此,所有演算法裡面的名詞都要非常精確,絕對不可以含糊其辭。如果演算法寫得不夠精確,這個演算法是沒有用的。
學會演算法的同學因此養成說話非常精確的習慣。如果在鄉間迷路了,GPS又失靈,最好找一位學過演算法的人問路。通常他們所給的指令都相當精確,按照他們的指令去走,一定會到達目的地,絕對不會走一個河邊,車旁又有一頭大牛,好像很不歡迎你的到來,使你進退兩難。講話精確並不是容易的事,很多人沒有這個能力。學習演算法,絕對有這樣的好處。
演算法也有難易之分,對很多學生而言,我們可以教他們最基本的演算法,這些基本的演算法就已經可以使學生了解演算法的重要性。演算法中有很多是相當難懂的,如果學生能夠了解那些複雜的演算法,一定會加強他們的思考能力。將來他們在解決問題時,會比較有好的想法,也比較能夠吸收新的知識。
我們不要常常講非常難懂的演算法,我們應該告訴資訊系學生,在寫程式時總要很有條理,無論哪一個程式,其實都是根據一個流程圖的,這個流程圖就是演算法。很多同學不會寫程式,也不知道如何偵錯,其實這都是因為他不會邏輯思考。學習演算法絕對有助於學生在邏輯思考方面的訓練。
我因此希望全國所有的資訊系都重視演算法教育,如果我們希望學生能夠寫出好的程式,這個學生的邏輯性一定要很強,而演算法的教育一定可以使學生在思考上相當合乎邏輯的。