正規語言與計算理論
Formal Languages and Theory of Computation
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 正規語言與計算理論 EC115 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 正規語言與計算理論 EC115 |
* 根據陽明交大上課時間表所列
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 discussions.</LI> <LI>Course website: NCTU E3 platform</LI> </UL>
<UL> <LI>Three (3) Examinations: Two (2) Mid-terms; One (1) final examinations.</LI> <LI>Grading policy: <UL><LI>Mid-term #1: 30%</LI> <LI>Mid-term #2: 30%</LI> <LI>Final: 40%</LI> <LI>Total: 100%</LI></UL></LI> </UL>
- Introduction
- Regular Languages
- Context-free Languages
- Computational Complexity
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction |
| 第 2 週 | Finite Automata, Regular Expressions & Languages |
| 第 5 週 | Pushdown Automata, Context-free Grammars & Languages |
| 第 9 週 | Mid-term Examination #1 |
| 第 10 週 | Turing Machines, Decidability, & Reducibility |
| 第 13 週 | Mid-term Examination #2 |
| 第 14 週 | Time Complexity, P, NP, & NP-Completeness |
| 第 18 週 | Final Examination |
<OL> <LI><B>[Required] </B><I>Introduction to the Theory of Computation</I> (2nd/3rd Edition), Michael Sipser, Thomson Course Technology. -- 歐亞書局代理,聯絡電話: 02-77053361,</LI> <LI><I>Introduction to Automata Theory, Languages, and Computation</I> (3rd Edition), John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Addison-Wesley. ISBN: 0321476174 (Softback).</LI> <LI><I>Problem Solving in Automata, Languages, and Complexity</I>, Ding-Zhu Du, and Ker-I Ko, Wiley-Interscience. ISBN: 0471439606 (Hardback), 0471224642 (Electronic). [Reference, downloadable in the NCTU campus].</LI> <LI><I>An Introduction to Formal Languages and Automata</I> (3rd Edition), Peter Linz, Jones and Bartlett Publishers. ISBN: 0763714224 (Hardback).</LI> </OL> ※請修課同學尊重智慧財產權!勿隨意過度影印教科書或使用未經授權之著作權與電腦軟體等。
- 地點
- EC711
- 時間
- 1EF (by appointment)
- 聯絡方式
- 校內分機 31446