標籤：

Math for CS 一周目閱讀完成紀念！

07-21
Math for CS 一周目閱讀完成紀念！

來自專欄最短的咒31 人贊了文章

原文發表於我的博客 notebook.xyli.me/MIT6-0

  • google books books.google.com/books?
  • 豆瓣讀書主頁 book.douban.com/subject
  • 2004版（339頁）boazbarak.org/cs121/Leh
  • 2012版（800頁） seas.harvard.edu/course
  • 2017版（1006頁） courses.csail.mit.edu/6
  • 2018版（1048頁） courses.csail.mit.edu/6
  • MIT 6.042相關習題/材料 learning-modules.mit.edu
  • MIT 6.042 2017 final courses.csail.mit.edu/6

這本久負盛名的6.042同名教材Mathematics for Computer Science幾乎每年隨著MIT重新開設6.042更新一遍，從2004年單薄的339頁到今年已經1000多頁。第一次被介紹這本書是在Stanford的公開課Algorithms: Design and Analysis的延伸閱讀材料里推薦了這本書2004版作為課程的數學基礎參考，我也只通讀了這一版的全部內容。

目前市面上沒有正式出版過它的紙質書，它實質上只是MIT 6.042這門課的講義集。相比附贈豐富習題集的2012以及後來版本，2004版339頁的講解內容顯得清爽緊湊，但或許也因為只是電子版的講義集，編寫時間距今已久，其中存在不少可能會使人困擾的勘誤。所以如果此時決定入手閱讀這本書，可以從這一年最近的電子版開始，習題大部分也是值得一做的。比較遺憾的是，網上比較難找到這些習題的題解，我也在讀完2004版開始嘗試著做了一下2017 final（歡迎和感謝有興趣的朋友交流和指正），試圖快速檢驗閱讀成效和兩版之間的區別，發現近年以來這本書也增加了很多有趣實用的概念和方法。

Mathematics for Computer Science這個標題試圖涵蓋的範圍很大，讓人無端聯想到知乎式的提問

我數學零基礎，想當程序員，應該先從什麼內容學起？

在了解到這本書之前，被問到想學計算機應該學哪些數學，大概會很潦草模糊的回答就像大部分大學的CS本科生一樣，學微積分，線性代數，離散數學，概率論……大概想學密碼學還需要補一下數論等等建議。突然有了這麼一本標題宏大的書似乎能一次性解決這個老生常談的問題？不存在的，稍有常識的人都知道不可能有一本書能夠一次打包計算機科學領域所需的全部數學工具，每當你想了解新理論和技術的基礎，都幾乎必須再去了解新的你所未曾了解過的數學知識。數學的應用和發展支持著計算機科學的常用常新，但反之計算機領域的新成果也一樣深刻地影響著數學，用靜態的眼光試圖一勞永逸掌握計算機領域的所有數學不過是不切實際的幻想。那麼為什麼MIT還要開這門課呢？我們還有繼續讀這本書的必要嗎？

當然有。MIT 6.042對於計算機基礎薄弱的低年級本科生來說，是非常快速和實用的前導課程。這本書無法成為萬用的靈丹妙藥幫助任何人一步登天，但可以拉著初學者的手溫柔平穩地把迷茫的他們送到美妙的計算機科學世界的門口。對於已經從事計算機工作或學習很久的讀者來說，也同樣可以通過它了解到自己可能忽視和遺忘的世界。應數風格的編書使得每個新概念都由一個具體的計算機問題引入，一步步手把手教你建模，用直觀的方法解決和證明，然後引出更多在計算機領域相關的該概念應用。即使拋開這些工具的實用性，它們也本來就是很美好的東西，閱讀這本書也可以僅憑直覺感受到這種讓人拍案的精妙。

  • Proofs 部分講了邏輯規範表達，以及一般會用到的證明方法。不僅有歸納和反證等貫穿全書的證明工具，也有針對於可計算基礎的遞歸定義的遞歸結構證明。這些都構成了good proof template的一部分。
  • Number Theory 部分以具體的Turing Code場景，展現了簡潔的密碼學發展史。
  • Communication Networks 部分介紹了圖論的知識在現實的分組轉發網路是如何運作的，以bufferfly模型為例引入分析整個網路的性能指標在不同的圖結構下的差異。
  • Counting 部分介紹了複雜度理論常用的漸近工具的定義和用法，Generating Functions轉換序列，以集合映射關係作為規範的計數基礎，配合豐富的應用場景講解計數方法，為後面的Probability部分打下堅實的鋪墊。
  • Recurrences 部分為遞歸問題提供了強力的計算工具，解Linear Recurrences遞推式同樣給了很多動態規劃問題另一種可能性。

以上作為本科時學習過相關數學課程的我仍感到值得一讀的地方，很多培養計劃裡面不會涉及這些內容或者只是草草帶過。當然雖然名字叫Mathematics for Computer Science卻完全沒有涉及微積分或者線性代數任何相關基礎知識，大概是默認這些內容需要另開課程詳細講解，其實對於其他出現在書中數學工具也是如此，它只能拉著你的手帶你了解到有這些東西的存在，敲開它們的門還是需要你自己動手，主動去尋求更深入的用法。正如前文所說，不存在這樣一勞永逸的包裹（正如Mathematics for Physics: A Guided Tour for Graduate Students本質上也只是更深刻嚴謹的「標題黨」，笑），想保持自己站在計算機科學技術的前沿，永遠要不斷去學習和開發新的數學工具，但這不影響這本書對於新手的巨大價值，以及系統和連貫講解這些本質美麗自由之物的美感。

推薦閱讀：

TAG:應用數學 | 計算機科學 |