《算法基礎：打開算法之門》一導讀

algorithms unlocked

計算機是如何解決問題的呢？小小的gps是如何隻在幾秒鐘内就從無數條可能路徑中找出到達目的地的最快捷路徑的呢？在網上購物時，又如何防止他人竊取你的信用卡賬号呢？解決這些問題，以及大量其他問題的答案均是算法。我寫本書的目的就是為你打開算法之門，解開算法之謎。

我是《算法導論》的合著者之一。《算法導論》是一本特别好的書（當然，這是我個人的主觀評價），但是它确實相當專業。

本書并不是《算法導論》，甚至不能被稱為一本教材。它既沒有對計算機算法領域進行廣度或深度的研究，也沒有遵照慣例來講述設計計算機算法的方法，甚至連一道需要讀者自己求解的難題或者練習題也沒有。

那麼，這是一本什麼樣的書呢？如果你符合如下條件，那麼就可以開始閱讀之旅了：

●你對計算機如何解決問題感興趣；

●你想知道如何評估這些解決方案的品質；

●你想了解計算方面的問題和這些問題的解決方案是如何與非計算機世界關聯起來的；

●你能處理一點數學運算；

●你不需要編寫過計算機程式（當然，編寫過程式更好）。

一些計算機算法方面的書籍是講述理論概念的，并涉及非常少的技術細節；一些書籍關注的全是技術細節；而另外一些書籍是介于這兩者之間的。每類圖書都有自己的定位，我将本書定位于介于兩者之間。誠然，本書涉及了一些數學知識，并且部分地方闡述得非常仔細，但是我已經竭力避免深入闡述細節（或許除了本書的末尾部分，我無法克制住自己，闡述了一些細節知識）。

我認為本書有點像開胃菜。設想你去了一家意大利餐廳，點了一份開胃菜，直到吃完開胃菜，你才會決定是否點其餘食物。開胃菜到了，你就開始用餐了。或許你不喜歡吃開胃菜，并且決定不點其他菜了。可能你喜歡吃開胃菜，但是吃完它，你就感覺飽了，是以不需要點其他菜了。或者也有可能你喜歡吃開胃菜，但你并沒有吃飽，此時你便開始期待其他菜了。将本書看作開胃菜，我希望能夠産生後兩種結果之一：或者讀完了本書，你就很滿足，感覺沒有必要再深入探究算法世界了；或者你非常喜歡從本書中所學到的知識，以至于你想要學習更多算法方面的内容。每一章最後一節的标題為“拓展閱讀”，其中會介紹更多關于該章主題的更為深入的書籍和文章。

你将從本書中學到什麼

我無法斷定你将從本書中學到什麼。如下是我希望你能從本書中學到的：

●什麼是計算機算法，能夠采用一種方式來描述計算機算法，以及如何評估算法。

●在計算機中查找資訊的簡單方式。

●在計算機中重排資訊以使其以一種預定順序排列的方法。（我們稱這一任務為“排序”。）

●如何解決那些能在計算機中以一種稱為“圖”的數學結構模組化的基本難題。在許多應用中，利用圖模組化的領域包括：道路網（哪些十字路口到哪些十字路口有直接相連的道路，這些道路有多長），任務間的依賴關系（哪個任務必須在其他任務之前完成），金融關系（世界各國貨币間的匯率是多少），或者是人與人之間的聯系（誰認識誰？誰讨厭誰？哪個演員和哪個演員出現在同一個電影中等）。

●如何解決關于文本字元串的問題。其中一些問題在某些領域有所應用，例如生物學領域，其中字元表示基本的分子，字元串表示dna結構。

●密碼學背後的基本原理。即使你自己從來沒有加密過一條資訊，你的計算機很可能已經對它執行加密操作了（例如當你在網上購物時）。

●資料壓縮的基本概念，這遠遠超過了“f u cn rd ths u cn gt a gd jb n gd pay”背後的壓縮原理。

●計算機在任意合理的時間内都難以解決的一些問題，或者至少還沒有人想出如何解決的問題。

為了了解本書中的内容，你需要事先了解什麼

正如我之前所說的，本書中涉及部分數學知識。如果你害怕數學，那麼你可以嘗試着跳過它，或者你也可以嘗試着閱讀涉及更少專業技術知識的書籍。但是我已經盡力做到令數學部分變得容易了解了。

我假定你從來沒有寫過，甚至從來沒有讀過一個計算機程式。如果你能看懂提綱的内容，就應該能夠了解我是如何表達每一步算法，以及如何将這些步驟合并在一起組合成一個完整的算法的。如果你聽到過如下笑話，那麼你已經是在通往算法世界了：

你聽說過被困在淋浴中的計算機專家嗎？當時他在按照洗發瓶上的訓示洗頭發。訓示說明是“打洗發露。沖洗。重複。”

本書使用了一種自由的寫作風格，希望這種比較個性的方法能使本書的内容看起來更容易了解。有些章節依賴于前面章節的内容，但是這種依賴程度很輕。有些章節開始時不涉及專業技術知識，但是會逐漸講述專業技術知識。即使你感覺某一章太難了，這也不會影響下一章内容的學習。你也很可能會從下一章的開始部分受益。

報告錯誤

如果你在本書中發現了錯誤，請通過發送郵件至algorithmsunlocked@mitedu來告知我。

<a href="https://yq.aliyun.com/articles/107633">第1章 什麼是算法以及為什麼應該關注算法</a>

<a href="https://yq.aliyun.com/articles/107637">1.1 正确性</a>

<a href="https://yq.aliyun.com/articles/107640">1.2 資源利用</a>

<a href="https://yq.aliyun.com/articles/107643">1.3 針對非計算機專業人士的計算機算法</a>

<a href="https://yq.aliyun.com/articles/107659">1.4 針對計算機專業人士的計算機算法</a>

<a href="https://yq.aliyun.com/articles/107660">1.5 拓展閱讀</a>

<a href="https://yq.aliyun.com/articles/107663">第2章 如何描述和評估計算機算法</a>

<a href="https://yq.aliyun.com/articles/107669">2.1 如何描述計算機算法</a>

<a href="https://yq.aliyun.com/articles/107673">2.2 如何描述運作時間</a>

<a href="https://yq.aliyun.com/articles/107674">2.3 循環不變式</a>

<a href="https://yq.aliyun.com/articles/107675">2.4 遞歸</a>

<a href="https://yq.aliyun.com/articles/107676">2.5 拓展閱讀</a>

<a href="https://yq.aliyun.com/articles/107678">第3章排序算法和查找算法</a>

<a href="https://yq.aliyun.com/articles/107679">3.1 二分查找</a>

<a href="https://yq.aliyun.com/articles/107708">3.2 選擇排序</a>

<a href="https://yq.aliyun.com/articles/107717">3.3 插入排序</a>

<a href="https://yq.aliyun.com/articles/107725">3.4 歸并排序</a>

<a href="https://yq.aliyun.com/articles/107740">3.5 快速排序</a>

<a href="https://yq.aliyun.com/articles/107749">3.6 小結</a>

<a href="https://yq.aliyun.com/articles/107750">3.7 拓展閱讀</a>

第4章排序算法的下界和如何超越下界

41基于排序的規則

42基于比較排序的下界

43使用計數排序超越下界

44基數排序

45拓展閱讀

第5章有向無環圖

51有向無環圖

52拓撲排序

53如何表示有向圖

54拓撲排序的運作時間

55pert圖表中的關鍵路徑

56有向無環圖中的最短路徑

57拓展閱讀

第6章最短路徑

61dijkstra算法

62bellmanford算法

63floydwarshall算法

64拓展閱讀

第7章字元串算法

71最長公共子序列

72字元串轉換

73字元串比對

74拓展閱讀

第8章密碼學基礎

81簡單替代密碼

82對稱密鑰加密

83公鑰加密

84rsa加密系統

85混合加密系統

86計算随機數

87拓展閱讀

第9章資料壓縮

91哈夫曼編碼

92傳真機

93lzw壓縮

94拓展閱讀

第10章難？問題

101棕卡車問題

102p、np和np完全類

103可判定問題和歸約