正規語言與計算理論
Formal Languages and Theory of Computation
學期
113-1
學分
3
學分
當期課號
535503
永久課號
CSIC30068
開課單位
資訊科學與工程研究所
授課教師
曾文貴
校區
光復
類別
選修
上課時間表
| 節 | 週一 | 週四 |
|---|---|---|
3 10:10–11:00 | 正規語言與計算理論 ED302 2 節連堂 | |
4 11:10–12:00 | ||
7 15:30–16:20 | 正規語言與計算理論 ED302 |
* 根據陽明交大上課時間表所列
概述
透過數學模型來瞭解計算機的能力,進而瞭解計算問題的本質與分類。
先修科目
程式設計,演算法
教學方式
實體上課講授,不提供遠端上課。
評分方式
(1) Homeworks: 25% (2) Two Midterms: 50% (3) Final: 25% ps. 暫定
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction and Regular languages (1) |
| 第 2 週 | Regular languages (2) |
| 第 3 週 | Regular languages (3) |
| 第 4 週 | Regular languages (4) |
| 第 5 週 | Midterm IContext-free languages (1) |
| 第 6 週 | Context-free languages (2) |
| 第 7 週 | Context languages (3) |
| 第 8 週 | Context languages (4) |
| 第 9 週 | Midterm II Church-Turing thesis (1) |
| 第 10 週 | Church-Turing thesis (2) |
| 第 11 週 | Decidability (1) |
| 第 12 週 | Decidability (2) |
| 第 13 週 | Reducibility |
| 第 14 週 | Complexity (1) |
| 第 15 週 | Complexity (2) |
| 第 16 週 | Complexity (3)Final |
教科書
Michael Sipser, Introduction to the Theory of Computation, 3rd Ed., 2013, Cengage Learning
Office Hours
- 地點
- EC238
- 時間
- M: 1:30pm-3:00pm Th: 1:30pm-3:00pm Appointment by emails
- 聯絡方式
- wgtzeng@cs.nycu.edu.tw