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

電腦運算正一步一步的改變我們的生活,其中最核心的部分就是演算法。舉例而言:網路搜尋是怎麼做到的?搜尋結果又是怎麼排序的?演算法就像是本精確的食譜,靠著它我們才有辦法利用電腦解決這些與生活息息相關的難題。
評論
評論

圖片來源: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. 寶傑,你說說看鈉有多恐怖?

從物流到巡檢!無人機小兵立大功,助產業翻轉應用場景、加速智慧城鄉腳步

隨著科技進步,在推動智慧城鄉的道路上,已發展出應用無人機來縮短城鄉差距、加速產業應用佈局,同時提升民眾的生活品質。
評論
photo credit:經濟部工業局
評論

談起無人機會令你想到什麼?對多數消費者而言,第一時間聯想到的或許是結合影音、娛樂的應用場景,藉由飛行優勢捕捉各種畫面、創造更有趣的觀賞體驗,但其實無人機早已升級,在許多我們意想不到的場域裡發揮它的技術,改善我們當前的生活品質。

根據 DRONEII.Com 的報告指出,全球無人機市場將從 2018 年 140 億美元、一舉躍升到 2024 年 430 億美元,其中能發揮無人機應用的場景除了熟悉的娛樂、拍攝外,勘/救災、預警系統、資料蒐集與分析與環境監測等,亦是無人機可著力之處。

看準無人機所具備的這些優勢,讓經濟部工業局在「普及智慧城鄉生活應用計畫」中,善用無人機的價值,讓它得以跳脫娛樂拍攝場景,以物流、巡檢等角色走入偏鄉,為在地民眾以科技力注入創新活水。

看無人機如何從物流到巡檢,翻轉智慧城鄉

「智慧城鄉的目的就是要透過科技力,讓偏鄉地區的民眾也能同步享受等同於都會區的資源與生活品質。」作為國內長期投入研發無人機的中光電智能機器人王仲平協理觀察,這也是為什麼中光電加入「普及智慧城鄉生活應用計畫」後,選擇以物流、巡檢等場景作為起手式,希望藉由技術的輔助讓偏鄉地區的生活體驗可以再升級。

攤開 Google 地圖,從新竹火車站前往尖石鄉的路程接近 3 小時,途中更是九彎十八拐,也常因天災造成道路坍方,切斷輸送物資的主要管道。「但這趟路對無人機而言僅需 10 分鐘」在天氣許可下,無人機能垂直飛行加速物資運送,讓偏鄉在資源需求上邁進了一大步。當然,王仲平也解釋,這樣的場景是需要串接地方政府、物流業者乃至於零售業者都缺一不可,中光電發揮在無人機的技術與專業,攜手夥伴們才能讓智慧城鄉的發展被實現。

而這項技術也已輸出海外、與日本樂天合作。王仲平透露,目前已在白馬山進行試飛,在高低落差近 1600 公尺、往返距離約 10 公里的地區,以無人機方式將貨物運送至目的地。讓過去需要耗費車程、人力約 7 小時的路途,如今只需要 10 分鐘就能解決,不只能運送物資上山、也同時能將山上的垃圾運下來,藉由無人機創造雙向價值、提升偏鄉的生活體驗。

除了物流場域,巡檢應用也同樣能發揮無人機效益。王仲平表示,電塔維護關係著偏鄉居民的生活及維修人員的生命財產安全,過去動輒爬上高處修繕或需要跨域的奔波,不僅耗時耗力、也可能有人為無法判斷的疏漏發生。如今在無人機的輔助下,不僅大範圍的檢測不成問題,因不受空間影響、更能 360 度的徹底檢查,即便在環境惡劣的山區也難不倒它。

photo credit:經濟部工業局

用「眼睛」跟「大腦」,讓無人機更智慧地徜徉在場域中

無人機之所以能實現如此多應用場景、強化偏鄉地區生活品質與智慧水準,全仰賴技術上的突破,「你就想像現在的無人機其實是台會飛行的掃地機器人,」王仲平生動地解釋。傳統無人機因缺乏人工智慧的導入,讓任務執行依舊需要耗費大量人力監控,也可能因人為操作而發生意外,而這也是為什麼中光電在研發無人機的第一天起,就希望能賦予智慧設計,讓無人機能具有思考與判斷能力。

首先,要能被稱作為智能機器人就需要配置影像辨識系統,王仲平表示這讓無人機如同人眼一般,能捕捉外界影像,讓它在執行任務時能採集需要的資訊,同時透過 SLAM 避障技術,協助無人機判別外界的障礙物,無論在運輸或是巡檢的過程中,更加順利。

此外,智能機器人也需要具備良好的運算平台、就像是大腦一樣,能將捕捉到的影像進行分析、並且建立模型,以利未來在同一條路徑上的飛行時,可以更加熟悉、也讓這台無人機得以減少對人為操作的依賴,加速對偏鄉服務的提供效率。

偏鄉需求大,無人機應用潛力無窮

「其實物流體系的成本有 75% 都是耗費在最後一哩路。」王仲平說,若能借重無人機的技術突破瓶頸,相信在偏鄉的民眾生活品質將會有大幅度邁進,同時為加快腳步,他認為每個物流節點都需要擁抱數位工具、面臨數位轉型,才能攜手翻轉當前的應用場景。

展望未來、王仲平更是滿心期待,他相信還有很多場域正等著無人機發揮技術突破現有框架,「你能想像如果我們有空中計程車的時候嗎?那將會是航空界的革命性發展,也將為偏鄉居民的醫療帶來全新的體驗。」短程的載人運送服務將可能為偏鄉居民、甚至是因登山發生意外的狀況,有了更即時與效率的幫助。藉著這次的計畫,王仲平相信在攜手產官學一同合作打造可落地的應用,就能讓更多人看見無人機的價值、也才能加速偏鄉擁抱智慧科技。

經濟部工業局廣告