<改變世界的九大演算法> 心得

原文作者：John MacCormick
譯者：陳正芬
出版社：經濟新潮社
出版日期：2014/08/07


    這本書我借了快兩個月，有一頁沒一頁的看，然後終於被催還了。XDD

    這本算是資訊領域很好的科普書。它提到的演算法都是每天被普羅大眾所使用、解決真實世界的具體問題的偉大演算法。書裡用深入淺出的例子，說明這些演算法運作的原理。

     那它選了哪九大演算法呢？

1. Text indexing (ch2)
2. PageRank (ch3)
3. 公鑰加密 (ch4)
4. 錯誤更正碼 (ch5)
5. Pattern Recognition (ch6)
6. 資料壓縮(ch7)
7. 資料庫transaction(ch8)
8. 數位簽章(ch9)
9. 如果存在會很了不起的演算法XD

- -  -

以下為個別介紹：

1. Text indexing (ch2)
這是搜尋引擎相關的演算法。
(1) Word-location trick：存網頁中每個字的位置，就可以運用位置的鄰近與否，來判斷搜尋的相關性。
(2) 元詞技法：在標題的文字，權重提高，來判斷搜尋的相關性。

2. PageRank (ch3)
    這是也搜尋引擎相關的演算法。
    PageRank是Google引擎當初之所以能打敗其他搜尋引擎、獨領風騷的原因。它運用的是超連結技法，把一個網站的超連結視為投票，被投票越多的網站權重越高，而權重越高的網站投出去的票越有價值。整個系統可以用矩陣相乘算到一個平衡結果。
    但是整個網頁相連的結構很大，算page rank耗時很久，這時採用random walk技法可以得到近似結果。

3. 公鑰加密 (ch4)
    這是資安相關的演算法。裡面提到我們要如何透過公開的網路進行秘密通訊。主要技法是採用一個公開的公鑰，雙方各自利用公鑰將自己的訊息處理後公開，取得對方的資訊後，利用對方的資訊再處理自己的資訊。藉由不可逆的運算過程，雙方最後會得到相同的結果。
例: 公鑰basis=2,clock=11,  我:8, 對方: 9
我: (2^8) mod 11 = 3
對方: (2^9) mod 11 = 6
我公開3, 對方公開6
我: (6^8) mod 11 = 4
對方: (3^9) mod 11 = 4
兩人會得到相同的數字4
這是由於11是質數，對2^n其餘數有循環性。這就是為什麼數學上要不斷尋找更大的質數，因為質數越大，加密效果越好。

4. 錯誤更正碼 (ch5)
可靠度相關演算法。就像我們的銀行帳戶或身分證都有最後一碼檢查碼, 錯誤更正是指藉由"重複"或"冗餘"來進行錯誤檢查。其中的"漢明碼"就是一種錯誤更正碼的編碼方式。使用二維的錯誤檢查碼甚至可以直接知道錯誤碼的位置。

5. Pattern Recognition (ch6)
最經典的問題是辨識0~9的數字，可以採用如knn、decision tree等，也可以採用類神經網路。

6. 資料壓縮(ch7)
所謂的無損壓縮(lossless compression)是指找到資料的pattern、儲存pattern來取代儲存資料本身的一種資料壓縮方式。例如:AAAABBB可以存成4A3B。
有損壓縮雖然不是白吃的午餐，但是常常很划算。

7. 資料庫transaction(ch8)
ACID properties可以確保資料庫在交易時是安全的。

8. 數位簽章(ch9)
資安相關的演算法。一個軟體要經過認證, 才能確保來源是安全的。
就像我們再使用信用卡的時候, 需要透過簽名才能確保是本人。
一個契約若由某個人(或是某間公司)所認可, 它必須要能夠通過數位簽章的審核。

例:
訊息:5
假設某A選擇一數字當作鎖: 6, 選擇時鐘尺寸(質數): 11  鑰匙: 2
有一個公家銀行提供某A的時鐘尺寸和鑰匙,
5*6 mod 11 = 8, 這個8即是數位簽章
這時如果有某個人想檢驗這個8是不是某A承諾的,
它只需要將 (8*2) mod 11 = 5
若剛好等同於一開始的訊息5, 即可開鎖

9. 如果存在會很了不起的演算法 (ch10)

什麼是可計算的?
再電腦科學的領域, 這是可以被證明的問題
例如搜尋當機行為的程式不可能存在
這可以by contradiction去證明

讓我想到離散裡,
有個理髮師宣稱他將會幫「不幫自己剪頭髮的人」剪頭髮,
證明這種理髮師不存在。