笑傲「演算法」江湖的獨孤九劍

評論
評論

圖片來源:The Social Network

最近恰巧在書店看到了一本書,書名叫做演算法統治世界說明了演算法如何的重要如何與生活息息相關,很可惜書中並沒有提到太多關於演算法的實質內容。最近剛好在因緣際會下也讀到了一本覺得非常實用的書 “ Algorithms That Changed the Future”,中譯 “ 改變世界的九個演算法 ” 由 John MacCormick 合著。 本書以一種非常淺顯易懂的方式,試圖讓不論是否具有背景的讀者們都能夠了解這些偉大的演算法如何運作,以及他們是怎麼樣在各層面影響我們的生活。

為何需要了解演算法

不論看到各種議題,大家心中所想到的往往是:與我何干?。 在如此繁忙的生活下,我們已經很難拿出額外的精力去注意與自己不相關的議題了。但是電腦運算正一點一滴地改變我們的生活,我們或許沒有辦法全盤的去了解它的運作。但我們可以藉由概念性的去理解其核心,然後去明白究竟在生活上電腦運算的發展會對生活產生什麼樣的影響。舉個例子來說:我們知道輪胎或者是鞋子上了防滑紋路是為了要增加摩擦力,因此我們知道當紋路磨損之後要換新的。但非專業人士的我們不需要去了解紋路的設計對摩擦力的影響,以及計算究竟可以產生多少摩擦力。

什麼是演算法

那究竟何謂演算法? 演算法簡單來說就好比是一個「精確的食譜」,把我們所遭遇到的問題的解決方法,藉由有系統與條理的方式一步一步的解釋清楚。從上述我們可以知道幾件事情:

  • 演算法是用來解決問題
  • 演算法將解法切割成不同步驟
  • 演算法的解決問題的步驟是精確的,不靠人類的直覺與猜測

因為上面的幾個特性,我們才能夠藉由將演算法編寫成程式利用電腦做運行計算,來解決我們生活上的問題。

在這裡舉一個很簡單的演算法實例,費波納契數列求解給想要看一下演算法長什麼樣子的讀者們。但這部分與書中內容無關只是讓讀者知道真正的演算法大概長什麼樣子。

費波納契數列

首先先解釋費波納契數列: 0、1、1、2、3、5、8、13、21、34 。這個數列的特性是:

  1. 第一個數為 0
  2. 第二個數為 1
  3. 從第三個數開始,每個當前的數為前面兩個數的總和。舉例來講:
    2 = 1 + 1,3 = 1 + 2,5 = 2 + 3。

問題

現在的問題是費波納契數列的第 n 個數是什麼? 舉例來講,當 n 為 1,答案就是 0,n = 3 答案就是 1,n = 5 答案就是 3。

演算法

我們可以發現,除了第一個與第二個費波納契數沒有辦法用公式解之外,其他的數字都有規律。(因為第一個數與第二個數前面沒有數字,沒有辦法用前面兩個數字相加)。

從上面這個數列我們得到下述的演算法:

  1. 當 n = 1 答案就是 0
  2. 當 n = 2 答案就是 1
  3. 當 n 不為 1 或者是 2 ,我從第三位開始將每一位算出來並記下來直到我算到第 n 位。計算的方法是: 當前的數字等於前兩個數字之和。然後得到第 n 位的答案。

我們再舉個例:假設今天 n 是 5 。我的演算法會有如下的步驟:

  1. n = 3,於是我把已知的第二位與第一位相加 1 + 0 = 1
  2. n = 4,我把剛得到的第三位與已知的第二位相加 1 + 1 = 2
  3. n = 5,我把剛得到的第四位與剛得到的第三位相加 1 + 2 = 3
  4. 我得到第五個費波納契數是 3

讀到這裡或許有讀者問為什麼要這麼麻煩?第五個數不是一看就知道是 3 嗎? 是的,因為我們現在數字很小,那假設我們說的是第兩千個費波納契數呢? 或者是第兩萬個費波納契數呢?人沒有辦法在這麼短的時間內計算並記住這麼多數字,所以才需要利用演算法,讓電腦來為我們處理。

九大演算法

當然,在書中並不是像上面那樣子,一行一行的列出解法,而是藉由簡單有趣的例子,以及一些簡化的數字運算來為我們點出這幾個演算法的精髓部份。在書中提出了八個與我們生活切身相關的演算法與一個如果存在將會很了不起的演算法來討論電腦能力的極限。其中現存的八種如下:

搜尋引擎的索引

搜尋引擎的索引,是幫助你我在網路上正確地找到資料不可或缺的工具,我們要怎麼樣才能夠做有效的搜尋讓我們從網路海中撈出一根針?

網頁排序

當我們搜尋關鍵字,出來了這麼多的頁面,我要怎麼樣才能判斷哪個頁面是真正重要的?才能優先將它列出來?

公鑰加密

我在亞馬遜上輸入我的信用卡買東西,我要怎麼才能夠確定我的資料只有亞馬遜才看得到?

錯誤更正碼

網路更正碼被應用在網路之間封包的傳遞,以及 CD、DVD 還有硬碟上。祝要是用來確認我所讀取以及接收到的資料是否正確。舉例而言:假設我電話傳錯一碼,那我整個傳送就沒有意義了。

辨識模式

辨識模式被廣泛應用在人工智能上,像是語音便是服務客戶的自動電話,網路上按照個人興趣推薦商品以及大數據的處理,辨識模式都占有一席之地。

資料壓縮

我們總打開或者是將檔案做成過 zip 或 rar 檔吧? 圖片以及文字是怎麼樣縮小與放大都與資料壓縮有關。

資料庫

銀行的資料庫要怎麼樣才能確保我的交易是正確的?我會不會在交易的時候因為銀行的伺服器當機然後錢沒了?我要怎麼樣才能夠讓資料可以更快的儲存與被讀取都跟這部分有關

數位簽章

一般而言我們並不會接觸到數位簽章,因為我們的電腦會自動對數位簽章做檢驗,通常發生在下載軟體的時候。

這些演算法所包含的範圍有:網際網路搜尋、網路安全、資料傳輸的正確性、大數據、以及資料儲存與處理等。每項都與我們的生活緊扣,除非我們完全不使用電腦,否則你我都會多少接觸到上述演算法所涉及的領域。

公鑰加密

在書中,最令我印象深刻的一段是公鑰加密的部分,利用以塗漆做舉例讓大家來了解公鑰的基本精神,因此在這裡特別和大家分享。

問題如下:假設今天有三個人我、你、他以及有很多罐顏料,每個人有自己的小房間可以藏自己的顏料。在所有的溝通必須公開透明的情況下,我該怎麼樣才能夠在他不知道的情況下混合出和你相同的顏色?假設顏色代表秘密,我和你該怎麼樣才能在他的眼皮下傳達你我共同的小秘密?

演算法如下:

  1. 我們每個人選出自己的個人色
  2. 我們任一個人選出公共色
  3. 我與你將公共色與自己的顏色做混合,並公開混合之後的顏色(你知,我知,他知)
  4. 解答慎入 1

為了不妨礙讀者思考的樂趣,在這裡將演算法的最後一步寫在最後,但在這裡有兩個重要的假設,其中之一是顏色非常的多,所以他無法知道我選的個人色是什麼,再來是我無法將顏色重新分開來得到原本你選的顏色。

結語

演算法一直是每個電腦科學系的必修,常常我們在學習的時候卻陷入了數字的囹圄或者是因為理論而暈頭轉向但很多的時候我們不妨可以像書中介紹的方法一樣,退一步,仔細看清楚這些演算法的全貌仔細想清楚他們想要解決的問題試著用生活的方式所舉例來加深自己的了解。

書中所介紹的演算法其實都非常的重要,在筆者就學的期間幾乎學過,或接觸過更甚至親手寫出程式來執行一半以上的演算法。往往很多人認為現在在寫 App 大多都是使用 Library,究竟演算法有什麼重要的?我記得當時在演算法課上,老師告訴我們兩個答案:

  1. 因為國外面試都問演算法
  2. 學習演算法是一種思維的訓練可以讓你變聰明。

很多的時候學習演算法可以讓你在學習各種新的東西上都快速了許多,因為我們必須從每個角度來檢視自己的思考是否正確,然後將每一步都說明清楚來得到正確的答案,長久下來訓練自己的思維就是讓你自己與別人可以分出差距的地方。

也同樣的,很多新的想法都是建立在原有的基礎上,學習演算法可以讓我們在遇到新的問題的時候,靠著原有的基礎想出更新更快的解法。這也就是為什麼在國外公司面試的時候,演算法受到如此的重視。因為知識性的考題可以靠著記來補強,但是思維卻沒有辦法短時間訓練。

這裡再舉個例:假設學過化學,我們就不會說出類似吃鹽細胞會爆炸或讓身體腐蝕之類的話 2(曾在台灣某節目上有來賓認為鈉離子比鈉恐怖,與與身體細胞結合會產生嚴重的影響)。

在電腦運算如此發達的時代,我們非常幸運的可以站在這些巨人的肩膀上了解好幾十年下來所累積的智慧。


  1. 只要你我都個把對方的公共混合色帶回自己的房間加上自己的個人色即可
  2. 寶傑,你說說看鈉有多恐怖?

評論