北京liu xinyu同學六年完成《初等算法》

jopen 10年前發布 | 14K 次閱讀 算法

北京 liuxinyu 同學寫完《初等算法》。全書英文寫作，600 多頁：我終于寫完了《初等算法》一書。

　　這本書完全免費，可以從這里下載電子版：https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/elementary-algorithms.pdf?raw=true

　　Why

　　算法書籍汗牛充棟，《算法導論》，《計算機程序設計藝術》，《計算機程序的構造和解釋》……，為什么要寫這么一本書？是不是重復發明輪子？

　　這本書的特點有以下幾個：

　　1、形式化。所有的算法都盡量形式化為數學公式，同時給出偽代碼。我希望能夠讓算法回歸數學，具有代數符號般的簡潔和優美；

　　2、函數化和 imperative 對照。幾乎所有的算法都同時給出了傳統的 imperative 實現和純函數實現。

　　3、多語言。盡量給出了多種語言的實現，包括C, Haskell, Python, C++， Scheme/Lisp 等。

　　4、盡量手繪插圖，兒童畫風格。

  • 歸并排序的插畫

  • 跳躍青蛙問題的插畫

  • 狼、羊、白菜過河問題的插畫

  • 選擇排序的插畫
    • </ul>

    　　內容：

    　　《初等算法》一書包括了如下內容（按照出現順序給出）：

    二叉樹、插入排序、紅黑樹、AVL 樹、Trie 和 Patricia，后綴樹、B樹；

    Binary heap, Leftist heap, Skew heap, Splay heap, 選擇排序，Binomial heap, Fibonacci heap, Pairing heap；

    隊列，基于 Finger tree 的序列，快速排序，歸并排序，眾數查找、二分查找，Saddleback 查找，KMP 和 Boyer-Moore 查找，DFS, BFS，貪心策略和動態規劃。

    </blockquote>

    　　參考：

    　　有兩本書對《初等算法》影響最大。一本是 Chris Okasaki 的《Purely functional data structure》另外一本是《算法導論》。寫作過程中還參考了一些其他書籍，包括 Knuth 的《計算機程序設計藝術》，Richard Bird 的《Pearls of functional algorithm design》，Bentley 的《編程珠璣》以及一些論文。

    　　不足：

    　　寫這本書的六年中，我總是想起法國數學天才伽羅瓦最后寫的那句話：“我沒有時間了！”，我原計劃用 10 年寫完這本書，結果提前了 4 年。這樣的代價很大。為了避免翻譯，過濾“噪聲”，我直接用英文寫作。由于不是 native speaker，書中的英文語法和拼寫難免貽笑大方。為了趕時間，proof reading 被壓縮，許多結論采取了“拿來主意”，沒有進行嚴格的數學證明。一些章節的課后習題也沒有給出答案。

    　　未來：

    　　理想情況下，一本嚴肅的算法書應該在穩定、寬松的環境下精雕細琢。可是在社會劇烈發展的今天，在日新月異的中國，在人們習慣快餐而不再享受大餐 的快節奏生活中，在微博、微信取代文章、書信的手機網絡大潮下，這樣的理想環境根本不存在。我經歷了 Symbian 的裁員，然后經歷了互聯網創業公司，到 Nokia 后又經歷了微軟的裁員。未來不可預知。對于《初等算法》這本書，開放給社區是最好的選擇。需要做的工作很多：

    1. 翻譯中文版

    2. 社區 proof reading 和 review，修正內容上的錯誤和英文上的不足

    3. 提供一本習題集

    4. 補足數學證明

    5. 采用強大的數學工具，對形式化的算法進行分析
      6. </ol>

      　　一些數據：

      　　《初等算法》黃金分割 0.618 版本，歷時 6 年，在 github 上總共提交 1680 次 commit。全書 600 多頁，19 萬字（word）。2 萬 2 千行示例代碼。

      　　保護：

      　　《初等算法》在 GNU FDL 許可協議下發布，所有代碼在 GNU GPLv3 協議下發布。

      　　Larry， LIU Xinyu