§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}^*$)。承諾問題通常會附上我們關心的「合法輸入範圍」,解決該問題的演算法沒有責任判斷輸入是否合法,也就是說,在這個合法範圍外的輸入,不管回答是什麼都被視為正確的。

大部分的問題可以轉化(Reduce)成決策性問題。而大部分關於計算理論的研究也都專注於決策性問題,比方說著名的 $\mathsf{P}=!!!!?,,\mathsf{NP}$ 問題,關注的就是兩個「由一些決策性問題組成的集合 $\mathsf{P}$、$\mathsf{NP}$」看看他們是否相等。

本文由卡恩(tmt514)撰寫。 本站使用 GasbyJS 搭配 Bulma 製作,其原始碼為 MIT 授權。 網站內容除了題源以外,若無特別說明皆為創用 CC-BY-NC-SA 4.0 授權。 題源部份若有版權爭議還請與我聯繫,感恩。