自動機，可計算性與複雜性

• 課程重點

本課程包含一套完整的作業。另外，復習／實習課程部分包括很多練習問題。6.045J是本系“理論資訊科學”系列中的一門課程。

 

教學大綱

此教學大綱說明了本課程的學習目標，預期成果，必備先修課，必讀資料，課程形式與課程規範。

 

• 學習目標

修完6.045這門課後，學生將能夠掌握計算理論的基本方法和結論。他們將能夠運用這些方法去解決來自不同領域的問題，以及能夠藉由計算解法得到這些問題的答案。

特別是，學生能夠：

1.說明對於不可判定性問題和固有複雜問題的計算解法的理論上的限制。

2.描述不同領域中，不可判定性問題與固有不可行問題的計算解法的具體例子。

3.設計與分析過程的複雜度， 以確定各類自動機的屬性。

4.理解機器模型的形式定義。

5.證明各種問題的不可判定性或複雜性。

 

• 預期成果

學生應該能夠：

1.依據特殊屬性建構有窮自動機。

2.在有窮自動機的多種不同的表達方法之間轉換。

3.運用鴿巢原理（譯者：即抽屜原理）以及封閉性來證明某些無法用有窮自動機解決的問題。

4.計算關於自動機，語言與圖論的簡單程式的可計算複雜度的漸近值。

5.用對角矩陣與簡化方法證明不可判定性。

6.用可識別性與可判定性的關係來確定問題的可判定性。

7.描述各種不可判定問題的具體例子。

8.定義與解釋"P = NP?"問題與NP完全性的重要性。

9.描述各種NP完全性問題的具體例子。

10.用對角矩陣與多項式時間簡化方法證明時間與空間複雜度的下限。

11.定義確定性與非確定性計算的時間與空間，並解釋彼此間的關係。

12.描述已知的在多項式時間不能解決的可判定問題的具體例子。

 

目標 vs. 成果

目標：相關的成果

 

不可判定性與複雜性：5, 6, 7, 8, 9, 10, 11, 12

不可判定問題與複雜問題的例子：6, 9, 11, 12

自動機：1, 2, 3

正則模型：1, 2, 3

證明不可判定性與複雜性：3, 4, 5, 6, 7, 8, 10, 11

 

成果：反映的目標

 

構造有窮自動機：3, 4

正則運算式等：3, 4

非正則性：3, 4, 5

漸進複雜度： 5

不可判定的例子：1, 2

不可判定性：1, 5

可識別性：1, 5

P與NP：1, 5

NP例子：1, 2

不可判定性與複雜性：1, 5

時間－空間（複雜度）：1, 2, 5

例子：1, 2

 

• 必備先修課

你應已修過6.042J,資訊科學數學。6.045 實際上是一門數學課程，你也要對數學概念相當熟悉。尤其是，你能熟練運用正規的數學證明，並能將證明恰當地寫出。

 

• 課程資料

本課程的教材是Michael Sipser 的《計算理論導論》Introduction to the Theory of Computation第二版，Boston, MA: Course Technology, 2005. ISBN: 0534950973.

除了教材以外，過去的學生認為以下幾本書很有用。我們希望學生在教科書中遇到費解的內容時可以參考這幾本書籍的解釋：

Martin, John. 《計算理論與語言導論》Introduction to Languages and the Theory of Computation.. New York, NY: McGraw Hill, 2002. ISBN: 0072322004.

Kozen, Dexter. 《自動機與可計算性》Automata and Computability. New York, NY: Springer-Verlag, 1999. ISBN: 0387949070.

Garey, Michael, and David S. Johnson. 《資訊與棘手問題：NP－完全性理論指導》 Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W.H. Freeman and Company, 1979. ISBN: 0716710455.

 

• 評分政策

最後的評分包括每週的作業，三次課堂測驗和期末考試。計算最終成績的方法如下：

Course grading.
項目	比重
作業	30%
測驗	30%
期末考試	30%
課堂和復習課討論的參與	10%

 

• 課後作業

作業要在每週上課前交，你必須瞭解準時交作業是很重要的，我們不接受遲交的作業。在最後計算總成績的時候我們會去掉你作業的一個最低分數，所以請勿為某次作業的不理想成績而擔憂。

正確的答案與證明會被給予滿分。我們對於不完全的或者有小瑕疵的解答會給予部分分數。我們也會對如“我不知道”這類答案給予一點分數。有瑕疵的證明同樣也會給予部分分數，並且如果你將瑕疵部分注明的話，可以得到更高的分數。我們對於毫無道理，明顯想要混分數的答案將不給分。請只寫下你有把握的答案。胡亂的猜測只會浪費你我的時間。你要相信：錯誤的證明對你的頭腦是有害的。

我們要求所有的作業都必須是打字的。我們會提供LaTeX工具讓你充實作業答案，不過你並不一定要用到它們。允許手繪圖表。

 

合作原則

我們非常鼓勵合作。我們不期望你獨立完成每題作業，不過，我們期望你寫下自己的答案，即使該答案來自你合作者的貢獻。 再次重申：每個人必須獨立寫出自己的答案。並請注明與你合作的人。如果你用到了教科書以外的資料，請在每題中注明所用的參考資料。

 

• 測驗和考試

共有三次測驗和一次期末考試。測驗會在下面的時間舉行

第十日

第二十二日

第三十三日

每次測驗會涉及課程的一單元，期末考試涉及總的課程。測驗的那天就不會有作業了。