演算法讀書筆記 - 快樂兒童餐入門篇

上回做完 BFS 程式面試考題，我萌生挑戰重讀演算法書的想法。其實，多年前我有試過一回，在圖書館借了些書回來唸，想拉近自己跟本科生的距離。但自學不比在校修課，沒有被當的壓力，學完又沒什麼機會馬上應用，加上東西又枯燥就... 你知道的。

臉書留言讀者推薦了一本「改變世界的九大演算法」，為重讀念頭灑了一把助燃劑，於是....

市立圖書館的演算法相關書籍比想像多且有個共同特色 - 都沒人在排隊，預約不用等。(噗! 想起以前預約商管書要超久，書硬一點比較沒人啃 XD) 週五預約，星期天就拿到書了。

雖說講的是硬綁綁的演算法，我還是先挑軟嫩好下嚥的開始，選了幾本科普走向、非教科書性質的入門書，算是「快樂兒童餐」等級吧，以防再次中輟。

第一波借了三本：

• 改變世界的九大演算法 讓今日電腦無所不在的最強概念，John MacCormick 著 陳正芬 譯
• 演算法圖鑑，石田保輝 宮崎修一 著 陳彩華 譯
• 寫程式前就該懂的演算法，Aditya Y. Bhargava 著，張書華 譯

原本以為要啃上好幾天，但意外的是，幾本書裡超過一半的演算法我原本就懂，公私鑰加解密跟數位簽章部分學生時代研究過，其餘有些在工作後自己查過資料。加上現在唸這些東西的目的在增廣見識，對演算法種類與應用情境有完整認識，不需硬記死背到應付考試或面試線上測驗的程度。知道有哪些兵器可用，何時該拔劍什麼場合該用矛，觀念清晰，用時再研究細節即可。何況這些演算法多有現成程式庫，需要自己重寫一個的機會很低，再加上近期 AI 快速發展，以後說不定一句「使用 Bellman-Ford 演算法計算最短路徑」程式就寫好了。

總之，讀完這三本書比我預期輕鬆，把握五一假期完食，我的演算法自修計劃成功踏出第一步。

下面的筆記是寫給自己，以術語為主當成記憶的索引：

改變世界的九大演算法

這本嚴格來說更像商管書，嘗試向不懂程式的人介紹與日常生活息息相關的幾個著名電腦演算法

• Ramdon Surfer Algorithm - 隨機漫遊，Google PageRank，評估網頁被其他網頁連結的熱門度，隨機開始向外找 15% 重新開始，更進一步用數學推導取代實際跑，用低成本得到相近結果
• WebSpam - 製造連結以提高 PageRank
• Block Cipher 分塊加密
• Diffie-Hellman Key (Paint-Mixing Trick) 多金鑰合成一把，用 Discrete Exponentation 離散指數混合、用 Discrete Logarithm 離散對數還原
• Clock Arithmetic 時鐘算數，例：刻度 11 的時鐘，走到 10 之後從 0 開始
• Public Private Number, PPN = 基數 ^ 個人數字 (時鐘尺寸) 時鐘尺寸需質數、基數需 Primitive Root 原根，各次方餘數涵蓋時鐘各刻度
• RSA 1970 申請專利，2000 年已到期
• Error-Correcting Code, ECC
• 多傳幾次 = 重複技法
• Redundant 冗餘技法 7, 4 Hamming Code, 7 碼中 4 碼數字 3 碼檢查
• Checksun 校驗技法 階梯式檢驗碼(如身分證檢查碼)、簡單+階梯 可檢測二碼錯誤
• Pinpoint 定點目標法 16 轉 4x4 加檢查，可偵測校正一碼錯誤
• Two-Dimension Parity 二維校驗
• Claude Shanno 通訊的數學理論 - 重量級論文
• Finite Field Algebra 有限場代數 - 用於 CD、DVD、硬碟資料校驗
• Ethernet 用 CRC32 校驗，另外還有 MD5、SHA1、SHA256、SHA512，衛星用 Low-Density Parity Check Code
• Pattern Recognition 模式識別，仍當今 AI 重要技術
• Nearest Neighbor Classifier - 依門牌判斷捐款給民主或共和黨，K-Nearest Neighbor K=3 or 5 取最近三個或五個判斷
• 圖像相近度判斷，二圖相減看差異比例，愈小愈像，99.5% 正確，跟 Support Vector Machine、CNN 效果相近，且不用學習
• Decision Tree 決策樹，問 20 個好問題，由是否決定答案
• 人工神經網路 Artificial Neural Network
• 太陽眼鐘問題 - 照片轉 30x30 Pixel 圖片，訊號 0 ~ 1、權重 0 ~ 1，輸出介於 0 ~ 1，機器學習
  Multivariable Calculus 多元微積分 Stochastic Gradient Descent 隨機梯度下降
• 1956 Dartmouth College 會議帶起 AI 話題，之後沈寂數十年，直到 1997 IBM 深藍
• 壓縮 Lostless Compression / Lossy Compression
• Run-Length Encoding: 21A 10BC 5A 3DEF
• Same-As-Earlier Trick: 往前回幾個字母複製幾次
• Shorter-Symbol Trick: 常用字母用一碼，有些用兩碼，編碼避開模棱兩可
• Leave-It-Out Trick: 刪去法，極端例子，移掉雙數列及欄，變 1/4，靠 Comppression Artifact 還原 ( Pixel 方格感 )
• 相片壓縮 JPEG、聲音 MP3/AAC、ZIP/LZ77、Huffman Coding 霍夫曼編碼法
• 資料庫 Wirte-Ahead Logging (To-Do List Trick) 一筆一筆記錄要做動作，先寫成日誌，做完再刪除
• Idempotent 冪等，動作不管做幾次結果都相同
• Two-Phase Commit (Prepare-Then-Commit Trick) 先打電話跟大家約時間，不成的話，第二階段一一打電話通知取消
• Virtual Table - SQL 查詢時，Join - Projection(推估、捨棄不要欄位) - Select，1970 年 IBM 研究員 E.F.Codd 發表關聯式資料庫重量級論文
• Physical Padlock Trick 實體鎖技法 - 私鑰=鎖、公鑰=鑰匙，公鑰跟時鐘尺寸公開
• 量子電腦因式分解能力優於傳統電腦，對公私鑰破解能力上升
• 反證法 Proof by Contradiction，S 暗示 T，若 T 是錯的，S 是錯的
• Undecidable 不可判定性，無藉由寫程式解決的問題。其對日常電腦使用影響不大，因：1) 是否有答案不是唯一考量，耗時可能無法接受 2) 處理過程會得到好結果
• 一些有潛力的演算法：Zero Knowledge Protocol 零知識協定、Distributed Hash Table 分散式雜湊表、Byzantine Fault Toerance 拜占庭容錯

寫程式前就該懂的演算法

作者經營插畫部落格，擅長用插圖解說程式原理範例，圖形路徑、貪婪演算法、背包問題解釋得挺好。但翻譯較怪，像是 Binary Search 翻二進位搜尋，有些地方太過簡略，需要額外查資訊讀懂

• 大 O，一般可反映演算法在最壞情況的計算複雜度(但有例外，如 QuickSort)，可視為演算法效率的指標 延伸閱讀：評量演算法好壞的 Big O by hanahpun
• O(log n) 對數、O(n) 線性、O(1) 與數量無關、O(n log n) 如快速排序、O(n!) TSP 旅行推銷員問題 O(n * 1/2 * n) = O(n²) 常數部分不計
• 歸納證明法 Inductive Proof：先分析基本情況再分析歸納情況，二者成立則得證。快速排序對大小為 0 或 1 的陣列有效(基本情況)，對大小為 1 的陣列有效，對大小為 3 的陣列也有效(歸納情況)，結論，不論陣列大小都有效。
• 雜湊表 Hashtable 又叫 Hashmap、Map、Dictionary、Associative Array
  碰撞 Collision，兩個 Key 產生的雜湊值相同，會指向同一個儲存位置，用 Linked List 解決
  搜尋、插入、刪除最佳都是 O(1)、最差是 O(N) 註：所有 Key 雜湊值都一樣，實務上不會發生 Load Factor 負載系數，儲存槽的已佔用比例，過高(例如>0.7)碰撞增加，應調整大小
• BFS Breadth-First Search，到 X 的最短距離
  最少棋子移動次數、最少編輯次數校正錯字、Shortest-Path Problem 最短路徑問題
• 有向圖 Directed Graph (連線有箭頭) / 無向圖 Undirected Graph
• 圖形 = Node 節點 + Edge 邊，Neighbor 相鄰節點
• 拓撲排序 Topology Sort - 依據圖形製作順序表
• 最短路徑：Dijkstra's Algorithm 戴克斯特拉演算法
  也可路徑帶行車時間(Edge 加上 Weight權重)，求耗時最短。Dijkstra 只適用有向無環圖，也不支援負權重(訪問過的 Node 不會再走)
• 樂譜換購鋼琴案例：做出 父項 / 節點 / 成本 的表，查表反推追出成本最低
• Bellman-Ford Algorithm 可支援負權重
• 貪婪演算法：排課問題(避免衝堂排滿課表)、背包問題(小偷在負重限制內裝入最高價值)、廣播節目選擇電台以求覆蓋所有州 O(n^2) 挑選 Local Optimal Solution 得到 Global Optimal Solution， 註：書中本段過於簡略，補充維基，貪婪演算法很少能找到最佳解，但簡單效率好，要求不高時不失為好選擇。追求最佳解有時會有反效果，例如：辛普森悖論。
• 冪集合 Power Set - 所有可能的子集合 O(2ⁿ)
• Approximation Algorithm 近似演算法 - 速度快、接近正解就好
• NP Complete / NPC、NP 完備、NP 完全：旅行推銷員、集合覆蓋 註：非確定性多項式(Non-deterministic Polynomial)問題(NP 問題) 指可以在多項式時間(與 n 成多項式關係，例如 n²，而非對數時間，如 2ⁿ)被驗證，但不能在多項式時間被解決的問題
• K-Nearest Neighbors Algorithm KNN，分群
• 垃圾郵件用 Naive Bayes Classifier
• Fourier Transform 傅利葉轉換，將聲音拆解成多種頻率聲音的混合 延伸閱讀：神奇的互動式傅立葉轉換介紹
• Parallel Algorithm 並行計算，注意拆分合併結果的管理成本、負載要平衡才有效果
• Distributed Algorithm 分散式計算，Map/Reduce，Apache Hadoop
• Bloom Filter 布隆過濾器 / Google 檢查是網頁否有索引過
  Probabilistic Data Structure，答案可能是對的，可能是錯的，但只會誤肯定(沒編索引的說有)，不會誤否定(說沒有的一定沒編過索引)，好處是資料空間比 Hashtable 小很多
• HyperLogLog / Google 計算特定搜尋次數
  近似答案，但所需空間極小
• SHA，Secure Hash Algorithm
• 密碼雜湊的黃金標準 bcrypt
• Locality-Sensitive Hash 區部敏感雜湊，Simash 用於比對相近內容
• Diffie-Hellman Algorithm 公私鑰，但 RSA 是後起之秀
• Linear Programming 線性規劃
  所有圖形演算法都能用 LP 求解，應用範圍更全面的架構，使用 Simplex Alogrithm，複雜!

演算法圖鑑

26 種演算法 7 種資料結構的用詳細圖解，對於了解原理蠻有幫助

• 基本資料結構：List (Linked List)、Array、Stack (LIFO)、Queue (FIFO)
• Hashtable：Collision 時用 Chaining (Linked List) 或是 Open Addressing 求下一個侯補位址 (多個雜湊函數或 Linear Probing 線性探測)
• Heap：樹狀結構，Priority Queue，最上方永遠是最小值，取最小值 O(1)，重整 O(log n)
• Binary Search Tree 二元搜尋樹：所有節點一定大於左支線出去的所有子節點、一定小於右支線出去的所有子節點
• 延伸：Self-Balancing Binary Search Tree、m 個子節點的 B-Tree
• 排序
  Bubble Sort O(n²)
  Selection Sort O(n²) 找最小值，將其與左邊對調
  Insertion Sort O(n²) 向右取下一次，插到合適位置
  Heap Sort O(n log n) 用 Heap 結構以 Descending Order 插入(最大值在取上面)，由上依序取出，取去最上 Node 時樹要重整 O(n log n)
  Merge Sort O(n log n) 不斷分割成幾乎等長的兩個數列，直到無法割為止，兩數列合併時較小數統一放左邊，比較左邊決定先取誰完成排序
  Quick Sort (n log n) 快速排序，分成 [比基準值小的陣列] 基準值 [比基準值大的陣列] Divide and Conquer
• 陣列搜尋 Linear Search O(n)、Binary Search O(log n)
• 圖形搜尋 BFS 找距離最近 DFS 探索路徑(找到就結束)
• Bellman-Ford Algorithm 貝爾曼福特，指定起終點、求邊權重總和最小路徑 O(n * m) m = 邊數量
• Dijkstra's Algorithm 戴克斯特拉，指定起終點、求邊權重總和最小路徑 O(n ²) 或 O(m + n log (n))(資料結構下點功夫的話)
  計算時間較短但不適用負權重，無法判斷最短路徑不存在(迴圈有負權重)
• A* Algorithm，由 Dijkstra 改良，忽略離終點很遠的路徑，需給線索(Heuristic Cost 試探權重，距離系數之類的)，但如果線索不準，表現比 Dijkstra 更差。常用於遊戲計算追逐敵人的路徑
• Eavesdrop 竊聽、Spoofing 欺騙、Falsification 竄改、Reputidiation 抵賴(不認帳)
• Shared Key Cryptosystem: Caesar Cipher、AES、DES、One-Time Pad
• Public Key Cryptosystem: RSA、Elliptic-Curve Cryptography 橢圓曲線密碼學
• Hybrid Cryptosystem: 用公私鑰系統加密共用金鑰傳送，用共享金鑰加解密內容(效率較好)
• Diffie-Hellman Key Exchange: 混合雙方共享的祕密數及公開數，安全地交換共用金鑰(二人在 2015 年獲圖靈獎)
  質數 P、生成元(原根) G，G^X mod P 求解 X，Discrete Logarithm Problem 離散對數問題，利用這個數學難題保護金鑰
• 訊息識別碼 Message Authentication Code
  HMAC Hash-based MAC、OMAC One-Key MAC、CMAC Cipher MAC
• 數位憑證 Digital Certificate
• 分群 Clustering，將類似的數據歸為一組
• K-means 隨機取點當中心，依距離分成指定數量的群，重算各點中心重新分群，直到中心點不再移動(數學證明一定會收斂)
• Hierarchical Clustering: 不必事先指定群數，n 點 n 群 -> 最近的兩群合併(n - 1) -> ... -> 合為一大群，過程中使用不同群集個數的分群進行分類，選擇其中最佳者
  如何決定最新的兩群：最短距離、最長距離、群平均法(Group Average Method)
• 輾轉相除法 Euclidean Algorithm 歐幾里德演算法(求最大公因數)
• 質數判定法 Primalty Test
  費馬質數判定法 Fermat Primality Test 若 p 為質數且 n < p， 則 n^p mod p = n (費馬小定理 Fermat's Little Theorem) 用此判斷質數的可能性高
• 用幾個數測試，可能性高就當它是質數 Probable Prime (可能質數)，RSA 用 Miller-Robin Primalty Test 非質數機率小於 0.5⁸⁰ 就算質數
• Carmichael Number 卡邁克爾數 / Absolute Pseudo Prime 絕對偽質數
  561 = 3 x 11 x 17 表示的合數(Composite Number，非質數的自然數) 可通過質數測試，但比例極低
• AKS Primalty Test 三位印度數學家找出 100% 判定質數的方法，但多項式階數很高計算耗時難以接受，實務上還是用費馬質數判定法
• Google 網頁排名 - Random Surfer Model
• Tower of Hanoi 河內之塔