§1.1 計算模型
什麼是計算機?我們當然可以含糊地說目前我們看到的電腦都是計算機、或是說只要可以跑程式寫扣解題的都是計算機。但這種說法是很不嚴謹的。
西元 1936 年是個計算理論發祥的年代。同一年間先後由 Alan Turing 提出 A-Machine (就是大家後來稱之為圖靈機的東西)以及 Alonzo Church 發表了 $\Lambda$-演算。這些計算模型的共通點都是,它明確定義了「單位時間」可以作哪些事情。
當數學家們在討論這幾種計算模型誰比較強(能夠解比較多的問題)的時候,Church 和 Turing 證明了他們各自的計算模型計算能力是等價的(而且也等價於另一類可以用遞迴方式計算的 general recursive 函數)。因此,著名的 Church-Turing Thesis 描述的就是:我們能假設任何可以計算的函數,都可以藉由定義在 Turing Mahcine 上的演算法實作出來。
值得一提的是,目前現實世界中的電腦,使用的是隨機存取模型(RAM Model),它已知與 Turing Machine 的計算能力是相同的。我們不需要擔心有些問題在目前的電腦上解不出來 、但是在圖靈機上面可解。
一旦決定了計算模型以後,衡量演算法的執行效率,就可以被這個計算模型的「單位時間操作」決定。
§1.2 問題的類型
計算問題
什麼是計算問題?只要「可能可以用電腦解決的問題」都被稱作計算問題。這個定義相當不嚴謹,而且好像什麼都沒講,超級賴皮。但很幸運的是,在這一系列筆記當中,我們只需要關心比較務實一點點的、可以被我們定義下來的計算問題。
在我們的宇宙觀(?)裡面,一個計算問題通常會包含一個有限長度的輸入、以及一個明確的輸出目標敘述。我們可以對於這個把常見的計算問題類型作一些分類:
- 決策性問題(Decision Problem):輸出的格式一律是 yes 或 no,而且對於一個輸入,問題的內容會保證恰好其中一者是正確的輸出。
- 搜索問題(Search Problem):題目的內容通常是一個條件,只要輸出任何一個滿足條件的解就行了。(請注意,無解也可以是輸出的一種。)
- 計數問題(Counting Problem):題目的內容仍然是一個條件,但是必須要輸出有多少滿足條件的解。
- 最佳化問題(Optimization Problem):題目的內容包含一個條件和一個目標函數(Objective function),輸出的解必須要同時滿足條件、並且在該目標函數下優於所有其他滿足條件的解。
- 承諾問題(Promise Problem):這個是針對輸入的內容進行合理假設的一類問題。對於大多數的計算問題我們可以假設輸入的內容是任意的(或者可以說是任意有限長度的 0-1 字串 ${0, 1}^*$)。承諾問題通常會附上我們關心的「合法輸入範圍」,解決該問題的演算法沒有責任判斷輸入是否合法,也就是說,在這個合法範圍外的輸入,不管回答是什麼都被視為正確的。