Algorithm

演算法是什麼?

演算法是計算機科學非常重要的基礎科目。簡單來說,演算法就是用電腦算數學的學問(古代人用算盤算、現代人用電腦算),可以說是數學科目。

想要解決現實生活當中的各種問題,計算機科學家就把現實問題對應到數學問題,然後設計公式、把公式寫成程式,讓電腦執行程式計算答案──這些公式就叫做演算法了。

儘管這裡用了「公式」這個字眼來形容演算法,然而並不是各位印象中的數學公式。由於電腦能夠執行繁複的計算,所以公式可以設計成好幾十行、好幾百行,甚至用到很多數學理論。

因此呢,就算學習過演算法的人,也不見得懂得設計演算法;因為數學、程式的東西實在太複雜了。想把現實問題對應到數學問題,那就更複雜了。

電腦只會算數字

回過頭來,電腦又是什麼?電腦是個很潮的中文翻譯,不過實際上電腦的原意是「計算機」。電腦的英文叫做computer,而計算的英文就叫做compute。

電腦是一臺計算機,只會計算、判斷、儲存數字。又快又準。

程式是一連串計算、判斷、儲存數字的步驟。

電腦只會處理數字(二進位數字)。電腦裡的每一個文字、每一種顏色、每一種聲音,其實都有相對應的數字。

打個比方,我們規定:用1代表「一」,用2代表「乙」,用3代表「人」,……。一個數字對應一個中文字。電腦裡面的所有中文字,都依循人為規定,變作了數字。

再打個比方,「人」這個字,呈現電腦螢幕上是個「人」樣。電腦螢幕的畫面,是由許多小光點組成的;電腦螢幕上的「人」也是由許多小光點組成的。我們以「人」的左下角為座標原點,橫向為X軸,直向為Y軸,那麼「人」其實是(0,1)、(1,2)、(2,3)、...這些座標畫上黑點後所形成的。「人」這個字的的形狀,在電腦中變作了一連串的數字。

同樣的道理,呈現在電腦螢幕畫面上的文字、顏色、圖片、影像、聲音,全部都可以化作數字。一切事物在電腦裡面都是數字。

電腦並沒有想像中的那麼神奇。不過電腦最厲害的地方並不是電腦本身,而是在於電腦可以接上各式各樣的設備。接上攝影機與螢幕,就可以把色彩變成數字、把數字變成色彩;接上麥克風與耳機,就可以把聲音變成數字、把數字變成聲音。

電腦一旦接上了設備,就額外有用處。接上話機和基地台,就可以互通有無;接上數位相機和印表機,就可以製造回憶;接上重量儀和篩子,電腦也會揀土豆;接上車廂、接上警示燈、再雜七雜八接上一堆東西,就變成了大眾運輸系統。

若要用電腦解決現實問題,通常要考慮兩個方面:一、電腦應該接上那些設備?如何用電腦控制這些設備?二、現實問題如何對應到數學問題?如何設計演算法?

程式用來比對數字、改變數字、儲存數字

舉個例子,我們希望把螢幕上的「人」變成斜體字。過程大略是這樣──首先呢,把「人」的形狀(0,1)、(1,2)、(2,3)、...這些數字拿出來;然後呢,位置越高的座標,就往右移動多一點,如此一來就成為斜體字了。想讓座標往右移動,就是讓電腦做數字加法計算,然後把相加結果儲存起來。

再舉個例子,用滑鼠點選一個資料夾,資料夾的顏色會反白。過程大略是這樣──首先呢,電腦偵測到滑鼠點擊的座標之後,把座標轉換成數字;然後呢,再把螢幕畫面的資料拿出來,看看螢幕上每個東西的座標,是哪一個與滑鼠的座標相符合;噢,原來是一個資料夾的圖示,把資料夾的顯示顏色給反白過來。

再舉個例子,電腦據說會揀選土豆。過程大略是這樣──把每一顆土豆拿出來,利用特殊的儀器,把形狀、重量、色澤、氣味統統轉換成數字,儲存在電腦裡面;然後呢,用電腦比較這些數字,找出優良的土豆,如此一來就有綿綿鬆鬆的土豆了!

編寫程式,計算數字,這就是程式設計師的工作。

數學和程式這麼複雜,為什麼要用電腦解決現實問題?

電腦的計算速度可說是非常的快,一秒鐘就能進行幾億次計算。就算文字多麼的多,圖片多麼的大,電腦處理起來,也是輕鬆寫意,順暢無比。

打開電腦裡的任何一份文件,用滑鼠捲動一下文件畫面,眼睛都還沒眨一下,正確畫面馬上就呈現在螢幕上了。事實上在捲動畫面的時候,電腦已經經過幾千萬次的計算,僅使用了極短的時間,就把螢幕上應該呈現的資料全部計算好了。

人類會想要用電腦解決問題,正是仰賴電腦的計算速度、正確性,以及電腦會自動按照程式計算的特性。程式設計師只要花心思寫出一支好程式,接下來的工作就可以讓電腦代勞了。電腦做的比人類更快更好,電腦做得到人類做不到的事情;儘管數學和程式很複雜,還是有很多人選擇使用電腦解決問題。

那些現實問題是用演算法解決的?

現代人的生活已經離不開演算法了。比如說你的手機裡面就有上百個演算法。你可以Google一下新聞。本站首頁底部的Multimedia和Interdisciplinarity欄位,也收集了許多影片。

Algorithm

演算法是什麼?

演算法由三個部分組成:輸入、計算步驟、輸出。介紹這件事情的時候,有人連結到函數的概念,也有人連結到黑箱白箱的概念。

          -----------------
input --->| computational |
          | sequence      |---> output
          -----------------

輸入、輸出是一堆數字。實務上是將這些數字放在資料結構,例如array、list。輸入來源,通常是硬碟裡面儲存的檔案,或者是藉由硬體裝置擷取到的數字,例如數位相機、麥克風等等。輸出去處,通常是硬碟裡面儲存的檔案,或者是藉由硬體裝置轉換之後以其他型態呈現,例如數位電視、數位音響等等。

計算步驟是一連串處理數字的指令。指令有兩種類型,一類是運算,例如數學運算加減乘除、邏輯運算且或非、比較運算大於等於小於、位元運算左右反且或異或。另一類是讀寫,例如讀取某處的數字、儲存數字至某處,就跟計算機的MR、M+按鍵的意義相似。

如何記載一個演算法?

有人用虛擬碼來記載一個演算法。如要設計電腦程式,虛擬碼是比較恰當的。

GREATEST_COMMON_DIVISOR(a, b)
1   while a ≠ b do
2       if a > b then
3           a ← a - b
4       else
5           b ← b - a
6   return a

有人用流程圖來記載一個演算法。如要設計電子電路,流程圖是比較恰當的。

大多數時候,我們無法光從虛擬碼和流程圖徹底理解演算法,就如同我們無法光從數學公式徹底理解數學概念。想要理解演算法,通常還是得藉由文字、圖片的輔助說明。

如何實作一個演算法?

實作的意思是:實際去操作、實際去運行。

對於資工系學生來說,自然就是把演算法撰寫成電腦程式,例如C或者C++程式,然後在個人電腦上面執行程式。

對於電機系學生來說,自然就是把演算法設計成電子電路,在麵包板印刷電路板PLD上面執行。

電子電路也有加法器、減法器、AND邏輯閘、OR邏輯閘等等,所以也可以用電子電路實作演算法。例如電子錶、隨身聽、悠遊卡等等,都是直接將演算法做死在晶片上面。在個人電腦、智慧型手機還沒流行之前,以往都是用電子電路實作演算法。

電子電路的執行速度是飛快的,電腦程式的執行速度慢了一點。然而,製作電子電路的過程相當麻煩,需要精密的設備、複雜的製程、大量的人力和經費,而且製成之後就無法修改;相對地,寫程式就簡單輕鬆多了,在電腦上面很容易調整程式碼,又可以儲存很多程式碼,最主要的是家家戶戶都有電腦。

Algorithm

學習程式語言

學習程式語言,有兩個層次:一、程式語言本身的語法;二、把想法轉換成程式碼。

第一個層次稱作「程式語言Programming Language」。目標是背熟規格書、靈活運用程式語言。

第二個層次稱作「程式設計Programming」。目標是設計程式碼解決問題。然而現今世界上還沒有一套公認的、固定的學習流程。

學習演算法

學習演算法,有兩個層次:一、演算法本身的運作過程;二、把想法轉換成演算法。

第一個層次稱作「演算法Algorithm」。目標是理解演算法、靈活運用演算法。讀者可以參考本站首頁的各大欄位,例如圖論、幾何、字串學等等。

第二個層次稱作「演算法設計Algorithm Design」。目標是設計計算步驟解決問題。讀者可以參考本站首頁的Algorithm Design欄位,以及從各種演算法當中汲取經驗、擷取靈感。

學習函式庫、工具

很多現實問題及其計算步驟,已經成為標準流程,沒有什麼改動的餘地,成為了演算法。因此科學家就把這些演算法編寫成「函式庫Library」,再把現實生活的常見需求編寫成「工具Toolkit」,讓程式設計的過程更加迅速。網路上已經有許多現成的函式庫和工具,通常也附帶詳細的使用說明書,方便工程師運用。

現今的軟體產業當中,幾乎都是直接使用現成的函式庫、工具;只有從事創新研發,才會從無到有設計程式碼、設計演算法。優秀的工程師,總是善於活用函式庫、工具,快速實現自己想要的功能。