正規語言與計算理論(英文授課)
Formal Languages and Theory of Computation
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 正規語言與計算理論(英文授課) EC122 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 正規語言與計算理論(英文授課) EC122 |
* 根據陽明交大上課時間表所列
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
<UL> <LI>Course format: Lectures, student individual and group discussion.</LI> </UL>
Three (3) Examinations: Two (2) Mid-terms; One (1) final examinations. Grading policy: Mid-term #1: 30% Mid-term #2: 30% Final: 40% Total: 100%
- Introduction
- Regular Languages
- Context-free Languages
- Computational Complexity
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction |
| 第 2 週 | Finite Automata, Regular Expressions & Languages |
| 第 5 週 | Pushdown Automata, Context-free Grammars & Languages |
| 第 8 週 | Mid-term Examination #1 |
| 第 9 週 | Turing Machines, Decidability, & Reducibility |
| 第 12 週 | Mid-term Examination #2 |
| 第 13 週 | Time Complexity, P, NP, & NP-Completeness |
| 第 16 週 | Final Examination |
[Required] Introduction to the Theory of Computation (2nd/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
- 時間
- 1F (by appointment)
- 聯絡方式
- 校內分機 31446