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」,讓程式設計的過程更加迅速。網路上已經有許多現成的函式庫和工具,通常也附帶詳細的使用說明書,方便工程師運用。

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

Algorithm

演算法書籍

教科書:適合資工系學生。

Algorithms
Robert Sedgewick and Kevin Wayne

Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

Introduction to Algorithms: A Creative Approach
Udi Manber

Algorithm Design
Jon Kleinberg and Éva Tardos

Algorithm Design: Foundations, Analysis, and Internet Examples
Michael T. Goodrich and Roberto Tamassia

An Introduction to the Analysis of Algorithms
Robert Sedgewick and Philippe Flajolet

An Introduction to the Analysis of Algorithms
Michael Soltys

工具書:適合程式設計師。

Algorithms in a Nutshell: A Practical Guide
Gary Pollice, Stanley Selkow, George Heineman

The Algorithm Design Manual
Steven Skiena

科普書:適合小朋友和大朋友。

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
繁:《演算法圖鑑:26種演算法 + 7種資料結構,人工智慧、數據分析、邏輯思考的原理和應用全圖解》
簡:《我的第一本算法书》

Grokking Algorithms: An illustrated guide for programmers and other curious people
繁:《寫程式前就該懂的演算法:資料分析與程式設計人員必學的邏輯思考術》
簡:《算法图解》

故事書:適合看熱鬧鄉民。

Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists
繁:《勇闖資訊新未來:打造資訊科技的幕後英雄》
简:《奇思妙想:15位计算机天才及其重大发现》

Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers
繁:《改變世界的九大演算法:讓今日電腦無所不能的最強概念》
简:《改变未来的九大算法》

Automate This: How Algorithms Came to Rule Our World
繁:《演算法統治世界》
简:《算法帝国》

演算法課程

Adam Blank
演算法課程網站,有許多課程講義。

Jeff Erickson
演算法課程網站,有許多課程講義。

Erik Demaine
演算法課程網站,有許多特殊主題。

演算法網站

GeeksforGeeks
程式語言、數學、演算法益智問題。

Algorithms Notes
演算法益智問題。

williamfiset/AlgorithmsWilliamFiset
演算法實作程式碼、教學講義、教學影片。

Rosetta Code
各式各樣的問題的實作程式碼。

Geometric Tools
數學、幾何、繪圖領域的實作程式碼。

演算法面試教學

LeetCode
演算法面試題庫,可以線上練習解題,主要是益智題目。

Coding Interview University
演算法教學資料彙整,主要是面試可能會問到的。

Algo Deck
演算法筆記,主要是面試可能會問到的。

GitHub: algorithms
GitHub的演算法項目,前幾名都是面試。

數學網站

AMS Open Math Notes
數學家的教學筆記。

Wolfram Math World
數學百科。

The On-Line Encyclopedia of Integer Sequences
數列百科。