正規語言與計算理論
Formal Languages and Theory of Computation
| 節 | 週四 |
|---|---|
3 10:10–11:00 | 正規語言與計算理論 EC114 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
The goal of this course is to introduce the theoretical framework of computation and foundations of computer science. Regular sets and context-free languages are used everywhere in the design of modern software. Finite automata and pushdown automata are conceptual machines that can process these languages. Defining Turing machines leads us further into the realm of computation theory and provides us a theoretical platform on which we can observe, discuss, and understand the behavior, capability, and limitation of computers. Decidability and tractability are covered in the course as well.
Discrete Mathematics
Course format: Lectures and/or student discussion.
Three (3) examinations: Two (2) mid-terms; One (1) final. Grading policy: Mid-term #1: 30% Mid-term #2: 30% Final: 40% Total: 100%
- Introduction
- Regular Languages
- Context-free Languages
- Computational Complexity
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction, Finite Automata, Regular Expressions & Languages, and Pushdown Automata, Context-free Grammars & Languages |
| 第 2 週 | |
| 第 3 週 | |
| 第 4 週 | |
| 第 5 週 | |
| 第 6 週 | |
| 第 7 週 | |
| 第 8 週 | Mid-term Examination #1 |
| 第 9 週 | Turing Machines, Decidability, & Reducibility |
| 第 10 週 | |
| 第 11 週 | |
| 第 12 週 | Mid-term Examination #2 |
| 第 13 週 | Time Complexity, P, NP, & NP-Completeness |
| 第 14 週 | |
| 第 15 週 | |
| 第 16 週 | Final Examination |
[Required] Introduction to the Theory of Computation (2nd or 3rd Edition), Michael Sipser, Thomson Course Technology. Introduction to Automata Theory, Languages, and Computation (3rd Edition), John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley. ISBN: 0321476174 (Softback). Problem Solving in Automata, Languages, and Complexity, Ding-Zhu Du, and Ker-I Ko, Wiley-Interscience. ISBN: 0471439606 (Hardback), 0471224642 (Electronic). [Reference, downloadable in the NCTU campus]. An Introduction to Formal Languages and Automata (3rd Edition), Peter Linz, Jones and Bartlett Publishers. ISBN: 0763714224 (Hardback). ※請修課同學尊重智慧財產權!勿隨意過度影印教科書或使用未經授權之著作權與電腦軟體等。
- 地點
- EC711
- 時間
- F5 (by appointment only)
- 聯絡方式
- 校內分機 31446