自從開始讀研究生, 這個博客的 level 就越來越高了...

首先要向大家介紹什麼是計算理論. 這是一個電腦科學的分支, 而且是完完全全理論性的一個研究分支. 我們都知道, 不管是硬體還是軟體, 它都是存在大量實際運用的, 但是這個分支是硬體理論和軟體理論的結合, 而且包含了大量數學. 我們在《演算法》這一系列的文章中, 告訴大家要解決某一個問題需要多長時間, 要用掉多少空間. 然而在這個系列的文章中, 我要告訴大家, 對於一個問題 :

上面的順序其實並不正確, 按照計算理論中, 正確的順序是首先研究計算模型理論, 然後研究可計算理論, 最後才研究計算複雜性理論. 請注意區分複雜性和複雜度這兩個概念, 複雜性是指一個問題難不難, 而複雜度是用於描述解決一個問題需要多少空間和時間. 不過為了方便理解, 我將調整順序

1. 計算複雜性理論

我遇到的問題是多種多樣的. 從我們人的直覺上, 我們其實可以感覺某些問題是容易解決的, 某些問題是難以解決的. 當然, 這裡有一個前提, 就是這個問題可以被解決. 在本博客中, 我們已經介紹過排序問題. 用你的直覺去感受, 排序是否困難呢? 很顯然, 這不難. 現在換一個問題. 對於大學某個學院, 有若干個老師, 若干個班, 這些老師要教授學生多個不同的課程, 如何編排這些課程使得

  • 同一老師不在同一時間內教授不同的班
  • 同一老師不在同一時間內教授不同的課程
  • 同一班學生不在同一時間上不同的課
  • 一個課室不在同一時間供兩個班上課
  • ...

上面列出的, 都是編排課程中不能出現的衝突. 用你的直覺去感受, 這個問題是否困難呢? 我覺得至少是難的, 因為我需要列舉出所有的可能性, 然後排除掉衝突的部分. 對於排課問題, 隨著老師、班級、課室和課程的增多, 即使是一台超級電腦, 也很難在很短的時間內得到答案

再舉一個實例, 從地圖中某幾個地點, 找到起始位置到終點最短的走法. 這個問題也不是特別難. 但是如果要求所有地點都只能走一次, 最後還要回到起始位置, 並且走的路徑最短, 這個問題是不是就難很多?

其實人確實是可以從直觀上去感覺一個問題是否是難的, 但是直覺總歸是不準確的, 所以就出現了計算複雜性理論這個研究分支

問題 1. 是什麼使得某些問題很難計算, 又是什麼使得某些問題很容易計算呢?

這個問題, 至今沒有答案. 但是, 我們確實可以根據一個問題的計算難度, 給問題劃分類別. 從這個角度來說, 我們雖然不能證明某些問題是難計算的, 但是可以以此為基準, 我們至少有一些證據和理論來表明某一個問題是難計算的

那麼這個研究分支的意義在哪裡呢? 面對一個很難計算的問題, 超級電腦都很難很短時間內給出答案, 我們會轉換這個問題, 試著能否通過化約為其它問題, 使得問題變得容易解決. 如果不行的情況下, 我們會採用另一個原則, 就是獲得一個並不是特別完美的解. 這裡, 不完美不僅僅代表不是最佳解, 很可能它也不準確, 但是我們可以接受. 再者, 如果某一個問題僅僅在某些情況下是困難的, 但是絕大多數情況下是容易的. 那麼一個偶爾運作稍慢的程式, 也可以令人接受

《貪婪演算法》這篇文章中, 我們已經向大家介紹了 P 問題和 NP 問題, 這就是計算複雜性理論中的概念. 一個直接受到計算複雜性理論影響的領域是密碼學. 我們希望密碼破解是難上加難的, 所以我們可以從計算複雜性理論出發, 設計出一個新的創造性的編碼

2. 可計算理論

在現代, 當面對一個需要巨量計算的問題, 我們首先想到使用電腦進行計算. 而某一些問題是不能用電腦解決的, 比如尋找 \frac {sinx}{x} 的原函數初等表達, 即 \int \frac {sinx}{x}dx. 通過電腦計算函數的原函數似乎很自然, 但是某一些任務是任何電腦都無法完成的 (準確地來說, 這裡的電腦是指決定性圖靈機器, 即 DTM). 計算複雜性理論將問題評判問題的難解性, 而可計算理論評判問題的可解性

3. 自動機理論

自動機理論闡述了計算的數學模型的定義和性質. 這些模型在電腦科學中有著若干應用, 例如我們接下來要講述的有限狀態機和上下文無關文法. 自動機理論是可計算理論和計算複雜性理論的基礎, 它們都需要精確的自動機理論定義. 另外, 自動機理論還可以幫助我們提升形式化語言的能力

我在介紹初等數學的時候, 已經要求大家掌握絕大部分初等數學的內容. 要學習這門課, 這些數學基礎基本夠用, 但是還需要圖論和布林運算基礎, 除此之外可能還需要少量的離散數學基礎. 對於圖論, 我們會在《資料結構》系列的文章中進行介紹, 剩餘一些理論基礎不是特別多, 因此可以在文章中直接額外附加. 當然, 後期博客也會補充完整的離散數學內容