教學時程、復習／實習課程、相關閱讀資料
自動機、可計算性與複雜性
因舊版課程無指定課堂作業與考試，因此統整所有作業、講義、考試內容合併列出。
自動機、可計算性與複雜性
因舊版課程無指定課堂作業與考試，因此統整所有作業、講義、考試內容合併列出。
以下的日程表提供了授課(L)，復習課(R)和測驗的資訊。
復習／實習課程部分包括用來討論的材料以及學生們在復習課中解決的問題。
該部分內容包括每週的閱讀材料。大部分閱讀資料來自教材：Michael Sipser 的《計算理論導論》Introduction to the Theory of Computation第二版，Boston, MA: Course Technology, 2005. ISBN: 0534950973.
（譯者：簡體中文譯本為《計算理論導論》第二版，張立昂等譯，機械工業出版社）
|
課 |
課程單元 |
重要日期 |
閱讀資料 |
|
|
簡介與復習Introduction and Review |
||||
|
L1 |
簡介Introduction |
指派作業1 |
教材第0章 |
|
|
R1 |
復習數學知識Math Review (PDF) |
|
教材0章 |
|
|
有窮自動機，正則語言，正則運算式Finite Automata, Regular Languages, Regular Expressions |
|
|||
|
L2 |
確定性有窮自動機(DFA) Deterministic Finite Automata (DFA) |
|
教材1.1 |
|
|
L3 |
非確定性有窮自動機 (NFA) Nondeterministic Finite Automata (NFA) |
交作業1 |
|
|
|
R2 |
確定性有窮自動機（DFA）和非確定性有窮自動機（NFA）DFAs and NFAs (PDF) |
|
教材1.1, 1.2 |
|
|
L4 |
正則運算式Regular Expressions |
|
教材1.3 |
|
|
L5 |
非正則語言Non-Regular Languages |
交作業2 |
教材1.4 |
|
|
R3 |
正則運算式和非正則語言Regular Expressions and Non-Regular Languages (PDF) |
|
教材1.3, 1.4 |
|
|
L6 |
自動機的演算法Algorithms for Automata |
|
教材第1章, 4.1 |
|
|
L7 |
測驗1 Quiz 1 |
指派作業3 |
|
|
|
R4 |
測驗1的題目和自動機綜合知識Quiz Questions and Automata Wrap-up (PDF) |
|
|
|
|
可計算性理論Computability Theory |
|
|||
|
L8 |
圖靈機Turing Machines |
|
教材第3章 (3.1, 3.3, 和3.2 – 尤其是非確定性圖靈機) |
|
|
L9 |
非確定性圖靈機 Nondeterministic Turing Machines |
交作業3 |
教材3.2 (尤其pp. 138-141), 教材4.2 (尤其pp. 160-164) |
|
|
R5 |
圖靈機Turing Machines (PDF) |
|
教材第3章 |
|
|
L10 |
不可判定性Undecidability |
|
教材第4章 (跳過pp. 156-158), 教材5.1 (直到p. 176) |
|
|
L11 |
Post對應問題(PCP) PCP |
交作業4 |
計算歷史(見教材p. 176) 和教材5.2 |
|
|
R6 |
不可判定性Undecidability (PDF) |
|
教材第4章 (到176頁), 教材5.1 (尤其 pp. 181-182), 5.2 |
|
|
L12 |
計數器和堆疊器 Counter and Stack Machines |
|
Hopcroft, John, Rajeev Motwani和Jeffrey Ullman.《自動機理論、語言和計算導論》Introduction to Automata Theory, Languages and Computation第2版，Reading, MA: Addison Wesley, 2000, section 8.5. ISBN: 0201441241. |
|
|
L13 |
簡化性Reducibility |
交作業5 |
教材5.3 |
|
|
R7 |
計數器和堆疊器，簡化性，Rice定理Counter and Stack Machines, Reducibility, Rice's Theorem (PDF) |
|
教材5.3 |
|
|
L14 |
遞迴定理Recursion Theorem |
|
教材6.1 |
|
|
L15 |
測驗2 Quiz 2 |
指派作業6 |
|
|
|
R8 |
測驗2的題目和可計算性綜合知識Quiz 2 Questions and Computability Wrap-up (PDF) |
|
|
|
|
複雜性理論Computability Theory |
|
|||
|
L16 |
時間複雜度Time Complexity |
|
教材7.1, 7.2 |
|
|
L17 |
非確定性時間複雜度Nondeterministic Time Complexity |
交作業6 |
教材7.3 |
|
|
R9 |
P問題和NP問題P and NP (PDF) |
|
教材7.1, 7.2, 7.3 |
|
|
L18 |
NP完全性NP-Completeness |
|
教材7.4 (尤其是定理7.30) |
|
|
L19 |
Cook-Levin定理Cook-Levin Theorem |
交作業7 |
教材7.4 (定理 7.30) |
|
|
R10 |
多項式時間簡化Poly-Time Reductions |
|
|
|
|
L20 |
NP完全性 II NP-Completeness II |
交作業8 |
教材7.5 |
|
|
R11 |
NP完全性NP-Completeness (PDF) |
|
教材7.5 |
|
|
L21 |
進階時間複雜度 Advanced Time Complexity |
|
教材9.1, 9.2 |
|
|
L22 |
測驗3 Quiz 3 |
指派作業9 |
|
|
|
R12 |
測驗3的題目和時間複雜度結尾Quiz 3 Questions and End of Time Complexity |
|
|
|
|
L23 |
空間複雜度Space Complexity |
|
教材8.4, 8.5, 8.6 |
|
|
L24 |
空間複雜度II Space Complexity II |
交作業9 |
教材8.4, 8.5, 8.6 |
|
|
R13 |
空間複雜度III Space Complexity III (PDF) |
|
教材8.4, 8.5, 8.6 |
|
|
L25 |
概率複雜度Probabilistic Complexity |
|
教材10.2 |
|
|
L26 |
概率複雜度續 Probabilistic Complexity (cont.) |
指派練習作業10.5 |
教材10.2 |
|
|
R14 |
概率複雜度和互動式證明Probabilistic Complexity and Interactive Proofs |
|
選讀： 教材10.4 |
|
|
|
期末考試復習(可選) Final Exam Review Session (Optional) |
|
|
|
|
|
期末考試Final Exam |
|
|
|