正規語言與計算理論
Formal Languages and Theory of Computation
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 正規語言與計算理論 ED302（光復） 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 正規語言與計算理論 ED302（光復） |
* 根據陽明交大上課時間表所列
The Ultimate Question: What inherently makes some problems computationally effortless while others remain frustratingly difficult? Despite five decades of intense research, computer scientists still don't have a definitive answer to this question. However, this pursuit has yielded a massive breakthrough: an elegant classification framework that categorizes problems based on their intrinsic difficulty. This theoretical blueprint has directly revolutionized the ancient field of cryptography. By intentionally building security systems around these certified "hard" problems, cryptographers have successfully engineered entirely new, ultra-secure codes.
Algorithms, Introduction to Formal Languages, etc
無備註
Lecturing
Weekly quiz and homework assignments： 30% Mid-term Exam： 40% Final project: 30%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Quick review on Turing machines, 2026-09-07(一),2026-09-10(四) |
| 第 2 週 | NP and NP-completeness 2026-09-14(一),2026-09-17(四) |
| 第 3 週 | Space complexity 2026-09-21(一),2026-09-24(四) |
| 第 4 週 | PSACE-completeness, NL-completeness 2026-09-28(一),2026-10-01(四) |
| 第 5 週 | Polynomial Hierarchy and Alternations 2026-10-05(一),2026-10-08(四) |
| 第 6 週 | Boolean Circuits, P/poly 2026-10-12(一),2026-10-15(四) |
| 第 7 週 | Randomized computation 2026-10-19(一),2026-10-22(四) |
| 第 8 週 | Interactive proofs 2026-10-26(一),2026-10-29(四) |
| 第 9 週 | Cryptography 2026-11-02(一),2026-11-05(四) |
| 第 10 週 | Midterm Exam 2026-11-09(一),2026-11-12(四) |
| 第 11 週 | PCP theorem and hardness of approximation: An introduction Proof complexity 2026-11-16(一),2026-11-19(四) |
| 第 12 週 | Decision Trees 2026-11-23(一),2026-11-26(四) |
| 第 13 週 | Circuit Lower bounds 2026-11-30(一),2026-12-03(四) |
| 第 14 週 | Proof Complexity 2026-12-07(一),2026-12-10(四) |
| 第 15 週 | Hardness amplification and error-correcting codes (if time permits) 2026-12-14(一),2026-12-17(四) |
| 第 16 週 | Hardness amplification and error-correcting codes (if time permits) 2026-12-21(一),2026-12-24(四) |
參考書： 1. Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak, published by Cambridge University Press, 2009 2. Theory of Computational Complexity, 2nd Ed, Ding-Zhu Du and Ker-I Ko, published by John Wiley & Sons, 2014 3. Introduction to the Theory of Computation, 3rd Ed. Michael Sipser, published by Cengage Learning, 2012
- 地點
- EC623
- 時間
- By appointment
- 聯絡方式
- sctsai@cs.nycu.edu.tw